P3391 【模板】文艺平衡树（Splay）

Bertha 。 2022-05-14 11:00 197阅读 0赞

## 题目：[点击打开链接][Link 1] ##

## 题意：中文题，不解释。 ##

## 分析：这题是平衡树区间翻转的裸题，翻转过程可参考（有图解）[http://blog.51cto.com/sbp810050504/1029553][http_blog.51cto.com_sbp810050504_1029553]，其实就是用Splay来维护一个序列，而不再是一棵二叉查找树了 然后建立两个虚点1和n+2每次操作时将\[l,r\]变成\[l+1,r+1\] 翻转就是将Rank为l的点splay到根，将Rank为r+2的点splay到根的右儿子，然后给r+2的左儿子（此时就是要修改的区间）打上rev标记。今天细节参考代码，不理解的可以在纸上画一画。 ##

## 代码： ##

#pragma GCC optimize(2)
    #pragma GCC optimize(3)
    #pragma GCC optimize(4)
    #pragma comment(linker, "/STACK:102400000,102400000")
    #include<unordered_map>
    #include<unordered_set>
    #include<algorithm>
    #include<iostream>
    #include<fstream>
    #include<complex>
    #include<cstdlib>
    #include<cstring>
    #include<cassert>
    #include<iomanip>
    #include<string>
    #include<cstdio>
    #include<bitset>
    #include<vector>
    #include<cctype>
    #include<cmath>
    #include<ctime>
    #include<stack>
    #include<queue>
    #include<deque>
    #include<list>
    #include<set>
    #include<map>
    using namespace std;
    #define pt(a) cout<<a<<endl
    #define debug test
    #define mst(ss,b) memset((ss),(b),sizof(ss))
    #define rep(i,a,n) for (int i=a;i<=n;i++)
    #define per(i,a,n) for (int i=n-1;i>=a;i--)
    #define all(x) (x).begin(),(x).end()
    #define fi first
    #define se second
    #define SZ(x) ((int)(x).siz())
    #define ll long long
    #define ull unsigned long long
    #define pb push_back
    #define mp make_pair
    #define inf 0x3f3f3f3f
    #define eps 1e-10
    #define PI acos(-1.0)
    typedef pair<int,int> PII;
    const ll mod = 1e9+7;
    const int N = 1e5+10;
    
    ll gcd(ll p,ll q){return q==0?p:gcd(q,p%q);}
    ll qp(ll a,ll b) {ll res=1;a%=mod; assert(b>=0); for(;b;b>>=1){if(b&1)res=res*a%mod;a=a*a%mod;}return res;}
    int to[4][2]={
       {-1,0},{1,0},{0,-1},{0,1}};
    
    int n,m,root;
    struct Splay {
        int fa[N],son[N][2],siz[N],add[N];///懒惰标记
        void up(int k) {///更新当前节点的子树节点个数(包括本节点)
            siz[k]=siz[son[k][0]]+siz[son[k][1]]+1;
        }
        void down(int k) {///下推标记
            if(add[k]) {
                swap(son[k][0],son[k][1]);
                add[son[k][0]]^=1,add[son[k][1]]^=1;///多次交换可抵消
                add[k]=0;
            }
        }
        void rotate(int x,int &k) {///旋转
            int f=fa[x],gran=fa[f],opt;
            opt=(son[f][1]==x);
            if(f==k) k=x;else son[gran][son[gran][1]==f]=x;
            son[f][opt]=son[x][opt^1];fa[son[f][opt]]=f;
            son[x][opt^1]=f;fa[f]=x;fa[x]=gran;
            siz[x]=siz[f];up(f);
        }
        void splay(int x,int &k) {///伸展
            while(x!=k) {
                int f=fa[x],gran=fa[f];
                if(f!=k) rotate((son[f][0]==x)^(son[gran][0]==f)?x:f,k);
                rotate(x,k);
            }
        }
        void build(int l,int r,int f) {///建树(树的中序遍历即为原数列从小到大的下标
            if(l>r) return ;
            int mid=(l+r)/2;
            if(mid<f) son[f][0]=mid;
            else son[f][1]=mid;
            fa[mid]=f,siz[mid]=1;
            build(l,mid-1,mid),build(mid+1,r,mid);
            up(mid);///别忘记更新
        }
        int find(int x,int k) {///找到第k大的节点
            down(x);///下推标记
            int s=siz[son[x][0]];
            if(s+1==k) return x;
            else if(s+1>k) return find(son[x][0],k);
            else return find(son[x][1],k-s-1);
        }
        void revse(int l,int r) {///翻转区间
            int x=find(root,l),y=find(root,r+2);///先找到下标位置 (l-1,r+1)->(l,r+2)
            splay(x,root),splay(y,son[root][1]);///旋转
            add[son[y][0]]^=1;///打标记
        }
    }T;
    
    int main() {
        ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
        cin>>n>>m;
        root=(n+3)>>1;T.build(1,n+2,root);///建立两个虚点1和n+2每次操作时将[l,r]变成[l+1,r+1] 
        for(int i=1;i<=m;i++){
            int l,r;
            cin>>l>>r;
            T.revse(l,r);
        }
        for(int i=2;i<=n;i++) cout<<T.find(root,i)-1<<" ";///减回来 相当于对2-n+1操作，
        cout<<T.find(root,n+1)-1<<endl;
        return 0;
    }

[Link 1]: https://www.luogu.org/problemnew/show/P3391
[http_blog.51cto.com_sbp810050504_1029553]: http://blog.51cto.com/sbp810050504/1029553