<span>gym-102307 D. Do Not Try This Problem</span>

题意

给定一个长度为\(n\)的字符串\(s\)，给定\(q\)个操作，每次操作给定\(i,a,k,c\)，表示将\(s_i,s_{i+a},\dots,s_{i+ka}\)赋值为字符\(c\)，输出经过\(q\)次操作后的字符串\(s\)。

分析

分类讨论：

• 若\(a>\sqrt n\)，直接暴力更新，单次操作时间复杂度为\(O(\sqrt n)\)，总时间复杂度为\(O(n\sqrt n)\)。
• 若\(a\le \sqrt n\)，将字符串\(s\)复制\(\sqrt{n}\)份\(t_1,t_2,\dots,t_{\sqrt n}\)（帮助理解算法流程，并不需要真的复制），对每个\(a\)所有操作离线，倒序来对\(t_a\)做每个操作，因为\(t_{a,i}\)的最终状态是由最后一次对它的操作决定的，所以每次操作可以将更新过的位置删除，删除可以用并查集或者set来删，并查集更快，当要删除\(t_a\)中第\(i\)个位置时，令\(fa[a][i]=fa[a][i+k]\)，这样我们遍历整个序列的时候就可以沿着并查集的边来跑，对于每个\(a\)的所有操作的时间复杂度为\(O(n)\)，总时间复杂度为\(O(n\sqrt n)\)。

怎么将所有的更新操作整合到字符串\(s\)上呢，用一个辅助数组\(mx\)，当第\(j\)次操作对第\(i\)个位置更新时令\(mx[i]=max(mx[i],j)\)。做完所有操作还原出\(s\)就可以了。

Code

#include<algorithm>
#include<iostream>
#include<cstring>
#include<iomanip>
#include<sstream>
#include<cstdio>
#include<string>
#include<vector>
#include<bitset>
#include<queue>
#include<cmath>
#include<stack>
#include<set>
#include<map>
#define rep(i,x,n) for(int i=x;i<=n;i++)
#define per(i,n,x) for(int i=n;i>=x;i--)
#define sz(a) int(a.size())
#define rson mid+1,r,p<<1|1
#define pii pair<int,int>
#define lson l,mid,p<<1
#define ll long long
#define pb push_back
#define mp make_pair
#define se second
#define fi first
using namespace std;
const double eps=1e-8;
const int mod=1e9+7;
const int N=1e5+10;
const int M=sqrt(1e5)+10;
const int inf=1e9;
int n,m,q;
char s[N],c[N];
int mx[N],x[N],a[N],k[N],vis[N];
int f[M][N];
int find(int x,int k){
	if(f[x][k]==k) return k;
	return f[x][k]=find(x,f[x][k]);
}
int main(){
	ios::sync_with_stdio(false);
	//freopen("in","r",stdin);
	cin>>s+1;
	cin>>q;
	n=strlen(s+1);
	m=sqrt(n);
	for(int i=1;i<=m;i++){
		for(int j=1;j<=n+1;j++) f[i][j]=j;
	}
	rep(i,1,q){
		cin>>x[i]>>a[i]>>k[i]>>c[i];
	}
	per(i,q,1){
		if(a[i]>m){
			for(int j=x[i];j<=x[i]+k[i]*a[i];j+=a[i]){
				mx[j]=max(mx[j],i);
			}
		}else{
			for(int j=x[i];j<=x[i]+k[i]*a[i];j=find(a[i],j)){
				mx[j]=max(mx[j],i);
				f[a[i]][j]=find(a[i],min(j+a[i],n+1));
			}
		}
	}
	for(int i=1;i<=n;i++) if(mx[i]) s[i]=c[mx[i]];
	cout<<s+1<<endl;
	return 0;
}