社区讨论

悬赏关注线段树求调!

学术版参与者 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 条回复,欢迎继续交流。

正在加载回复...