Codeforces 899F - Letters Removing
思路：考虑一下怎么找到输入的l和r在原来串中的位置，我们想到用前缀和来找，一开始所有位置都为1,删掉后为0，那么前缀和为l的位置就是l的位置，前缀和为r的位置就是r的位置。
那么用树状数组来维护一下前缀和，再用二分查找来找到位置就可以了。然后找到的区间可能很大，然而我们要删的只有一种字符，把每种字符的位置分开来保存来操作，可以用set也可以用vector。
代码1（set版，187ms）：
#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define pb push_back
#define mem(a,b) memset(a,b,sizeof(a)) const int N=2e5+;
int bit[N];
bool vis[N];
int n;
set<int>pos[];
void add(int x,int a)
{
while(x<=n)
{
bit[x]+=a;
x+=x&(-x);
}
}
int sum(int x)
{
int ans=;
while(x)
{
ans+=bit[x];
x-=x&(-x);
}
return ans;
}
int search(int x)
{
int l=,r=n,m=(l+r)>>;
while(l<r)
{
if(sum(m)>=x)r=m;
else l=m+;
m=(l+r)>>;
}
return m;
}
int main()
{
ios::sync_with_stdio(false);
cin.tie();
int m,l,r;
string s;
char c;
cin>>n>>m>>s;
for(int i=;i<=n;i++)add(i,),pos[s[i-]].insert(i);
while(m--)
{
cin>>l>>r>>c;
l=search(l);
r=search(r);
set<int>::iterator it=pos[c].lower_bound(l);
while(it!=pos[c].end())
{
if(*it>r)break;
add(*it,-);
pos[c].erase(it++);
}
}
for(int i=;i<;i++)
{
for(auto x:pos[i])vis[x]=true;
}
for(int i=;i<=n;i++)if(vis[i])putchar(s[i-]);
puts("");
return ;
}
代码2（vector版，155ms）：
#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define pb push_back
#define mem(a,b) memset(a,b,sizeof(a)) const int N=2e5+;
int bit[N];
bool vis[N];
int n;
vector<int>pos[];
void add(int x,int a)
{
while(x<=n)
{
bit[x]+=a;
x+=x&(-x);
}
}
int sum(int x)
{
int ans=;
while(x)
{
ans+=bit[x];
x-=x&(-x);
}
return ans;
}
int search(int x)
{
int l=,r=n,m=(l+r)>>;
while(l<r)
{
if(sum(m)>=x)r=m;
else l=m+;
m=(l+r)>>;
}
return m;
}
int main()
{
ios::sync_with_stdio(false);
cin.tie();
int m,l,r;
string s;
char c;
cin>>n>>m>>s;
for(int i=;i<=n;i++)add(i,),pos[s[i-]].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<pos[c].size();i++)
{
if(pos[c][i]>r)break;
if(!vis[pos[c][i]])add(pos[c][i],-),vis[pos[c][i]]=true;
}
}
for(int i=;i<=n;i++)if(!vis[i])putchar(s[i-]);
puts("");
return ;
}