思路：考虑一下怎么找到输入的l和r在原来串中的位置，我们想到用前缀和来找，一开始所有位置都为1,删掉后为0，那么前缀和为l的位置就是l的位置，前缀和为r的位置就是r的位置。

那么用树状数组来维护一下前缀和，再用二分查找来找到位置就可以了。然后找到的区间可能很大，然而我们要删的只有一种字符，把每种字符的位置分开来保存来操作，可以用set也可以用vector。

代码1（set版，187ms）：

#include
     
      using namespace std;#define ll long long#define pb push_back#define mem(a,b) memset(a,b,sizeof(a))const int N=2e5+5;int bit[N];bool vis[N];int n;set
      
       pos[123];void add(int x,int a){    while(x<=n)    {        bit[x]+=a;        x+=x&(-x);    }}int sum(int x){    int ans=0;    while(x)    {        ans+=bit[x];        x-=x&(-x);    }    return ans;}int search(int x){    int l=1,r=n,m=(l+r)>>1;    while(l
       
        =x)r=m;        else l=m+1;        m=(l+r)>>1;    }    return m;}int main(){    ios::sync_with_stdio(false);    cin.tie(0);    int m,l,r;    string s;    char c;    cin>>n>>m>>s;    for(int i=1;i<=n;i++)add(i,1),pos[s[i-1]].insert(i);    while(m--)    {        cin>>l>>r>>c;        l=search(l);        r=search(r);        set
        
         ::iterator it=pos[c].lower_bound(l);        while(it!=pos[c].end())        {            if(*it>r)break;            add(*it,-1);            pos[c].erase(it++);        }    }    for(int i=0;i<123;i++)    {        for(auto x:pos[i])vis[x]=true;    }    for(int i=1;i<=n;i++)if(vis[i])putchar(s[i-1]);    puts("");    return 0;}
        
       
      
     

代码2（vector版，155ms）：

#include
     
      using namespace std;#define ll long long#define pb push_back#define mem(a,b) memset(a,b,sizeof(a))const int N=2e5+5;int bit[N];bool vis[N];int n;vector
      
       pos[123];void add(int x,int a){    while(x<=n)    {        bit[x]+=a;        x+=x&(-x);    }}int sum(int x){    int ans=0;    while(x)    {        ans+=bit[x];        x-=x&(-x);    }    return ans;}int search(int x){    int l=1,r=n,m=(l+r)>>1;    while(l
       
        =x)r=m;        else l=m+1;        m=(l+r)>>1;    }    return m;}int main(){    ios::sync_with_stdio(false);    cin.tie(0);    int m,l,r;    string s;    char c;    cin>>n>>m>>s;    for(int i=1;i<=n;i++)add(i,1),pos[s[i-1]].pb(i);    while(m--)    {        cin>>l>>r>>c;        l=search(l);        r=search(r);        int it=lower_bound(pos[c].begin(),pos[c].end(),l)-pos[c].begin();        for(int i=it;i
        
         r)break;            if(!vis[pos[c][i]])add(pos[c][i],-1),vis[pos[c][i]]=true;        }    }    for(int i=1;i<=n;i++)if(!vis[i])putchar(s[i-1]);    puts("");    return 0;}