RT,在板子题上去世了,求大佬挑错,谢谢大家(鞠躬)
#include<iostream>
#include<cstdio>
using namespace std;
#define int long long
int n,m,tot,rt,fa[100005],ch[100005][2],cnt[100005],val[100005],sz[100005],tag[100005][2],maxn[100005],a[100005];
inline void maintain(int x)
{
sz[x]=sz[ch[x][0]]+sz[ch[x][1]]+cnt[x];
maxn[x]=max(val[x],max(maxn[ch[x][0]],maxn[ch[x][1]]));
}
inline bool get(int x)
{
return x==ch[fa[x]][1];
}
inline void push_down(int x)
{
if(ch[x][0])
{
val[ch[x][0]]+=tag[x][0];
tag[ch[x][0]][0]+=tag[x][0];
maxn[ch[x][0]]+=tag[x][0];
}
if(ch[x][1])
{
val[ch[x][1]]+tag[x][0];
tag[ch[x][1]][0]+=tag[x][0];
maxn[ch[x][1]]+=tag[x][0];
}
if(tag[x][1])
{
ch[x][0]^=ch[x][1]^=ch[x][0]^=ch[x][1];
tag[ch[x][0]][1]^=1;
tag[ch[x][1]][1]^=1;
}
tag[x][0]=tag[x][1]=0;
}
inline void rotate(int x)
{
int y=fa[x],z=fa[y];
push_down(y);
push_down(x);
int k=get(x);
ch[y][k]=ch[x][k^1];
fa[ch[x][k^1]]=y;
ch[x][k^1]=y;
fa[y]=x;
fa[x]=z;
if(z)
ch[z][y==ch[z][1]]=x;
maintain(y);
maintain(x);
}
inline void splay(int x,int goal)
{
for(register int f=fa[x];(f=fa[x])!=goal;rotate(x))
if(fa[f]!=goal)
rotate(get(f)==get(x)? f:x);
if(!goal)
rt=x;
}
inline int build(int f,int l,int r)
{
if(l>r)
return 0;
int node=++tot,mid=(l+r)>>1;
fa[node]=f;
val[node]=maxn[node]=a[mid];
cnt[node]=1;
ch[node][0]=build(node,l,mid-1);
ch[node][1]=build(node,mid+1,r);
maintain(node);
return node;
}
inline int kth(int k)
{
int node=rt;
while(1)
{
push_down(node);
if(ch[node][0]&&k<=sz[ch[node][0]])
node=ch[node][0];
else
{
k-=cnt[node]+sz[ch[node][0]];
if(k<=0)
return node;
node=ch[node][1];
}
}
}
inline void update(int l,int r,int k)
{
l=kth(l-1);
r=kth(r+1);
splay(l,0);
splay(r,l);
tag[ch[ch[rt][1]][0]][0]+=k;
val[ch[ch[rt][1]][0]]+=k;
maxn[ch[ch[rt][1]][0]]+=k;
}
inline void reverse(int l,int r)
{
l=kth(l-1);
r=kth(r+1);
splay(l,0);
splay(r,l);
tag[ch[ch[rt][1]][0]][1]^=1;
}
int query(int l,int r)
{
l=kth(l-1);
r=kth(r+1);
splay(l,0);
splay(r,l);
return maxn[ch[ch[rt][1]][0]];
}
signed main()
{
scanf("%lld%lld",&n,&m);
maxn[0]=a[1]=a[n+2]=-1<<30;
rt=build(0,1,n+2);
while(m--)
{
int opt,x,y;
scanf("%lld%lld%lld",&opt,&x,&y);
if(opt==1)
{
int k;
scanf("%lld",&k);
update(x+1,y+1,k);
}
if(opt==2)
reverse(x+1,y+1);
if(opt==3)
printf("%lld\n",query(x+1,y+1));
}
return 0;
}