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

xingke233 / 2024-11-09 / 原文

题目大意

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

输入的第一行包含一个字符串 $s$。

第二行包含一个整数 $m$。

接下来 $m$ 行，每行包含 $4$ 个参数 $l_i,r_i,x_i,y_i$，相邻两个参数之间用一个空格分隔，其中 $l_i,r_i$ 为整数，$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$ 的长度。

思路

因为不会线段树分裂合并只能用普通做法。

按照题目开 $26$ 棵权值线段树。

对于修改操作，我们遍历要修改的 $x$ 线段树。

如果当前区间全为 $x$ 那么直接在 $y$ 那颗树上修改并打上覆盖标记。

    if(ll>=l&&rr<=r&&sum(x,p)==rr-ll+1){
        sum(y,p)=sum(x,p);
        sum(x,p)=0;
        chg(y,p)=1;chg(x,p)=0;
        return ;
    }

输出答案时，直接遍历 $26$ 棵线段树即可。

注意线段树的空间。

Code

#include<bits/stdc++.h>
using namespace std;
#define LL int
#define Ld long double
#define sum(k,p) tree[k][p].sum
#define chg(k,p) tree[k][p].chg
const int N = 100005,M=100005;

LL m,l,r,n;
char ch[N],x,y;
struct Segment_tree{
    LL sum,chg;
}tree[26][N*4];

void build(LL p,LL l,LL r){
    for(int i=0;i<26;i++)chg(i,p)=-1;
    if(l==r){
        sum(ch[l]-'a',p)=1;
        return ;
    }
    LL mid=(l+r)>>1;
    build(p<<1,l,mid);
    build(p<<1|1,mid+1,r);
    for(int i=0;i<26;i++) sum(i,p)=sum(i,p<<1)+sum(i,p<<1|1);
    return ;
}

void pushdown(LL p,LL k,LL l,LL r,LL mid){
    if(chg(k,p)==-1) return ;
    sum(k,p<<1)=(mid-l+1)*chg(k,p);
    sum(k,p<<1|1)=(r-mid)*chg(k,p);
    chg(k,p<<1)=chg(k,p<<1|1)=chg(k,p);
    chg(k,p)=-1;
    return ;
}

void pushup(LL p,LL k){
    sum(k,p)=sum(k,p<<1)+sum(k,p<<1|1);
    return ;
}

void change(LL p,LL l,LL r,LL x,LL y,LL ll,LL rr){
    if(!sum(x,p)) return ;
    if(ll>=l&&rr<=r&&sum(x,p)==rr-ll+1){
        sum(y,p)=sum(x,p);
        sum(x,p)=0;
        chg(y,p)=1;chg(x,p)=0;
        return ;
    }
    LL mid=(ll+rr)>>1;
    pushdown(p,x,ll,rr,mid);
    pushdown(p,y,ll,rr,mid);
    if(l<=mid) change(p<<1,l,r,x,y,ll,mid);
    if(r>mid) change(p<<1|1,l,r,x,y,mid+1,rr);
    pushup(p,x);
    pushup(p,y);
    return ;
}

void out(LL p,LL l,LL r){
    if(l==r){
        for(int i=0;i<26;i++){
            if(sum(i,p)!=0){
                cout<<(char)(i+97);
                break;
            }
        }
        return ;
    }
    LL mid=(l+r)>>1;
    for(int i=0;i<26;i++) pushdown(p,i,l,r,mid);
    out(p<<1,l,mid);
    out(p<<1|1,mid+1,r);
    return ;
}

signed main(){
    cin>>ch+1;
    LL len=strlen(ch+1);
    build(1,1,len);
    cin>>n;
    for(int i=1;i<=n;i++){
        cin>>l>>r>>x>>y;
        change(1,l,r,x-'a',y-'a',1,len);
    }
    out(1,1,len);
    return 0;
}