社区讨论
悬赏关注线段树求调!
学术版参与者 3已保存回复 4
讨论操作
快速查看讨论及其快照的属性,并进行相关操作。
- 当前回复
- 4 条
- 当前快照
- 1 份
- 快照标识符
- @lo7mztzt
- 此快照首次捕获于
- 2023/10/27 04:28 2 年前
- 此快照最后确认于
- 2023/10/27 04:28 2 年前
CPP
#include<bits/stdc++.h>
using namespace std;
string s;
int n,tot,size;
int a[100010];
struct node
{
int l,r;
int c[30];
}tr[400040];
void build(int c,int l,int r);
inline void init(){
cin >> s;
for(int i = 1;i <= s.size();i++)
a[i] = s[i-1] - 'a';
size = s.size();
cin >> n;
build(1,1,size);
}
inline void pushdown(int c)
{
for(int i=0;i<=26;i++)
tr[c*2].c[i] = tr[c].c[tr[c*2].c[i]];
for(int i=0;i<=26;i++)
tr[c*2+1].c[i] = tr[c].c[tr[c*2+1].c[i]];
for(int i=0;i<=26;i++)
tr[c].c[i] = i;
}
void build(int c,int l,int r){
tot++;
tr[c].l = l;
tr[c].r = r;
for(int i = 0;i <= 26;i++)
tr[c].c[i] = i;
if(l == r) {return ;}
int mid = (l+r)/2;
build(c*2,l,mid);
build(c*2+1,mid+1,r);
}
void change(int c,int l1,int r1,int x,int y){
if(c > tot) return ;
if(tr[c].l >= l1 && tr[c].r <= r1)
{
for(int i=0;i<=26;i++)
if(tr[c].c[i] == x) tr[c].c[i] = y;
return ;
}
pushdown(c);
if(tr[c*2].r >= l1) change(c*2,l1,r1,x,y);
if(tr[c*2+1].l <= r1) change(c*2+1,l1,r1,x,y);
}
void check(int c)
{
if(c > tot) return ;
if(tr[c].l == tr[c].r) {cout << char('a'+tr[c].c[a[tr[c].l]]);return ;}
pushdown(c);
check(c*2);
check(c*2+1);
}
int main(){
ios::sync_with_stdio(false);
init();
for(int i=1;i<=n;i++){
int l1,r1;char a1,b1;
cin >> l1 >> r1 >> a1 >> b1;
int x = a1 - 'a';
int y = b1 - 'a';
change(1,l1,r1,x,y);
}
check(1);
return 0;
}
回复
共 4 条回复,欢迎继续交流。
正在加载回复...