CF899F. Letters Removing

给一个字符串支持以下操作：区间删除某个特定字符。最后输出字符串。n,m<=200000。

这题我居然不会可以回家了。。

首先，单点删除，选个平衡树比如set。

然后，他给的下标是会随删除操作变化的，需要查“存在于字符串中的第K个是谁”来找左右端点，一个树状数组搞定。

树状数组找出题目给的x,y在初始串中的下标L,R，对每个字符开一个set存它的所有出现位置，把这个set里在L,R间的位置去掉，去掉的同时把树状数组里的对应位置-1，即可。

 #include<stdio.h>

 #include<string.h>

 #include<algorithm>

 #include<stdlib.h>

 #include<set>

 #include<math.h>

 //#include<iostream>

 using namespace std;

 int n,m;

 #define maxn 200011

 char a[maxn];

 set<int> s[];

 #define IT set<int>::iterator

 struct BIT

 {

     int a[maxn];

     BIT() {memset(a,,sizeof(a));}

     void add(int x,int v) {for (;x<=n;x+=x&-x) a[x]+=v;}

     int query(int x) {int ans=;for (;x;x-=x&-x) ans+=a[x];return ans;}

     int find(int x)

     {

         int now=,tot=;

         for (int j=;j>=;j--)

         {

             now+=<<j;

             if (now<=n && a[now]+tot<x) tot+=a[now];

             else now-=<<j;

         }

         return now+;

     }

 }t;

 int main()

 {

     scanf("%d%d",&n,&m);

     scanf("%s",a+);

     for (int i=;i<=n;i++) s[a[i]].insert(i);

     for (int i=;i<=n;i++) t.a[i]=i&-i;

     int x,y;char id[];

     while (m--)

     {

         scanf("%d%d%s",&x,&y,id);

         int L=t.find(x),R=t.find(y);

         IT it=s[id[]].lower_bound(L);

         for (;it!=s[id[]].end() && *it<=R;)

         {

             IT tmp=it; it++;

             t.add(*tmp,-);

             s[id[]].erase(tmp);

         }

     }

     for (int i=;i<=n;i++) if (t.query(i)-t.query(i-)) putchar(a[i]);

     return ;

 }

巴特西

CF899F. Letters Removing

最新文章

热门文章