To start with
Splay经常用于处理区间问题(或许这就是Splay相较treap的优越之处)。
区间翻转经常用Splay处理,这类题的核心就是打标记,传标记。
Problem
Solution
处理区间[l,r]时:
将中序遍历第l-1的点x转至根,中序遍历第r+1的点y转至根的右儿子(找中序遍历第x的点,这个东西经常要用,就称之Find函数)。那么y的左子树代表的区间就是[l,r],在这里打标记。
每次区间处理,我们只需将根到x和y的链上的标记处理完毕,就能保证不会出现标记错乱。而Find函数的神奇之处,就是这个函数找寻某个点的时候,经过的节点都在根节点到这个点的链上,恰好下传标记。
Code
#include <cstdio>
#include <iostream>
#include <algorithm>
using namespace std;
const int N = 50100;
const int INF = 0x3f3f3f3f;
int a[N]; int val[N]; int tag[N];
bool rev[N]; int tr[N][2];
int fa[N]; int sz[N];
int n,m,root=0;
inline int read()
{
int t=1,x=0; char ch=getchar();
while(ch<'0' || ch>'9'){
if(ch=='-') t=-1;
ch=getchar();
}
while(ch>='0' && ch<='9'){
x=x*10+ch-'0';
ch=getchar();
}
return t*x;
}
void Pushup(int& k)
{
int l=tr[k][0],r=tr[k][1];
sz[k]=sz[l]+sz[r]+1;
val[k]=max(val[l],val[r]);
val[k]=max(val[k],a[k]);
}
void Pushdown(int& k)
{
int l=tr[k][0],r=tr[k][1];
if(l) {tag[l]+=tag[k];val[l]+=tag[k];a[l]+=tag[k];}
if(r) {tag[r]+=tag[k];val[r]+=tag[k];a[r]+=tag[k];}
rev[l]^=rev[k]; rev[r]^=rev[k];
if(rev[k]) swap(tr[k][0],tr[k][1]);
tag[k]=0; rev[k]=0;
}
void Build(int& k,int l,int r,int p)
{
int mid=(l+r)>>1; k=mid;
fa[k]=p; sz[k]=r-l+1;
if(l<mid) Build(tr[k][0],l,mid-1,k);
if(mid<r) Build(tr[k][1],mid+1,r,k);
}
void Rotate(int x,int& k)
{
int y=fa[x],z=fa[y];
int t=tr[y][0]==x?0:1;
if(y==k) k=x;
else{
if(tr[z][0]==y) tr[z][0]=x;
else tr[z][1]=x;
}
fa[x]=z; fa[y]=x; fa[tr[x][t^1]]=y;
tr[y][t]=tr[x][t^1]; tr[x][t^1]=y;
Pushup(y); Pushup(x);
}
void Splay(int x,int& k)
{
while(x!=k){
int y=fa[x];
if(y!=k){
int z=fa[y];
if(tr[z][0]==y^tr[y][0]==x) Rotate(x,k);
Rotate(y,k);
}
Rotate(x,k);
}
}
int Find(int x,int& k)
{
Pushdown(k);
int t=sz[tr[k][0]]+1;
if(t==x) return k;
else if(t<x) return Find(x-t,tr[k][1]);
else return Find(x,tr[k][0]);
}
void Add(int l,int r,int x)
{
l=Find(l-1,root); r=Find(r+1,root);
Splay(l,root); Splay(r,tr[l][1]);
tag[tr[r][0]]+=x; val[tr[r][0]]+=x; a[tr[r][0]]+=x;
}
void Reverse(int l,int r)
{
l=Find(l-1,root); r=Find(r+1,root);
Splay(l,root); Splay(r,tr[l][1]);
rev[tr[r][0]]^=1;
}
int Query(int l,int r)
{
l=Find(l-1,root); r=Find(r+1,root);
Splay(l,root); Splay(r,tr[l][1]);
return val[tr[r][0]];
}
int main()
{
int opt,l,r,x;
freopen("1251.in","r",stdin);
freopen("1251.out","w",stdout);
n=read(); m=read();
a[0]=val[0]=-INF;
Build(root,1,n+2,0);
for(int i=1;i<=m;i++){
opt=read(); l=read(); r=read();
if(opt==1) x=read(),Add(l+1,r+1,x);
else if(opt==2) Reverse(l+1,r+1);
else printf("%d\n",Query(l+1,r+1));
}
return 0;
}
Last but not least
类似的题还有:
BZOJ3223:比这题简单很多,只有翻转。需要注意输出时一定要下传标记。
BZOJ1552:做法多样,注意标记的处理(千万不能错乱)。