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

· · 题解

Solution

->题面：（模拟+离线问询） 一维序列折腾问题系列

暴力算法：O(nm)

自然是平衡树来解答。。。（废话）

维护中序遍历是当前序列

int build(int l,int r){
    if (l==r) return s[l]=1,l;
    int m=(l+r)>>1;
    if (m-1>=l) ch[m][0]=build(l,m-1);
    if (m+1<=r) ch[m][1]=build(m+1,r);
    //这里不是线段树哦qwq
    s[m]=r-l+1;
    return m;
}

//先建一棵初始树好了。
//这个题只有翻转操作，所以不需要维护重数之类的。

->如果翻转的是完整子树，只要对称就好（左右儿子互换）

->如果翻转非完整子树，设位[L,R];

STEP1. 将L-1向上旋转到根节点

STEP2: 将R+1向上连续旋转到根的右儿子

->此时[L,R]被调整到同一棵子树上（根节点的左右孙子）

void rotateKth(int k,int x,int &p,bool toRt) {
    if (rev[x]) flip(x);
    if (k==s[ch[x][0]]+1) return;
    int d=k>(s[ch[x][0]]+1);
    rotateKth(k-d*(s[ch[x][0]]+1),ch[x][d],ch[x][d],toRt);
    if (toRt || x!=rt) p=rotate(x,d^1);
}

//将中序遍历k号元素一顿操作，toRt=1表示旋转到根，=0表示到根的（右）儿子
//先找k号元素，然后往子树里找，回溯时每次向上旋转

->如何旋转完整子树：直接对称，复杂度O(n)

如果子树没有被查询到...那么不需要翻转（有点像线段树QWQ）

rt=build(1,n+2);
for (int i=1,l,r;i<=m;i++) {
    cin>>l>>r,l++,r++;
    if (l==r) continue;
    rotateKth(l-1,rt,rt,true);
    rotateKth(r+1,rt,rt,false);
    rev[ch[ch[rt][1]][0]]^=1;
}
print(rt); cout<<endl;
void flip(int x) { 
    swap(ch[x][0],ch[x][1]);
    rev[ch[x][0]]^=1;
    rev[ch[x][1]]^=1;
    rev[x]^=1;
}

void print(int x) { 
    if (rev[x]) flip(x);  
    if (ch[x][0]) print(ch[x][0]); 
    if (x>=2 && x<=n+1) cout<<x-1<<" ";
    if (ch[x][1]) print(ch[x][1]);
}

完整代码：

// luogu-judger-enable-o2
#include <bits/stdc++.h>
using namespace std;
const int N=100009;
int m,n,tot=1,rt=1,ch[N][2],s[N],rev[N];
int rotate(int o,int d) {
    int k=ch[o][d^1];
    ch[o][d^1]=ch[k][d];
    ch[k][d]=o;
    s[o]=1+s[ch[o][0]]+s[ch[o][1]];
    s[k]=1+s[ch[k][0]]+s[ch[k][1]];
    return k;
}
int build(int l,int r){
    if (l==r) return s[l]=1,l;
    int m=(l+r)>>1;
    if (m-1>=l) ch[m][0]=build(l,m-1);
    if (m+1<=r) ch[m][1]=build(m+1,r);
    s[m]=r-l+1;
    return m;
}
void flip(int x) { 
    swap(ch[x][0],ch[x][1]);
    rev[ch[x][0]]^=1;
    rev[ch[x][1]]^=1;
    rev[x]^=1;
}
void print(int x) { 
    if (rev[x]) flip(x);  
    if (ch[x][0]) print(ch[x][0]); 
    if (x>=2 && x<=n+1) cout<<x-1<<" ";
    if (ch[x][1]) print(ch[x][1]);
}
void rotateKth(int k,int x,int &p,bool toRt) {
    if (rev[x]) flip(x);
    if (k==s[ch[x][0]]+1) return;
    int d=k>(s[ch[x][0]]+1);
    rotateKth(k-d*(s[ch[x][0]]+1),ch[x][d],ch[x][d],toRt);
    if (toRt || x!=rt) p=rotate(x,d^1);
}
int main(){
    cin>>n>>m;
    rt=build(1,n+2);
    for (int i=1,l,r;i<=m;i++) {
        cin>>l>>r,l++,r++;
        if (l==r) continue;
        rotateKth(l-1,rt,rt,true);
        rotateKth(r+1,rt,rt,false);
        rev[ch[ch[rt][1]][0]]^=1;
    }
    print(rt); cout<<endl;
    return 0;
}

AC记录： qwqwq

致谢： @distantlight 老师