传送门：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 |
指针版线段树：
#include<iostream>
#include<cstdio>
#include<cmath>
#include<algorithm>
#include<queue>
#include<cstring>
#define PAU putchar(' ')
#define ENT putchar('\n')
#define CH for(int d=0;d<=1;d++) if(ch[d])
using namespace std;
const int maxn=+,maxnode=+,inf=-1u>>;
struct node{
node*ch[];int mi,mx,sm,add,set,siz;node(){mi=inf;mx=-inf;sm=add=;set=inf;}
void sett(int tag){mi=mx=set=tag;sm=tag*siz;add=;return;}
void addt(int tag){add+=tag;mi+=tag;mx+=tag;sm+=tag*siz;return;}
void down(){
if(set!=inf){CH{ch[d]->sett(set);}set=inf;}
if(add){CH{ch[d]->addt(add);}add=;}
return;
}
void update(){
mi=inf;mx=-inf;sm=;
CH{mi=min(mi,ch[d]->mi);mx=max(mx,ch[d]->mx);sm+=ch[d]->sm;}
return;
}
}seg[maxnode],*nodecnt=seg,*root;
int A[maxn],ql,qr,cv,tp;
void build(node*&x,int L,int R){
x=nodecnt++;
if(L==R) x->mi=x->mx=x->sm=A[L];
else{
int M=L+R>>;
build(x->ch[],L,M);
build(x->ch[],M+,R);
x->update();
} x->siz=R-L+;return;
}
void update(node*&x,int L,int R){
if(ql<=L&&R<=qr){
if(tp) x->addt(cv);
else x->sett(cv);
}
else{
int M=L+R>>;
x->down();
if(ql<=M) update(x->ch[],L,M);
if(qr>M) update(x->ch[],M+,R);
x->update();
}
return;
}
int _mi,_mx,_sm;
void query(node*x,int L,int R){
if(ql<=L&&R<=qr){
_mi=min(_mi,x->mi);
_mx=max(_mx,x->mx);
_sm+=x->sm;
}
else{
int M=L+R>>;
x->down();
if(ql<=M) query(x->ch[],L,M);
if(qr>M) query(x->ch[],M+,R);
} return;
}
inline int read(){
int x=,sig=;char ch=getchar();
while(!isdigit(ch)){if(ch=='-')sig=-;ch=getchar();}
while(isdigit(ch))x=*x+ch-'',ch=getchar();
return x*sig;
}
inline void write(int x){
if(x==){putchar('');return;}if(x<)putchar('-'),x=-x;
int len=,buf[];while(x)buf[len++]=x%,x/=;
for(int i=len-;i>=;i--)putchar(buf[i]+'');return;
}
int n,Q;
void init(){
n=read();Q=read();
for(int i=;i<=n;i++) A[i]=read();
build(root,,n);
return;
}
void work(){
char ch;
while(Q--){
tp=read();ql=read();qr=read();
if(tp!=){
cv=read();
update(root,,n);
}
else{
_mi=inf;_mx=-inf;_sm=;
query(root,,n);
write(_mx);PAU;write(_mi);PAU;write(_sm);ENT;
}
}
return;
}
void print(){
return;
}
int main(){init();work();print();return ;}
题解：传两个lazy标：setv,addv,addv是建立在setv上的增加量，这样来一个setv就清掉addv，来一个addv就加上去，维护懒标的时候先维护setv再维护addv就好了。
#include<iostream>
#include<cstdio>
#include<cmath>
#include<algorithm>
#include<queue>
#include<cstring>
#define PAU putchar(' ')
#define ENT putchar('\n')
using namespace std;
const int maxn=+,maxn3=+,inf=-1u>>;
int maxv[maxn3],minv[maxn3],sumv[maxn3],setv[maxn3],addv[maxn3],A[maxn];
void pushup(int o,int lc,int rc){
minv[o]=min(minv[lc],minv[rc]);
maxv[o]=max(maxv[lc],maxv[rc]);
sumv[o]=sumv[lc]+sumv[rc];
return;
}
void pushdown(int o,int lc,int rc){
if(setv[o]>=){
setv[lc]=setv[rc]=setv[o];
addv[lc]=addv[rc]=;
setv[o]=-;
} if(addv[o]){
addv[lc]+=addv[o];
addv[rc]+=addv[o];
addv[o]=;
} return;
}
void maintain(int o,int L,int R){
int lc=o<<,rc=lc|;
if(L<R&&setv[o]<) pushup(o,lc,rc);
if(setv[o]>=){
minv[o]=maxv[o]=setv[o];
sumv[o]=(R-L+)*setv[o];
} if(addv[o]){
minv[o]+=addv[o];
maxv[o]+=addv[o];
sumv[o]+=(R-L+)*addv[o];
} return;
}
int _min,_max,_sum,ql,qr,tp,cv;
void update(int o,int L,int R){
if(ql<=L&&R<=qr){
if(tp) addv[o]+=cv;
else setv[o]=cv,addv[o]=;
} else{
int M=L+R>>,lc=o<<,rc=lc|;
pushdown(o,lc,rc);
if(ql<=M) update(lc,L,M); else maintain(lc,L,M);
if(qr>M) update(rc,M+,R); else maintain(rc,M+,R);
} maintain(o,L,R);return;
}
void build(int o,int L,int R){
if(L==R) setv[o]=A[L];
else{
int M=L+R>>,lc=o<<,rc=lc|;
build(lc,L,M);build(rc,M+,R);
} maintain(o,L,R);return;
}
void query(int o,int L,int R,int add){
if(setv[o]>=){
int change=setv[o]+addv[o]+add;
_sum+=(min(R,qr)-max(L,ql)+)*change;
_min=min(_min,change);
_max=max(_max,change);
} else if(ql<=L&&R<=qr){
_sum+=sumv[o]+(R-L+)*add;
_min=min(_min,minv[o]+add);
_max=max(_max,maxv[o]+add);
} else{
int M=L+R>>,lc=o<<,rc=lc|;
if(ql<=M) query(lc,L,M,add+addv[o]);
if(M<qr) query(rc,M+,R,add+addv[o]);
} return;
}
inline int read(){
int x=,sig=;char ch=getchar();
while(!isdigit(ch)){if(ch=='-')sig=-;ch=getchar();}
while(isdigit(ch))x=*x+ch-'',ch=getchar();
return x*=sig;
}
inline void write(int x){
if(x==){putchar('');return;}if(x<)putchar('-'),x=-x;
int len=,buf[];while(x)buf[len++]=x%,x/=;
for(int i=len-;i>=;i--)putchar(buf[i]+'');return;
}
int n,Q;
void init(){
memset(setv,-,sizeof(setv));
n=read();Q=read();
for(int i=;i<=n;i++) A[i]=read();
build(,,n);
return;
}
void work(){
while(Q--){
tp=read();ql=read();qr=read();
if(tp==){//query
_sum=;_min=inf;_max=-inf;
query(,,n,);
write(_max);PAU;write(_min);PAU;write(_sum);ENT;
} else cv=read(),update(,,n);
}
return;
}
void print(){
return;
}
int main(){init();work();print();return ;}
然而分块大法好！注意query一块内是不用down的。
#include<iostream>
#include<cstdio>
#include<cmath>
#include<algorithm>
#include<queue>
#include<cstring>
#define PAU putchar(' ')
#define ENT putchar('\n')
using namespace std;
const int maxn=+,maxb=,inf=-1u>>;
int mi[maxb],mx[maxb],sm[maxb],st[maxb],en[maxb],A[maxn],set[maxb],add[maxb],b[maxn],siz[maxb],n,Q,size;
int _mi,_mx,_sm;
void update(int L,int R){
int i=b[L];if(b[L]!=b[R]) abort();
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+);
else{
for(int j=L;j<=R;j++){
_mi=min(_mi,A[j]+add[i]);
_mx=max(_mx,A[j]+add[i]);
_sm+=A[j]+add[i];
}
}return;
}
void updateb(int L,int R){
for(int b=L;b<=R;b++){
_mi=min(_mi,mi[b]);
_mx=max(_mx,mx[b]);
_sm+=sm[b];
} return;
}
void update(int b){
bool se=set[b],ad=add[b];
if(se&&ad) _mi=_mx=set[b]+add[b];
}
void build(int b){
mi[b]=inf;mx[b]=-inf;sm[b]=;
for(int i=st[b];i<=en[b];i++){
mi[b]=min(mi[b],A[i]);
mx[b]=max(mx[b],A[i]);
sm[b]+=A[i];
}return;
}
void addt(int L,int R,int cv){for(int i=L;i<=R;i++) A[i]+=cv;build(b[L]);return;}
void sett(int L,int R,int cv){for(int i=L;i<=R;i++) A[i]=cv;build(b[L]);return;}
void addb(int L,int R,int cv){
for(int b=L;b<=R;b++) add[b]+=cv,mi[b]+=cv,mx[b]+=cv,sm[b]+=cv*siz[b];return;
}
void setb(int L,int R,int cv){
for(int b=L;b<=R;b++) set[b]=cv,add[b]=,mi[b]=cv,mx[b]=cv,sm[b]=cv*siz[b];return;
}
void down(int b){
if(set[b]!=inf) sett(st[b],en[b],set[b]);
if(add[b]) addt(st[b],en[b],add[b]);
set[b]=inf;add[b]=;return;
}
inline int read(){
int x=,sig=;char ch=getchar();
while(!isdigit(ch)){if(ch=='-') sig=-;ch=getchar();}
while(isdigit(ch)) x=*x+ch-'',ch=getchar();
return x*=sig;
}
inline void write(int x){
if(x==){putchar('');return;}if(x<) putchar('-'),x=-x;
int len=,buf[];while(x) buf[len++]=x%,x/=;
for(int i=len-;i>=;i--) putchar(buf[i]+'');return;
}
void init(){
n=read();Q=read();size=(int)sqrt(n);
for(int i=;i<=n;i++){
A[i]=read();
b[i]=(i-)/size+;
if(!st[b[i]]) st[b[i]]=i;
en[b[i]]=i;
}
for(int i=b[n];i>=;i--) siz[i]=en[i]-st[i]+;
for(int i=b[n];i>=;i--) build(i);
for(int i=;i<=b[n];i++) set[i]=inf;
return;
}
void work(){
int tp,ql,qr,cv;
while(Q--){
tp=read();ql=read();qr=read();
if(tp==){
_mi=inf;_mx=-inf;_sm=;
if(b[ql]==b[qr]) update(ql,qr);
else{updateb(b[ql]+,b[qr]-);update(ql,en[b[ql]]);update(st[b[qr]],qr);}
write(_mx);PAU;write(_mi);PAU;write(_sm);ENT;
}else if(tp){
cv=read();if(b[ql]==b[qr]) down(b[ql]),addt(ql,qr,cv);
else{addb(b[ql]+,b[qr]-,cv);down(b[ql]);down(b[qr]);addt(ql,en[b[ql]],cv);addt(st[b[qr]],qr,cv);}
}else{
cv=read();if(b[ql]==b[qr]) down(b[ql]),sett(ql,qr,cv);
else{setb(b[ql]+,b[qr]-,cv);down(b[ql]);down(b[qr]);sett(ql,en[b[ql]],cv);sett(st[b[qr]],qr,cv);}
}
}
return;
}
void print(){
return;
}
int main(){
init();work();print();return ;
}