注册 登录  
 加关注
   显示下一条  |  关闭
温馨提示!由于新浪微博认证机制调整,您的新浪微博帐号绑定已过期,请重新绑定!立即重新绑定新浪微博》  |  关闭

ydc的博客

 
 
 

日志

 
 

bzoj 2116 Joy  

2014-01-16 08:11:50|  分类: bzoj |  标签: |举报 |字号 订阅

  下载LOFTER 我的照片书  |
第一问很容易想到要差分……然后第二问的贪心也就显然了
我刚开始的做法是想维护波峰波谷,觉得应该可以的
然后去看看何朴帆的题解看有没有什么不同……发现绝大多数都是相同的。不过他还指出第一问就是所有正数加起来……好厉害的样子阿于是就这么写了
noip day2 T1……真是痛阿
叫写二分+线段树的逗逼ydc情何以堪

说下做法把……先差分
第一问就是正数和
第二问……无视掉开头的负数段和结尾的负数段后,一个操作相当于在移动负数段的端点,而一个显然的贪心是让他们移动到相邻的位置使得他们的差最小……也就是每次找到“总和-最大值”最小的负数段来贪心。很容易想到把这东西建成一棵平衡树
修改操作的话……就是要分情况讨论了……修改一个数的值,可能会造成负数段的插入和删除,同时还可能造成负数段的合并与分离……多写几个if就好了
为了程序的实现方便不妨写一个线段树来辅助

