自动搬运

查看原文

来自洛谷，原作者为

	Rainbow_qwq **

搬运于2025-08-24 22:37:27，当前版本为作者最后更新于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;
}