BruceJay's Blog

BZOJ1251 序列终结者

| Comments

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:做法多样,注意标记的处理(千万不能错乱)。

Comments

comments powered by Disqus