P8796 [蓝桥杯 2022 国 AC] 替换字符

题面

给定一个仅含小写英文字母的字符串 \(s\) 和 \(m\) 次操作，每次操作选择一个区间 \([l_i,r_i]\) 将 \(s\) 的该区间中的所有字母 \(x_i\) 全部替换成字母 \(y_i\)，问所有操作做完后，得到的字符串是什么。

对于所有评测用例，\(1 \leq |s|, m \leq 10^5\)，\(1 \leq l_i \leq r_i \leq |s|\)，\(x_i\neq y_i\)，其中 \(|s|\) 表示字符串 \(s\) 的长度。

思路

首先我写了一个蹩脚的 FHQ-Treap，后来被我证伪了……

其实这道题是一个线段树合并 / 分裂水题。

首先先按照 \(s\) 的值域建出 \(26\) 棵线段树。对于每一个 \(s_i\)，用第 \(s_i\) 个线段树将第 \(i\) 个元素修改为 \(1\)（也就是，存在）。

然后修改的时候直接将 \([l_i,r_i]\) 从第 \(x_i\) 个线段树上分裂下来，合并到第 \(y_i\) 个线段树上，也就可以了。

最后输出的时候暴力枚举值域，找到存在的输出即可。

时间复杂度 \(O(m\log|s_i|)\)。

另外本题有双倍经验 Codeforces911G Mass Change Queries，代码就不放了，具体看 Codeforces 提交记录。

代码

#include <bits/stdc++.h>

#define int long long

#define ls(i) (t[i].ls)

#define rs(i) (t[i].rs)

#define mid ((l+r)>>1)

using namespace std;

const int N = 1e5+5;

struct node{

	int ls,rs,v;

} t[N<<8];

int root[30],tot;

inline void newnode(int &i){

	if(!i)i=(++tot);

}

void update(int p,int v,int &i,int l,int r){

	newnode(i);

	if(l==r){

		t[i].v=v;

		return;

	}

	if(p<=mid){

		update(p,v,ls(i),l,mid);

	}

	else{

		update(p,v,rs(i),mid+1,r);

	}

}

int split(int ql,int qr,int &i,int l,int r){

	int p=0;

	newnode(p);

	if(ql<=l&&r<=qr){

		t[p]=t[i];

		i=0;

	}

	else{

		if(ql<=mid){

			ls(p)=split(ql,qr,ls(i),l,mid);

		}

		if(qr>mid){

			rs(p)=split(ql,qr,rs(i),mid+1,r);

		}

	}

	return p;

}

void merge(int &x,int &y){

	if(x==0||y==0){

		if(y)x=y;

		if(x)y=x;

		return;

	}

	t[x].v+=t[y].v;

	merge(ls(x),ls(y));

	merge(rs(x),rs(y));

}

int query(int p,int i,int l,int r){

	if(!i)return 0;

	if(l==r){

		return t[i].v;

	}

	if(p<=mid){

		return query(p,ls(i),l,mid);

	}

	else{

		return query(p,rs(i),mid+1,r);

	}

}

char s[N];

int n,m;

signed main(){

	ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);

	cin>>(s+1);

	n=strlen(s+1);

	for(int i=1;i<=n;i++){

		update(i,1,root[s[i]-'a'],1,n);

	}

	cin>>m;

	while(m--){

		int li,ri,x,y;char xi,yi;

		cin>>li>>ri>>xi>>yi;

		x=xi-'a',y=yi-'a';

		int ytxy_ak_ioi = split(li,ri,root[x],1,n);

		merge(root[y],ytxy_ak_ioi);

	}

	for(int i=1;i<=n;i++){

		for(char j='a';j<='z';j++){

			if(query(i,root[j-'a'],1,n)>0){

				cout<<j;

				break;

			}

		}

	}

	return 0;

	return 0;

}

AC Record

巴特西

P8796 [蓝桥杯 2022 国 AC] 替换字符

题面

思路

代码

最新文章

热门文章