发现最巧妙的就是定义了最小升级系数dis,因为这个变量相当有用,但是又不容易想到(看来思维真的很重要)。。。
dis变量的定义,很好的将lazy结合起来了。就用简单的加减就很直观的转换。。
那么在有了这个变量之后,我们也就可以像一般线段树那样操作了。。
若当前lazy标记要更新,则传递给子树。。并把自己的lazy标记清空。。
若当前最大经验值大于升级的所需经验时就开始往下更新,直到不能更新位置(没有升级的了或到了叶子节点)。。
其中在这期间最重要的还是不断的更新和维护dis(升级最小系数),exp(当前区间的最大经验值),level(当前区间的最大等级)这3个变量;
最后在返回的时候,要根据子树的情况不断的更新父亲树。。。
PS:其实此题和hdu的4027有很大的相似处,就是当我们对一个区间进行更新的时候,区间值的更新情况并不一样,要根据自身情况来更新。。
#include <iostream> #include <cstring> #include <cstdio> #include <cstdio> #include <cstring> #include <string> using namespace std; const int N=10030; const int inf=1e9; struct Node { int L,R; int exp,lev; int dis; int lazy; } t[N*5]; int nd[N]; int n,k,q; void built(int l,int r,int fa) { t[fa].L=l; t[fa].R=r; t[fa].exp=0; t[fa].lev=1; t[fa].dis=nd[1]; t[fa].lazy=0; if(l==r)return ; int mid=(l+r)/2; built(l,mid,fa<<1); built(mid+1,r,fa<<1|1); } void up(int fa) { int ls=fa<<1; int rs=fa<<1|1; t[fa].exp=max(t[ls].exp,t[rs].exp); t[fa].lev=max(t[ls].lev,t[rs].lev); t[fa].dis=min(t[ls].dis,t[rs].dis); } void down(int fa) { int ls=fa<<1; int rs=fa<<1|1; t[ls].exp+=t[ls].lev*t[fa].lazy; t[ls].lazy+=t[fa].lazy; t[ls].dis-=t[fa].lazy; t[rs].exp+=t[rs].lev*t[fa].lazy; t[rs].lazy+=t[fa].lazy; t[rs].dis-=t[fa].lazy; t[fa].lazy=0; } void update(int l,int r,int fa,int v) { int ls=fa<<1; int rs=fa<<1|1; int mid=(t[fa].L+t[fa].R)/2; if(t[fa].L==t[fa].R) { t[fa].exp+=t[fa].lev*v; while(t[fa].exp>=nd[t[fa].lev]) t[fa].lev++; t[fa].dis=(nd[t[fa].lev]-t[fa].exp)/t[fa].lev; if((nd[t[fa].lev]-t[fa].exp)%t[fa].lev!=0) t[fa].dis++; return ; } if(t[fa].L>=l&&t[fa].R<=r) { if(t[fa].dis<=v) { down(fa); update(t[ls].L,t[ls].R,ls,v); update(t[rs].L,t[rs].R,rs,v); up(fa); } else { t[fa].exp+=t[fa].lev*v; t[fa].dis-=v; t[fa].lazy+=v; } return ; } if(t[fa].lazy) down(fa); if(r<=mid) update(l,r,ls,v); else if(l>mid) update(l,r,rs,v); else { update(l,mid,ls,v); update(mid+1,r,rs,v); } up(fa); } int query(int l,int r,int fa) { int ls=fa<<1,rs=fa<<1|1; int mid=(t[fa].L+t[fa].R)/2; if(t[fa].L==l&&t[fa].R==r) return t[fa].exp; if(t[fa].lazy) down(fa); if(r<=mid) return query(l,r,ls); else if(l>mid) return query(l,r,rs); else return max(query(l,mid,ls),query(mid+1,r,rs)); } int in() { char c; while(c=getchar(),c<'0'||c>'9'); int r=c-'0'; while(c=getchar(),c>='0'&&c<='9')r=r*10+c-'0'; return r; } int main() { int t=1; int cas; scanf("%d",&cas); while(cas--) { scanf("%d%d%d",&n,&k,&q); memset(nd,0,sizeof(nd)); for(int i=1; i<k; i++) nd[i]=in(); //scanf("%d",&nd[i]); nd[0]=0; nd[k]=inf; built(1,n,1); char ch[10]; int a,b,c; printf("Case %d:\n",t++); while(q--) { cin>>ch; if(ch[0]=='W') { //cin>>a>>b>>c; a=in();b=in();c=in(); update(a,b,1,c); } else { //cin>>a>>b; a=in();b=in(); //int ans=query(a,b,1); //cout<<ans<<endl; printf("%d\n",query(a,b,1)); } } //cout<<endl; puts(""); } return 0; }