题解 P1703 【那个什么密码2】

· · 题解

这应该是平衡树维护区间翻转的模板题吧

对于一次翻转（L , R）

主流的做法是Splay把编号为L-1的节点旋转到根

再把编号为R+1的节点旋转到根的右节点

这样根的右节点的左子树全为L---R，打上翻转标记即可

顺便再拓展一种算法，也就是我写的非选择treap

核心操作是split和merge

split是从某一位置把平衡树拆开，返回两个值即两根

merge是合并两个子树，要求保证某一子树元素严格小于另一子树

这样翻转区间L---R的时候

可以通过split拆出树1---L-1，树L---R，树R+1---n(均为编号)

在第二棵树的根上打上翻转标记

按顺序合并三棵树，在合并过程中下放标记

即可以复杂度O(len*log(len))的复杂度水过此题

以下是我的代码：

#include<cmath>
#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>
#include<ctime>
#define rt register int
#define ll long long
#define r read()
using namespace std;
inline int read()
{
    int x = 0; int zf = 1; char ch;
    while (ch != '-' && (ch < '0' || ch > '9')) ch = getchar();
    if (ch == '-') zf = -1, ch = getchar();
    while (ch >= '0' && ch <= '9') x = x * 10 + ch - '0', ch = getchar(); return x * zf;
}
int i,j,m,n,x,y,z,cnt,all,num,Root;
struct points{
    int ls,rs,val,size,lazy;
}a[10010];
struct two{int ls,rs;};
inline void up(const int x)
{
    a[x].size=a[a[x].ls].size+a[a[x].rs].size+1;
}
inline void down(const int x)
{
    if(!a[x].lazy)return;
    swap(a[x].ls,a[x].rs);
    a[a[x].ls].lazy^=1;
    a[a[x].rs].lazy^=1;
    a[x].lazy=0;
}
inline int merge(const int x,const int y)//x < y
{
    if(!x)return y;if(!y)return x;
    down(x);down(y);
    if(a[x].val>a[y].val)
    {
        a[y].ls=merge(x,a[y].ls);
        up(y);
        return y;
    }
    else
    {
        a[x].rs=merge(a[x].rs,y);
        up(x);
        return x;        
    }
}
two split(const int x,const int val)//rank 1...val ;val+1...n
{
    two ret={0,0};down(x);
    if(!x)return ret;rt p=a[a[x].ls].size+1;
    if(p<=val)
    {
        ret=split(a[x].rs,val-p);
        a[x].rs=ret.ls;
        ret.ls=x;
    }
    else
    {
        ret=split(a[x].ls,val);
        a[x].ls=ret.rs;
        ret.rs=x;
    }up(x);
    return ret;
}
char v[10010],k,c[10010];short len1,len2;
void writes(const int x)
{
    down(x);
    if(a[x].ls)writes(a[x].ls);
    putchar(c[x]);
    if(a[x].rs)writes(a[x].rs);
}
inline int newnode(const int x)
{
    cnt++;a[cnt].size=1;a[cnt].val=rand();return cnt;
}
inline void insert(const int val)
{
    two u=split(Root,val);
    Root=merge(merge(u.ls,u.rs),newnode(val));
}
inline void solve(const int L,const int R)
{
    two p1=split(Root,L-1); 
    two p2=split(p1.rs,R-a[p1.ls].size);
    a[p2.ls].lazy^=1; 
    Root=merge(p1.ls,merge(p2.ls,p2.rs));
}
int main()
{
    srand(time(0));j=0;
    scanf("%s %s",v+1,c+1);rt len1=strlen(v+1);n=strlen(c+1);
    for(rt i=1,j=1;i<=n;i++,j++)
    {
        if(j>len1)j-=len1;
        if(v[j]<='Z')k=v[j]-'A';else k=v[j]-'a';
        if(c[i]<='Z')k+=c[i]-'A';else k+=c[i]-'a';
        if(k>=26)k-=26;
        if(c[i]<='Z')c[i]='A'+k;else c[i]='a'+k;
    }
    for(rt i=1;i<=n;i++)insert(i);
    for(m=r;m;m--)
    {
        x=r;y=r;
        solve(x,y);
    }
    writes(Root);
    return 0;
}