扶苏的问题
题目
题目描述
给定一个长度为 \(n\) 的序列 \(a\)，要求支持如下三个操作：
- 给定区间 \([l, r]\)，将区间内每个数都修改为 \(x\)。
- 给定区间 \([l, r]\)，将区间内每个数都加上 \(x\)。
- 给定区间 \([l, r]\)，求区间内的最大值。
输入格式
第一行是两个整数，依次表示序列的长度 \(n\) 和操作的个数 \(q\)。
第二行有 \(n\) 个整数，第 \(i\) 个整数表示序列中的第 \(i\) 个数 \(a_i\)。
接下来 \(q\) 行，每行表示一个操作。每行首先有一个整数 \(op\)，表示操作的类型。
- 若 \(op = 1\)，则接下来有三个整数 \(l, r, x\)，表示将区间 \([l, r]\) 内的每个数都修改为 \(x\)。
- 若 \(op = 2\)，则接下来有三个整数 \(l, r, x\)，表示将区间 \([l, r]\) 内的每个数都加上 \(x\)。
- 若 \(op = 3\)，则接下来有两个整数 \(l, r\)，表示查询区间 \([l, r]\) 内的最大值。
输出格式
对于每个 \(op = 3\) 的操作，输出一行一个整数表示答案。
题解
解法一线段树
方法：用两个懒标记，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;
}
解法二ODT——珂朵莉树
珂朵莉树不是数据结构！！！
我没用这个方法做，可以把ODT卡掉的。
如果对这种方法有兴趣的同学，可以看这道题（洛谷）（CF）。