【Codeforces】159C String Manipulation 1.0

 1 #include<cstdio>

 2 #include<cstring>

 3 #define MAXN 200010

 4 char s[MAXN];

 5 int tree[26][MAXN<<2];

 6 bool vis[MAXN];

 7 inline void PushUp(int t,int rt)

 8 {

 9     tree[t][rt]=tree[t][rt<<1]+tree[t][rt<<1|1];

10 }

11 void Update(int t,int x,int L,int R,int rt)

12 {

13     if(L==R)

14         tree[t][rt]=1;

15     else

16     {

17         int mid=(L+R)>>1;

18         if(mid>=x)

19             Update(t,x,L,mid,rt<<1);

20         else

21             Update(t,x,mid+1,R,rt<<1|1);

22         PushUp(t,rt);

23     }

24 }

25 int Find(int t,int x,int L,int R,int rt)

26 {

27     if(L==R)

28     {

29         tree[t][rt]=0;

30         return L;

31     }

32     int ans,mid=(L+R)>>1;

33     if(tree[t][rt<<1]>=x)

34         ans=Find(t,x,L,mid,rt<<1);

35     else

36     {

37         x-=tree[t][rt<<1];

38         ans=Find(t,x,mid+1,R,rt<<1|1);

39     }

40     PushUp(t,rt);

41     return ans;

42 }

43 int main()

44 {

45     char ch;

46     int k,i,j,q,len,n;

47     while(~scanf("%d %s%d",&k,s+1,&q))

48     {

49         memset(vis,false,sizeof(vis));

50         memset(tree,0,sizeof(tree));

51         len=strlen(s+1);

52         n=len*k;

53         for(j=len+1;--k;)

54         {

55             for(i=1;i<=len;i++)

56                 s[j++]=s[i];

57         }

58         s[j]=0;

59         for(i=1;s[i];i++)

60             Update(s[i]-'a',i,1,n,1);

61         while(q--)

62         {

63             scanf("%d %c",&i,&ch);

64             k=Find(ch-'a',i,1,n,1);

65             vis[k]=true;

66         }

67         for(i=1;s[i];i++)

68         {

69             if(!vis[i])

70                 putchar(s[i]);

71         }

72         putchar('
');

73     }

74     return 0;

75 }