1 條題解
-
0
扶苏的问题
题目
题目描述
给定一个长度为 的序列 ,要求支持如下三个操作:
- 给定区间 ,将区间内每个数都修改为 。
- 给定区间 ,将区间内每个数都加上 。
- 给定区间 ,求区间内的最大值。
输入格式
第一行是两个整数,依次表示序列的长度 和操作的个数 。 第二行有 个整数,第 个整数表示序列中的第 个数 。 接下来 行,每行表示一个操作。每行首先有一个整数 ,表示操作的类型。
- 若 ,则接下来有三个整数 ,表示将区间 内的每个数都修改为 。
- 若 ,则接下来有三个整数 ,表示将区间 内的每个数都加上 。
- 若 ,则接下来有两个整数 ,表示查询区间 内的最大值。
输出格式
对于每个 的操作,输出一行一个整数表示答案。
题解
解法:线段树
方法:用两个懒标记,
lazy1
存的是相加懒标记,lazy2
存的是修改懒标记,tree
存的是最大值。 但是问题来了:又相加又覆盖怎么解决?修改
当我们需要修改时,我们不需要管
lazy1
相加懒标记的值,因此,我们需要将lazy1
相加懒标记清零,lazy2
修改懒标记相加。 代码:void intervalcover(int l,int r,int rt,int x,int y,LL data){ if(x<=l&&r<=y)return lazy2[rt]=tree[rt]=data,lazy1[rt]=0,void(); push_down(rt); if(x<=mid)intervalcover(lson,x,y,data); if(mid<y)intervalcover(rson,x,y,data); push_up(rt); }
相加
当我们需要相加时,我们需要先将
lazy2
修改懒标记下放,这样才能相加。inline void change_cover(int rt,LL data){lazy1[rt]=0,tree[rt]=data,lazy2[rt]=data;} inline void push_down_cover(int rt){ if(lazy2[rt]!=-INF){ change_cover(ls(rt),lazy2[rt]);change_cover(rs(rt),lazy2[rt]); lazy2[rt]=-INF; } } void intervaland(int l,int r,int rt,int x,int y,LL data){ if(x<=l&&r<=y){ push_down_cover(rt); return tree[rt]+=data,lazy1[rt]+=data,void(); } push_down(rt); if(x<=mid)intervaland(lson,x,y,data); if(mid<y)intervaland(rson,x,y,data); push_up(rt); }
至于普通的下放懒标记操作,就是先下放
lazy2
修改懒标记,再下放lazy1
相加懒标记。inline void change_cover(int rt,LL data){lazy1[rt]=0,tree[rt]=data,lazy2[rt]=data;} inline void push_down_cover(int rt){ if(lazy2[rt]!=-INF){ change_cover(ls(rt),lazy2[rt]);change_cover(rs(rt),lazy2[rt]); lazy2[rt]=-INF; } } inline void change_and(int rt,LL data){tree[rt]+=data,lazy1[rt]+=data;} inline void push_down_and(int rt){ if(lazy1[rt]){ change_and(ls(rt),lazy1[rt]);change_and(rs(rt),lazy1[rt]); lazy1[rt]=0; } } inline void push_down(int rt){push_down_cover(rt);push_down_and(rt);}
合并相加,覆盖操作
这时候聪明的你一定会发现,区间和函数和区间修改函数的不同点仅仅是
if(x<=l&&r<=y)
的处理不同,这个时候,我们就可以合并成一个函数。void intervalchange(int l,int r,int rt,int x,int y,LL data,int op){ if(x<=l&&r<=y){ if(op==2){ push_down_cover(rt); return tree[rt]+=data,lazy1[rt]+=data,void(); }else return lazy2[rt]=tree[rt]=data,lazy1[rt]=0,void(); } push_down(rt); if(x<=mid)intervalchange(lson,x,y,data,op); if(mid<y)intervalchange(rson,x,y,data,op); push_up(rt); }
求值&建树
没什么好说的,注意一下
push_up()
函数inline void push_up(const int &r){tree[rt]=max(tree[ls(rt)],tree[rs(rt)]);}
最终的代码
注意:一定要开
long long
,不开long long
见祖宗!#include<cstdlib> #include<cstring> #include<cstdio> #include<cctype> #include<algorithm> using std::max; typedef long long LL; typedef unsigned long long ULL; namespace FastIo{ typedef __uint128_t ULLL; static char buf[100000],*p1=buf,*p2=buf,fw[100000],*pw=fw; #define gc p1==p2&&(p2=(p1=buf)+fread(buf,1,100000,stdin),p1==p2)?EOF:*p1++ inline void pc(const char &ch){ if(pw-fw==100000)fwrite(fw,1,100000,stdout),pw=fw; *pw++=ch; } #define fsh fwrite(fw,1,pw-fw,stdout),pw=fw struct FastMod{ FastMod(ULL b):b(b),m(ULL((ULLL(1)<<64)/b)){} ULL reduce(ULL a){ ULL q=(ULL)((ULLL(m)*a)>>64); ULL r=a-q*b; return r>=b?r-b:r; } ULL b,m; }HPOP(10); struct QIO{ char ch; int st[40]; bool pd; template<class T>inline void read(T &x){ x=0,ch=gc,pd=false; while(!isdigit(ch)){pd=ch=='-'?true:false;ch=gc;} while(isdigit(ch)){x=(x<<3)+(x<<1)+(ch^48);ch=gc;} if(pd)x=-x; } inline void write(LL a){ if(a<0)a=-a,pc('-'); do{st[++st[0]]=HPOP.reduce(a);a/=10;}while(a); while(st[0])pc(st[st[0]--]^48); pc('\n'); } }qrw; } using namespace FastIo; const LL INF=1e18;//有些题解把INF设为1145141919810 #define NUMBER1 1000000 #define P(A) A=-~A #define fione_i(begin,end) for(register int i=begin;i<=end;P(i)) #define ls(rt) rt<<1 #define rs(rt) rt<<1|1 #define mid (l+r>>1) #define lson l,mid,ls(rt) #define rson mid+1,r,rs(rt) LL a[NUMBER1+5]; struct Segment{ LL tree[(NUMBER1<<3)+5],lazy1[(NUMBER1<<3)+5],lazy2[(NUMBER1<<3)+5]; inline void change_cover(int rt,LL data){lazy1[rt]=0,tree[rt]=data,lazy2[rt]=data;} inline void push_down_cover(int rt){ if(lazy2[rt]!=-INF){ change_cover(ls(rt),lazy2[rt]);change_cover(rs(rt),lazy2[rt]); lazy2[rt]=-INF; } } inline void change_and(int rt,LL data){tree[rt]+=data,lazy1[rt]+=data;} inline void push_down_and(int rt){ if(lazy1[rt]){ change_and(ls(rt),lazy1[rt]);change_and(rs(rt),lazy1[rt]); lazy1[rt]=0; } } inline void push_down(int rt){push_down_cover(rt);push_down_and(rt);} inline void push_up(const int &rt){tree[rt]=max(tree[ls(rt)],tree[rs(rt)]);} void build(int l,int r,int rt){ lazy2[rt]=-INF; if(l==r)return tree[rt]=a[l],void(); build(lson);build(rson); push_up(rt); } LL intervalmax(int l,int r,int rt,int x,int y){ if(x<=l&&r<=y)return tree[rt]; push_down(rt); LL res(-INF);//不要把res初始化为0! if(x<=mid)res=max(intervalmax(lson,x,y),res); if(mid<y)res=max(res,intervalmax(rson,x,y)); return res; } void intervalchange(int l,int r,int rt,int x,int y,LL data,int op){ if(x<=l&&r<=y){ if(op==2){ push_down_cover(rt); return tree[rt]+=data,lazy1[rt]+=data,void(); }else return lazy2[rt]=tree[rt]=data,lazy1[rt]=0,void(); } push_down(rt); if(x<=mid)intervalchange(lson,x,y,data,op); if(mid<y)intervalchange(rson,x,y,data,op); push_up(rt); } }seg; signed main(){ int m,k,x,y,op,n; qrw.read(n); qrw.read(m); fione_i(1,n)qrw.read(a[i]); seg.build(1,n,1); while(m--){ qrw.read(op); qrw.read(x); qrw.read(y); if(op==3)qrw.write(seg.intervalmax(1,n,1,x,y)); else{ qrw.read(k); seg.intervalchange(1,n,1,x,y,k,op); } } fsh; exit(0); return 0; }
- 1
資訊
- ID
- 254
- 時間
- 2000ms
- 記憶體
- 512MiB
- 難度
- 4
- 标签
- 遞交數
- 11
- 已通過
- 5
- 上傳者