#include<iostream>
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<cmath>
#include<algorithm>
#include<map>
#define maxn 300000
using namespace std;
typedef long long LL;
template<class T>
void Read(T &digit)
{
digit=0;
char c;
for(c=getchar();(c<'0'||c>'9')&&c!='-';c=getchar());
bool type=true;
if(c=='-')
type=false,c=getchar();
for(;c>='0'&&c<='9';digit=digit*10+c-'0',c=getchar());
if(type==false)
digit=-digit;
}
int n,m,nTree;
LL delta[maxn],total;
struct Node
{
Node *fa,*son[2];
int size;
LL sum,val;
}*Root,*st[maxn];
map< int,pair<Node*,int> >Table;
int top;
struct message
{
LL maxv,sum;
message() {}
message(LL maxv,LL sum): maxv(maxv),sum(sum) {}
friend message operator + (const message &a,const message &b)
{
message c;
c.maxv=max(a.maxv,b.maxv),c.sum=a.sum+b.sum;
return c;
}
}Tree[maxn];
message Query(int l,int r)
{
message ans=message(-1<<30,0);
for(l=l-1+nTree,r=r+nTree+1;l^r^1;l>>=1,r>>=1)
{
if(~l&1)
ans=ans+Tree[l^1];
if(r&1)
ans=ans+Tree[r^1];
}
return ans;
}
void Modify(int p,LL v)
{
p+=nTree;
Tree[p]=message(v,v);
for(p=p>>1;p;p>>=1)
Tree[p]=Tree[p<<1]+Tree[p<<1|1];
}
void update(Node *p)
{
p->size=1,p->sum=p->val;
if(p->son[0])
p->size+=p->son[0]->size,p->sum+=p->son[0]->sum;
if(p->son[1])
p->size+=p->son[1]->size,p->sum+=p->son[1]->sum;
}
void Rotate(Node *p,Node *x)
{
int mark=p==x->son[1];
Node *y=p->son[mark^1],*z=x->fa;
if(y!=0)
y->fa=x;
if(z!=0)
z->son[x==z->son[1]]=p;
p->son[mark^1]=x,p->fa=z,x->son[mark]=y,x->fa=p,update(x);
}
void Splay(Node *p)
{
while(p->fa)
{
Node *x=p->fa,*y=x->fa;
if(y==0)
Rotate(p,x);
else if((p==x->son[1])^(x==y->son[1]))
Rotate(p,x),Rotate(p,y);
else
Rotate(x,y),Rotate(p,x);
}
update(p),Root=p;
}
void Insert(Node *p,int l,int r)
{
message v=Query(l,r);
LL val=v.sum-v.maxv;
if(p==0)
{
Node *q=st[top--];
q->val=q->sum=val,q->size=1;
q->son[0]=q->son[1]=q->fa=0;
Root=q;
return ;
}
for(Node *i=p;;i=i->son[i->val<val])
if(i->son[i->val<val]==0)
{
Node *q=st[top--];
q->son[0]=q->son[1]=0;
q->fa=i,q->val=val,i->son[i->val<val]=q,Splay(q);
return ;
}
}
void Delete(Node *p)
{
Splay(p);
if(p->son[0]==0&&p->son[1]==0)
Root=0;
else if(p->son[0]==0&&p->son[1]!=0)
Root=p->son[1],Root->fa=0;
else if(p->son[0]!=0&&p->son[1]==0)
Root=p->son[0],Root->fa=0;
else
for(Node *i=p->son[0];;i=i->son[1])
if(i->son[1]==0)
{
p->son[0]->fa=0,p->son[1]->fa=i,i->son[1]=p->son[1];
Splay(i);
break;
}
st[++top]=p;
}
int Query(Node *p,LL sum)
{
if(sum<=0)
return 0;
if(p==0||p->sum+sum>0)
return -1;
int ans=0;
while(1)
{
int Left=p->son[0]?p->son[0]->sum:0,sLeft=p->son[0]?p->son[0]->size:0;
if(Left+sum>0&&Left+sum+p->val<=0)
{
ans=ans+sLeft+1;
Splay(p);
return ans;
}
else if(Left+sum+p->val>0)
ans=ans+sLeft+1,sum=sum+Left+p->val,p=p->son[1];
else
p=p->son[0];
}
}
void read()
{
Table.clear();
Root=0,total=0;
static int a[maxn];
Read(n),Read(m);
top=n;
for(int i=1;i<=top;++i)
st[i]=new Node;
for(int i=1;i<=n;++i)
Read(a[i]);
for(int i=2;i<=n;++i)
{
delta[i]=a[i]-a[i-1];
if(delta[i]>0)
total+=delta[i];
}
for(nTree=1;nTree-2<n;nTree<<=1);
for(int i=nTree+1;i<=nTree+nTree;++i)
Tree[i]=message(-1<<30,0);
for(int i=1;i<=n;++i)
Tree[i+nTree]=message(delta[i],delta[i]);
for(int i=nTree;i>=1;--i)
Tree[i]=Tree[i<<1]+Tree[i<<1|1];
for(int i=2;i<=n;++i)
{
int j=i;
while(i<=n&&delta[i]<=0)
++i;
if(i!=j)
Insert(Root,j,i-1),Table[j]=make_pair(Root,i-1);
}
}
void add(int b,int d)
{
int sig1=delta[b]>0?1:-1;
delta[b]+=d;
int sig2=delta[b]>0?1:-1;
Modify(b,delta[b]);
if(sig1==1&&sig2==1)
total+=d;
else if(sig1==1&&sig2==-1)
{
total=total-(delta[b]-d);
map< int,pair<Node*,int> >::iterator R=Table.upper_bound(b),L=R;
if(L!=Table.begin())
--L;
int l=b,r=b;
if(L!=R&&L->second.second==b-1)
l=L->first,Delete(L->second.first);
if(R!=Table.end()&&R->first==b+1)
r=R->second.second,Delete(R->second.first);
if(L==R&&L->first==b+1)
Table.erase(L);
else
{
if(L->second.second==b-1)
Table.erase(L);
if(R!=Table.end()&&R->first==b+1)
Table.erase(R);
}
Insert(Root,l,r);
Table[l]=make_pair(Root,r);
}
else if(sig1==-1&&sig2==1)
{
total+=delta[b];
map< int,pair<Node*,int> >::iterator it=Table.upper_bound(b);
--it;
int l=it->first,r=it->second.second;
Delete(it->second.first),Table.erase(it);
if(l<b)
Insert(Root,l,b-1),Table[l]=make_pair(Root,b-1);
if(b<r)
Insert(Root,b+1,r),Table[b+1]=make_pair(Root,r);
}
else
{
map< int,pair<Node*,int> >::iterator it=Table.upper_bound(b);
--it;
int l=it->first,r=it->second.second;
Delete(it->second.first),Table.erase(it);
Insert(Root,l,r),Table[l]=make_pair(Root,r);
}
}
void Query()
{
for(int i=1,a,b,c,d;i<=m;++i)
{
Read(a);
if(a==1)
{
map< int, pair<Node*,int> >::iterator L=Table.begin(),R=Table.end();
int l1,r1,l2,r2;
if(delta[2]<0)
l1=2,r1=L->second.second,Delete(L->second.first),Table.erase(L);
if(delta[n]<0)
--R,l2=R->first,r2=n,Delete(R->second.first),Table.erase(R);
printf("%lld %d\n",total,Query(Root,total));
if(delta[2]<0)
Insert(Root,l1,r1),Table[2]=make_pair(Root,r1);
if(delta[n]<0)
Insert(Root,l2,r2),Table[l2]=make_pair(Root,n);
}
else
{
Read(b),Read(c),Read(d);
if(b>1)
add(b,d);
if(c<n)
add(c+1,-d);
}
}
}
int main()
{
int test;
for(Read(test);test;--test)
{
read();
Query();
}
return 0;
}

  评论这张
 
阅读(585)| 评论(0)
推荐 转载

历史上的今天

在LOFTER的更多文章

评论

<#--最新日志,群博日志--> <#--推荐日志--> <#--引用记录--> <#--博主推荐--> <#--随机阅读--> <#--首页推荐--> <#--历史上的今天--> <#--被推荐日志--> <#--上一篇,下一篇--> <#-- 热度 --> <#-- 网易新闻广告 --> <#--右边模块结构--> <#--评论模块结构--> <#--引用模块结构--> <#--博主发起的投票-->
 
 
 
 
 
 
 
 
 
 
 
 
 
 

页脚

网易公司版权所有 ©1997-2017