传送门：http://oj.cnuschool.org.cn/oj/home/problem.htm?problemID=1001
| WZJ的数据结构（十） |
| 难度级别：D； 运行时间限制：3000ms； 运行空间限制：51200KB； 代码长度限制：2000000B |
|
试题描述
|
|
请你设计一个数据结构，高效执行以下过程： #include<iostream> |
|
输入
|
|
见代码
|
|
输出
|
|
见代码
|
|
输入示例
|
|
5 5
1 2 3 4 5 2 1 3 0 1 5 2 1 2 3 3 2 1 4 2 1 5 |
|
输出示例
|
|
3 1 6
5 2 14 5 2 16 |
|
其他说明
|
|
1<=n,Q<=100000
0<=tp<=2 1<=A[i],v<=1000 1<=ql<=qr<=n |
指针版线段树：
1 #include<iostream> 2 #include<cstdio> 3 #include<cmath> 4 #include<algorithm> 5 #include<queue> 6 #include<cstring> 7 #define PAU putchar(' ') 8 #define ENT putchar(' ') 9 #define CH for(int d=0;d<=1;d++) if(ch[d]) 10 using namespace std; 11 const int maxn=100000+10,maxnode=200000+10,inf=-1u>>1; 12 struct node{ 13 node*ch[2];int mi,mx,sm,add,set,siz;node(){mi=inf;mx=-inf;sm=add=0;set=inf;} 14 void sett(int tag){mi=mx=set=tag;sm=tag*siz;add=0;return;} 15 void addt(int tag){add+=tag;mi+=tag;mx+=tag;sm+=tag*siz;return;} 16 void down(){ 17 if(set!=inf){CH{ch[d]->sett(set);}set=inf;} 18 if(add){CH{ch[d]->addt(add);}add=0;} 19 return; 20 } 21 void update(){ 22 mi=inf;mx=-inf;sm=0; 23 CH{mi=min(mi,ch[d]->mi);mx=max(mx,ch[d]->mx);sm+=ch[d]->sm;} 24 return; 25 } 26 }seg[maxnode],*nodecnt=seg,*root; 27 int A[maxn],ql,qr,cv,tp; 28 void build(node*&x,int L,int R){ 29 x=nodecnt++; 30 if(L==R) x->mi=x->mx=x->sm=A[L]; 31 else{ 32 int M=L+R>>1; 33 build(x->ch[0],L,M); 34 build(x->ch[1],M+1,R); 35 x->update(); 36 } x->siz=R-L+1;return; 37 } 38 void update(node*&x,int L,int R){ 39 if(ql<=L&&R<=qr){ 40 if(tp) x->addt(cv); 41 else x->sett(cv); 42 } 43 else{ 44 int M=L+R>>1; 45 x->down(); 46 if(ql<=M) update(x->ch[0],L,M); 47 if(qr>M) update(x->ch[1],M+1,R); 48 x->update(); 49 } 50 return; 51 } 52 int _mi,_mx,_sm; 53 void query(node*x,int L,int R){ 54 if(ql<=L&&R<=qr){ 55 _mi=min(_mi,x->mi); 56 _mx=max(_mx,x->mx); 57 _sm+=x->sm; 58 } 59 else{ 60 int M=L+R>>1; 61 x->down(); 62 if(ql<=M) query(x->ch[0],L,M); 63 if(qr>M) query(x->ch[1],M+1,R); 64 } return; 65 } 66 inline int read(){ 67 int x=0,sig=1;char ch=getchar(); 68 while(!isdigit(ch)){if(ch=='-')sig=-1;ch=getchar();} 69 while(isdigit(ch))x=10*x+ch-'0',ch=getchar(); 70 return x*sig; 71 } 72 inline void write(int x){ 73 if(x==0){putchar('0');return;}if(x<0)putchar('-'),x=-x; 74 int len=0,buf[15];while(x)buf[len++]=x%10,x/=10; 75 for(int i=len-1;i>=0;i--)putchar(buf[i]+'0');return; 76 } 77 int n,Q; 78 void init(){ 79 n=read();Q=read(); 80 for(int i=1;i<=n;i++) A[i]=read(); 81 build(root,1,n); 82 return; 83 } 84 void work(){ 85 char ch; 86 while(Q--){ 87 tp=read();ql=read();qr=read(); 88 if(tp!=2){ 89 cv=read(); 90 update(root,1,n); 91 } 92 else{ 93 _mi=inf;_mx=-inf;_sm=0; 94 query(root,1,n); 95 write(_mx);PAU;write(_mi);PAU;write(_sm);ENT; 96 } 97 } 98 return; 99 } 100 void print(){ 101 return; 102 } 103 int main(){init();work();print();return 0;}
题解：传两个lazy标：setv,addv,addv是建立在setv上的增加量，这样来一个setv就清掉addv，来一个addv就加上去，维护懒标的时候先维护setv再维护addv就好了。
1 #include<iostream> 2 #include<cstdio> 3 #include<cmath> 4 #include<algorithm> 5 #include<queue> 6 #include<cstring> 7 #define PAU putchar(' ') 8 #define ENT putchar(' ') 9 using namespace std; 10 const int maxn=100000+10,maxn3=300000+10,inf=-1u>>1; 11 int maxv[maxn3],minv[maxn3],sumv[maxn3],setv[maxn3],addv[maxn3],A[maxn]; 12 void pushup(int o,int lc,int rc){ 13 minv[o]=min(minv[lc],minv[rc]); 14 maxv[o]=max(maxv[lc],maxv[rc]); 15 sumv[o]=sumv[lc]+sumv[rc]; 16 return; 17 } 18 void pushdown(int o,int lc,int rc){ 19 if(setv[o]>=0){ 20 setv[lc]=setv[rc]=setv[o]; 21 addv[lc]=addv[rc]=0; 22 setv[o]=-1; 23 } if(addv[o]){ 24 addv[lc]+=addv[o]; 25 addv[rc]+=addv[o]; 26 addv[o]=0; 27 } return; 28 } 29 void maintain(int o,int L,int R){ 30 int lc=o<<1,rc=lc|1; 31 if(L<R&&setv[o]<0) pushup(o,lc,rc); 32 if(setv[o]>=0){ 33 minv[o]=maxv[o]=setv[o]; 34 sumv[o]=(R-L+1)*setv[o]; 35 } if(addv[o]){ 36 minv[o]+=addv[o]; 37 maxv[o]+=addv[o]; 38 sumv[o]+=(R-L+1)*addv[o]; 39 } return; 40 } 41 int _min,_max,_sum,ql,qr,tp,cv; 42 void update(int o,int L,int R){ 43 if(ql<=L&&R<=qr){ 44 if(tp) addv[o]+=cv; 45 else setv[o]=cv,addv[o]=0; 46 } else{ 47 int M=L+R>>1,lc=o<<1,rc=lc|1; 48 pushdown(o,lc,rc); 49 if(ql<=M) update(lc,L,M); else maintain(lc,L,M); 50 if(qr>M) update(rc,M+1,R); else maintain(rc,M+1,R); 51 } maintain(o,L,R);return; 52 } 53 void build(int o,int L,int R){ 54 if(L==R) setv[o]=A[L]; 55 else{ 56 int M=L+R>>1,lc=o<<1,rc=lc|1; 57 build(lc,L,M);build(rc,M+1,R); 58 } maintain(o,L,R);return; 59 } 60 void query(int o,int L,int R,int add){ 61 if(setv[o]>=0){ 62 int change=setv[o]+addv[o]+add; 63 _sum+=(min(R,qr)-max(L,ql)+1)*change; 64 _min=min(_min,change); 65 _max=max(_max,change); 66 } else if(ql<=L&&R<=qr){ 67 _sum+=sumv[o]+(R-L+1)*add; 68 _min=min(_min,minv[o]+add); 69 _max=max(_max,maxv[o]+add); 70 } else{ 71 int M=L+R>>1,lc=o<<1,rc=lc|1; 72 if(ql<=M) query(lc,L,M,add+addv[o]); 73 if(M<qr) query(rc,M+1,R,add+addv[o]); 74 } return; 75 } 76 inline int read(){ 77 int x=0,sig=1;char ch=getchar(); 78 while(!isdigit(ch)){if(ch=='-')sig=-1;ch=getchar();} 79 while(isdigit(ch))x=10*x+ch-'0',ch=getchar(); 80 return x*=sig; 81 } 82 inline void write(int x){ 83 if(x==0){putchar('0');return;}if(x<0)putchar('-'),x=-x; 84 int len=0,buf[15];while(x)buf[len++]=x%10,x/=10; 85 for(int i=len-1;i>=0;i--)putchar(buf[i]+'0');return; 86 } 87 int n,Q; 88 void init(){ 89 memset(setv,-1,sizeof(setv)); 90 n=read();Q=read(); 91 for(int i=1;i<=n;i++) A[i]=read(); 92 build(1,1,n); 93 return; 94 } 95 void work(){ 96 while(Q--){ 97 tp=read();ql=read();qr=read(); 98 if(tp==2){//query 99 _sum=0;_min=inf;_max=-inf; 100 query(1,1,n,0); 101 write(_max);PAU;write(_min);PAU;write(_sum);ENT; 102 } else cv=read(),update(1,1,n); 103 } 104 return; 105 } 106 void print(){ 107 return; 108 } 109 int main(){init();work();print();return 0;}
然而分块大法好！注意query一块内是不用down的。
1 #include<iostream> 2 #include<cstdio> 3 #include<cmath> 4 #include<algorithm> 5 #include<queue> 6 #include<cstring> 7 #define PAU putchar(' ') 8 #define ENT putchar(' ') 9 using namespace std; 10 const int maxn=100000+10,maxb=350,inf=-1u>>1; 11 int mi[maxb],mx[maxb],sm[maxb],st[maxb],en[maxb],A[maxn],set[maxb],add[maxb],b[maxn],siz[maxb],n,Q,size; 12 int _mi,_mx,_sm; 13 void update(int L,int R){ 14 int i=b[L];if(b[L]!=b[R]) abort(); 15 if(set[i]!=inf) _mi=min(_mi,set[i]+add[i]),_mx=max(_mx,set[i]+add[i]),_sm+=(set[i]+add[i])*(R-L+1); 16 else{ 17 for(int j=L;j<=R;j++){ 18 _mi=min(_mi,A[j]+add[i]); 19 _mx=max(_mx,A[j]+add[i]); 20 _sm+=A[j]+add[i]; 21 } 22 }return; 23 } 24 void updateb(int L,int R){ 25 for(int b=L;b<=R;b++){ 26 _mi=min(_mi,mi[b]); 27 _mx=max(_mx,mx[b]); 28 _sm+=sm[b]; 29 } return; 30 } 31 void update(int b){ 32 bool se=set[b],ad=add[b]; 33 if(se&&ad) _mi=_mx=set[b]+add[b]; 34 } 35 void build(int b){ 36 mi[b]=inf;mx[b]=-inf;sm[b]=0; 37 for(int i=st[b];i<=en[b];i++){ 38 mi[b]=min(mi[b],A[i]); 39 mx[b]=max(mx[b],A[i]); 40 sm[b]+=A[i]; 41 }return; 42 } 43 void addt(int L,int R,int cv){for(int i=L;i<=R;i++) A[i]+=cv;build(b[L]);return;} 44 void sett(int L,int R,int cv){for(int i=L;i<=R;i++) A[i]=cv;build(b[L]);return;} 45 void addb(int L,int R,int cv){ 46 for(int b=L;b<=R;b++) add[b]+=cv,mi[b]+=cv,mx[b]+=cv,sm[b]+=cv*siz[b];return; 47 } 48 void setb(int L,int R,int cv){ 49 for(int b=L;b<=R;b++) set[b]=cv,add[b]=0,mi[b]=cv,mx[b]=cv,sm[b]=cv*siz[b];return; 50 } 51 void down(int b){ 52 if(set[b]!=inf) sett(st[b],en[b],set[b]); 53 if(add[b]) addt(st[b],en[b],add[b]); 54 set[b]=inf;add[b]=0;return; 55 } 56 inline int read(){ 57 int x=0,sig=1;char ch=getchar(); 58 while(!isdigit(ch)){if(ch=='-') sig=-1;ch=getchar();} 59 while(isdigit(ch)) x=10*x+ch-'0',ch=getchar(); 60 return x*=sig; 61 } 62 inline void write(int x){ 63 if(x==0){putchar('0');return;}if(x<0) putchar('-'),x=-x; 64 int len=0,buf[15];while(x) buf[len++]=x%10,x/=10; 65 for(int i=len-1;i>=0;i--) putchar(buf[i]+'0');return; 66 } 67 void init(){ 68 n=read();Q=read();size=(int)sqrt(n); 69 for(int i=1;i<=n;i++){ 70 A[i]=read(); 71 b[i]=(i-1)/size+1; 72 if(!st[b[i]]) st[b[i]]=i; 73 en[b[i]]=i; 74 } 75 for(int i=b[n];i>=1;i--) siz[i]=en[i]-st[i]+1; 76 for(int i=b[n];i>=1;i--) build(i); 77 for(int i=1;i<=b[n];i++) set[i]=inf; 78 return; 79 } 80 void work(){ 81 int tp,ql,qr,cv; 82 while(Q--){ 83 tp=read();ql=read();qr=read(); 84 if(tp==2){ 85 _mi=inf;_mx=-inf;_sm=0; 86 if(b[ql]==b[qr]) update(ql,qr); 87 else{updateb(b[ql]+1,b[qr]-1);update(ql,en[b[ql]]);update(st[b[qr]],qr);} 88 write(_mx);PAU;write(_mi);PAU;write(_sm);ENT; 89 }else if(tp){ 90 cv=read();if(b[ql]==b[qr]) down(b[ql]),addt(ql,qr,cv); 91 else{addb(b[ql]+1,b[qr]-1,cv);down(b[ql]);down(b[qr]);addt(ql,en[b[ql]],cv);addt(st[b[qr]],qr,cv);} 92 }else{ 93 cv=read();if(b[ql]==b[qr]) down(b[ql]),sett(ql,qr,cv); 94 else{setb(b[ql]+1,b[qr]-1,cv);down(b[ql]);down(b[qr]);sett(ql,en[b[ql]],cv);sett(st[b[qr]],qr,cv);} 95 } 96 } 97 return; 98 } 99 void print(){ 100 return; 101 } 102 int main(){ 103 init();work();print();return 0; 104 }