题意:
分析:
区间加,区间翻转,区间查询最大值
如果没有第二个操作的话,就是线段树裸题
但是有了第二个操作也没有关系,我们有 (fhq)
( (fhq) 据说 (treap) , (splay) , 线段树能做的它都能做,唯一的缺点就是不能同时按 (siz) 或者 (val) 作为键值来构建)
和普通的 (fhq) 没什么区别,只不过多维护一个区间最大值,同时要维护 区间加 和 区间翻转 两个标记,所以细节有亿点点多
(tip:)
- (pushu) 的时候注意是否有左右儿子,不然会和 (0) 取 (max) 使最大值为负数的情况挂掉
- (fhq) 清零时要连 (val,siz,son) 等数组一并清空,不能只是简单地将 (rt,cnt) 重置为 (0)
代码:
#include<bits/stdc++.h>
#define pii pair<int,int>
#define mk(x,y) make_pair(x,y)
#define lc rt<<1
#define rc rt<<1|1
#define pb push_back
#define fir first
#define sec second
using namespace std;
namespace zzc
{
inline int read()
{
int x=0,f=1;char ch=getchar();
while (!isdigit(ch)){if (ch=='-') f=-1;ch=getchar();}
while (isdigit(ch)){x=x*10+ch-48;ch=getchar();}
return x*f;
}
const int maxn = 1e6+5;
int n,m;
namespace fhq_treap
{
int val[maxn],mx[maxn],rev[maxn],son[maxn][2],rnd[maxn],siz[maxn],tag[maxn];
int rt,cnt;
int new_node(int x)
{
int u=++cnt;
val[u]=x;siz[u]=1;mx[u]=x;rev[u]=0;tag[u]=0;
rnd[u]=rand();
return u;
}
void pushup(int rt)
{
siz[rt]=siz[son[rt][0]]+siz[son[rt][1]]+1;
mx[rt]=val[rt];
if(son[rt][0]) mx[rt]=max(mx[rt],mx[son[rt][0]]);
if(son[rt][1]) mx[rt]=max(mx[rt],mx[son[rt][1]]);
}
void pushdown(int rt)
{
if(rev[rt]!=0)
{
swap(son[rt][0],son[rt][1]);
if(son[rt][0]) rev[son[rt][0]]^=1;
if(son[rt][1]) rev[son[rt][1]]^=1;
rev[rt]=0;
}
if(tag[rt]!=0)
{
if(son[rt][0])
{
val[son[rt][0]]+=tag[rt];
tag[son[rt][0]]+=tag[rt];
mx[son[rt][0]]+=tag[rt];
}
if(son[rt][1])
{
val[son[rt][1]]+=tag[rt];
tag[son[rt][1]]+=tag[rt];
mx[son[rt][1]]+=tag[rt];
}
tag[rt]=0;
}
pushup(rt);
}
void split(int tmp,int k,int &u,int &v)
{
if(!tmp)
{
u=0;v=0;
return ;
}
pushdown(tmp);
if(siz[son[tmp][0]]<k)
{
u=tmp;
split(son[u][1],k-siz[son[tmp][0]]-1,son[u][1],v);
pushup(u);
}
else
{
v=tmp;
split(son[v][0],k,u,son[v][0]);
pushup(v);
}
}
int merge(int x,int y)
{
if(!x||!y) return x|y;
pushdown(x);pushdown(y);
if(rnd[x]<rnd[y])
{
son[x][1]=merge(son[x][1],y);
pushup(x);
return x;
}
else
{
son[y][0]=merge(x,son[y][0]);
pushup(y);
return y;
}
}
void reverse(int l,int r)
{
int x,y,z;
split(rt,l-1,x,z);
split(z,r-l+1,y,z);
rev[y]^=1;
rt=merge(x,merge(y,z));
}
void modify(int l,int r,int k)
{
int x,y,z;
split(rt,l-1,x,z);
split(z,r-l+1,y,z);
tag[y]+=k;
val[y]+=k;
mx[y]+=k;
rt=merge(x,merge(y,z));
}
void query(int l,int r)
{
int x,y,z;
split(rt,l-1,x,z);
split(z,r-l+1,y,z);
printf("%d
",mx[y]);
rt=merge(x,merge(y,z));
}
}
using namespace fhq_treap;
void work()
{
int opt,a,b,c;
n=read();m=read();
for(int i=1;i<=n;i++) rt=merge(rt,new_node(0));
for(int i=1;i<=m;i++)
{
opt=read();
if(opt==1)
{
a=read();b=read();c=read();
modify(a,b,c);
}
else if(opt==2)
{
a=read();b=read();
reverse(a,b);
}
else
{
a=read();b=read();
query(a,b);
}
}
}
}
int main()
{
zzc::work();
return 0;
}