526互联

Codeforces 1588F - Jumping Through the Array

发布时间 2023-06-06 18:43:57作者: tzc_wk

显然无法用 polylog 的数据结构维护，序列分块也不行，考虑询问分块。每 \(B\) 个询问处理一次。

将这个询问中 \(2,3\) 操作涉及到的点设为“关键点”，那么容易发现，环上每一段以关键点结尾的链在这块操作的过程中始终保持不变，也就是说我们可以把它们缩在一起。

先预处理出每个块的增量对每组询问的答案的贡献系数，这可以一遍 two pointers 求出，随后询问就可以通过实时维护一个增量数组求出。\(2\) 操作就直接对环上的每个段令其增量数组 \(+v\) 即可，由于关键点个数是 \(O(B)\) 的所以修改的位置也是 \(O(B)\) 的。\(3\) 操作直接换。取 \(B=\sqrt{q}\) 即可。总复杂度 \(O(q\sqrt{q})\)。

const int MAXN=2e5;
const int BLK=500;
int n,qu,p[MAXN+5];ll a[MAXN+5],s[MAXN+5];
struct qry{int opt,x,y;}q[MAXN+5];
struct dat{
	int x,coef,id;
	friend bool operator <(const dat &X,const dat &Y){
		return X.x<Y.x;
	}
}d[BLK*2+5];
bool vis[MAXN+5];
int nxt[MAXN+5],id[MAXN+5],coef[BLK+5][BLK*2+5],len,tmp[BLK*2+5],dcnt;
ll add[BLK*2+5];
void deal(int l,int r){
//	printf("deal %d %d\n",l,r);
	memset(vis,0,sizeof(vis));memset(nxt,0,sizeof(nxt));
	memset(id,0,sizeof(id));memset(coef,0,sizeof(coef));len=dcnt=0;
	memset(tmp,0,sizeof(tmp));memset(add,0,sizeof(add));
	for(int i=l;i<=r;i++){
		if(q[i].opt==1)d[++dcnt]={q[i].x-1,-1,i-l},d[++dcnt]={q[i].y,1,i-l};
		else if(q[i].opt==2)vis[q[i].x]=1;
		else vis[q[i].x]=vis[q[i].y]=1;
	}
	for(int i=1;i<=n;i++)if(vis[i]){
		int cur=p[i];vector<int>vec;
		while(!vis[cur])vec.pb(cur),cur=p[cur];
		vec.pb(cur);id[cur]=++len;
		for(int x:vec)nxt[x]=cur;
	}
//	for(int i=1;i<=n;i++)printf("%d%c",nxt[i]," \n"[i==n]);
//	for(int i=1;i<=n;i++)printf("%d%c",id[i]," \n"[i==n]);
	sort(d+1,d+dcnt+1);
	for(int i=1,j=1;i<=dcnt;i++){
		while(j<=d[i].x){tmp[id[nxt[j]]]++;++j;}
		for(int k=1;k<=len;k++)coef[d[i].id][k]+=d[i].coef*tmp[k];
	}
	for(int i=l;i<=r;i++){
		if(q[i].opt==1){
			ll res=s[q[i].y]-s[q[i].x-1];
			for(int k=1;k<=len;k++)res+=add[k]*coef[i-l][k];
			printf("%lld\n",res);
		}else if(q[i].opt==2){
			int cur=p[q[i].x];
			do{
				add[id[nxt[cur]]]+=q[i].y;cur=p[nxt[cur]];
			}while(cur!=p[q[i].x]);
		}else swap(p[q[i].x],p[q[i].y]);
	}
	for(int i=1;i<=n;i++)a[i]+=add[id[nxt[i]]],s[i]=s[i-1]+a[i];
}
int main(){
	scanf("%d",&n);
	for(int i=1;i<=n;i++)scanf("%lld",&a[i]),s[i]=s[i-1]+a[i];
	for(int i=1;i<=n;i++)scanf("%d",&p[i]);
	scanf("%d",&qu);int blk_sz=(int)sqrt(qu),cur=0;
	for(int i=1;i<=qu;i++)scanf("%d%d%d",&q[i].opt,&q[i].x,&q[i].y);
	for(int i=1;i<=qu;i++){
		++cur;
		if(cur==blk_sz)deal(i-cur+1,i),cur=0;
	}
	if(cur)deal(qu-cur+1,qu);
	return 0;
}