P8263

Rainbow_qwq · 2022-07-30 23:46:48 · 题解

使用可持久化平衡树处理区间复制。

使用倍增，建立表示复制 2^1,2^2,2^3... 的节点，这些节点直接由两个子节点 merge 上来。复制 k 次的话就是取对应的 2^i 节点 merge 一下。

题目中的 2 操作也不难处理，直接处理 2^i 节点与 2^i 的反节点即可。

实现用了 leafy tree，因为 fhq 只能随机合并，合并复杂度为 \log(siz_x+siz_y) 倍增处理会是 2log，而 leafy tree 合并复杂度为 \log(\frac{siz_x}{siz_y}) 倍增处理是 1log。

由于是模板题，直接放代码：

#include<bits/stdc++.h>
#define For(i,a,b) for( int i=(a);i<=(b);++i)
#define Rep(i,a,b) for( int i=(a);i>=(b);--i)
using namespace std;
inline int read()
{
    char c=getchar();int x=0;bool f=0;
    for(;!isdigit(c);c=getchar())f^=!(c^45);
    for(;isdigit(c);c=getchar())x=(x<<1)+(x<<3)+(c^48);
    if(f)x=-x;return x;
}

#define fi first
#define se second
#define pb push_back
#define mkp make_pair
typedef pair<int,int>pii;
typedef vector<int>vi;

#define maxn 200005
#define inf 0x3f3f3f3f

int n,m;
char a[maxn];

#define N 50000005
int rt,sz[N],sum[N],ls[N],rs[N],rub[N],tot,top;
bool rev[N];

int newn(){
    if(top)return rub[top--];
    return ++tot;
} 

void up(int u){
    sz[u]=sz[ls[u]]+sz[rs[u]];
    sum[u]=sum[ls[u]]+sum[rs[u]];
}
int up(int l,int r){
    int u=newn();
    return ls[u]=l,rs[u]=r,up(u),u;
}
int copy(int p){
    int u=newn();
    ls[u]=ls[p],rs[u]=rs[p],sum[u]=sum[p],sz[u]=sz[p],rev[u]=rev[p];
    return u;
}
int newn(int x){
    int u=newn(); ls[u]=rs[u]=0;
    return sz[u]=1,sum[u]=x,u;
}
int build(int l,int r){
    if(l==r)return newn(a[l]&1);
    int m=l+r>>1; return up(build(l,m),build(m+1,r));
}
int pushr(int p){
    int u=copy(p);
    return rev[u]=rev[u]^1,swap(ls[u],rs[u]),u;
}
void down(int u){
    if(!rev[u]||!ls[u])return;
    ls[u]=pushr(ls[u]),rs[u]=pushr(rs[u]),rev[u]=0;
}

const double alp=1-sqrt(2)/2,delp=alp/(1-alp);
int merge(int u,int v){
    if(!u||!v)return u|v;
    if(sz[u]>=delp*sz[v]&&sz[v]>=delp*sz[u])return up(u,v);
    if(sz[u]<=sz[v]){
        down(v);
        int l=ls[v],r=rs[v];
        if(sz[r]>=alp*(sz[u]+sz[v]))return merge(merge(u,l),r);
        down(l);
        return merge(merge(u,ls[l]),merge(rs[l],r));
    }else{
        down(u);
        int l=ls[u],r=rs[u];
        if(sz[l]>=alp*(sz[u]+sz[v]))return merge(l,merge(r,v));
        down(r);
        return merge(merge(l,ls[r]),merge(rs[r],v)); 
    }
}
void split(int p,int k,int&x,int&y){
    if(!p||!k)return x=0,y=p,void();
    if(k==sz[p])return x=p,y=0,void();
    down(p);
    if(k<=sz[ls[p]])split(ls[p],k,x,y),y=merge(y,rs[p]);
    else split(rs[p],k-sz[ls[p]],x,y),x=merge(ls[p],x);
}
int bound(int p,int k){
    if(!ls[p])return 1;
    down(p);
    if(sum[ls[p]]>=k)return bound(ls[p],k);
    return sz[ls[p]]+bound(rs[p],k-sum[ls[p]]);
}

void del(int l,int r){
    int x,y,z,tmp;
    split(rt,r,tmp,z),split(tmp,l-1,x,y);
    rt=merge(x,z);
}
int ask(int k){
    if(sum[rt]<k)return -1;
    return bound(rt,k);
}

int op,p[33],q[33];
void work(int l,int r,int k,int o)
{
    int x,y,z,tmp,u=-1,i=0; op=o;
    split(rt,r,tmp,z),split(tmp,l-1,x,y);
    p[0]=y;
    if(!o){
        while((1<<(i+1))<=k)++i,p[i]=up(p[i-1],p[i-1]);
        For(j,0,i)if(k>>j&1)u=(u==-1?p[j]:merge(u,p[j]));
    }else{
        q[0]=pushr(p[0]); 
        while((1<<(i+1))<=k)++i,p[i]=up(p[i-1],q[i-1]),q[i]=up(q[i-1],p[i-1]);
        bool r=0;
        Rep(j,i,0)if(k>>j&1)tmp=(r?q[j]:p[j]),u=(u==-1?tmp:merge(u,tmp)),r^=1;
    }
    rt=merge(merge(x,u),z);
}

signed main()
{
    n=read();
    scanf("%s",a+1);
    rt=build(1,n);

    m=read();
    For(i,1,m){
        int o=read(),l,r,x,y,z,tmp;
        if(o==4){
            printf("%d\n",ask(read()));
            continue;
        }
        l=read(),r=read();
        if(o==1||o==2)work(l,r,read(),o-1);
        else del(l,r);
    }
    return 0;
}