Codeforces 899F Letters Removing 线段树/树状数组

虽然每次给一个区间，但是可以看作在区间内进行数个点操作，同样数列下标是动态变化的，如果我们将每个字符出现看作1，被删除看作0，则通过统计前缀和就能轻松计算出两个端点的位置了！这正是经典的树状数组操作

需要注意的是，即使每次找到了两个端点，如果只是朴素总左到右遍历会TLE，所以可以给每个字符开一个set，每个set储存字符出现的位置。

  1 #include <iostream>
  2 #include <cstdio>
  3 #include <cstring>
  4 #include <string>
  5 #include <map>
  6 #include <set>
  7 #include <vector>
  8 #include <algorithm>
  9 #pragma warning ( disable : 4996 )
 10 using namespace std;
 11 
 12 int Max( int a, int b ) { return a>b?a:b; }
 13 int Min( int a, int b ) { return a>b?b:a; }
 14 int lowbit( int x )        { return x&-x; }
 15 
 16 const int inf = 0x3f3f3f3f;
 17 const int maxn = 2e5+5;
 18 
 19 set<int> pos[65];
 20 set<int>::iterator it, it2;
 21 char str[maxn];
 22 int istr[maxn];
 23 bool isdel[maxn];
 24 
 25 int len, q;
 26 
 27 int getI( char c )
 28 {
 29     if( c >= 'a' && c <= 'z' ) return c-'a';
 30     if( c >= 'A' && c <= 'Z' ) return c-'A'+26;
 31     if( c >= '0' && c <= '9' ) return c-'0'+52;
 32 }
 33 
 34 int sum( int x )
 35 {
 36     int ret = 0;
 37     while( x > 0 )
 38         {    ret += istr[x]; x -= lowbit(x); }
 39     return ret;
 40 }
 41 
 42 void add( int x, int d )
 43 {
 44     while( x <= len )
 45         { istr[x] += d; x += lowbit(x); }
 46 }
 47 
 48 int find( int s )
 49 {
 50     int mid, lhs = 1, rhs = len;
 51     int tmp;
 52     while ( lhs <= rhs )
 53     {
 54         mid = (lhs+rhs)>>1;
 55         tmp = sum(mid);
 56         if ( tmp >= s ) rhs = mid-1;
 57         else lhs = mid+1;
 58     }
 59     return lhs;
 60 }
 61 
 62 void change( int l, int r, char c )
 63 {
 64     int p = getI(c);
 65     it = pos[p].lower_bound(l);
 66     while ( it!=pos[p].end() && *it<=r )
 67     {
 68         isdel[(*it)] = true;
 69         add((*it), -1);
 70         it2 = it; it++;
 71         pos[p].erase(it2);
 72     }
 73 }
 74 
 75 int main()
 76 {
 77     cin >> len >> q;
 78     scanf("%s", str+1);
 79 
 80     for ( int i = 1; i <= len; i++ )
 81     {
 82         add(i,1);
 83         int p = getI(str[i]);
 84         pos[p].insert(i);
 85     }
 86 
 87     int x, y;
 88     char c;
 89     for ( int i = 1; i <= q; i++ )
 90     {
 91         scanf( "%d %d %c", &x, &y, &c );
 92         x = find(x); y = find(y);
 93         change( x, y, c );
 94     }
 95 
 96     for( int i = 1; i <= len; i++ )
 97         if( !isdel[i] )
 98             printf( "%c", str[i] );
 99     
100     printf("
");
101     return 0;
102 }

View Code

我们看到区间操作，自然就会想到线段树，但是数列下标是动态变换的，乍一看似乎线段树就没有用武之地了。实际仔细想想，线段树也可以动态统计从哪个区间开始操作，相比普通线段树只是在每次操作前要计算新的下标到哪了，实际上每个节点管辖的范围是始终不变的，变的只是范围内字符的个数size，每次操作前通过这个size找到对应的左端点和右端点就行了。

  1 //线段树
  2 #include <iostream>
  3 #include <cstdio>
  4 #include <cstring>
  5 #include <string>
  6 #include <map>
  7 #include <vector>
  8 #include <algorithm>
  9 #pragma warning ( disable : 4996 )
 10 using namespace std;
 11 
 12 int Max( int a, int b ) { return a>b?a:b; }
 13 int Min( int a, int b ) { return a>b?b:a; }
 14 
 15 const int inf = 0x3f3f3f3f;
 16 const int maxn = 2e5+2;
 17 
 18 struct tree {
 19     int size, lhs, rhs;
 20     int clu[62];
 21 }t[maxn<<2];
 22 char str[maxn];
 23 
 24 int getI( char c )
 25 {
 26     if( c >= 'a' && c <= 'z' ) return c-'a';
 27     if( c >= 'A' && c <= 'Z' ) return c-'A'+26;
 28     if( c >= '0' && c <= '9' ) return c-'0'+52;
 29 }
 30 
 31 char getC( int i )
 32 {
 33     if( i >= 0 && i <= 25 )  return 'a'+i;
 34     if( i >= 26 && i <= 51 ) return 'A'+i-26;
 35     if( i >= 52 && i <= 61 ) return '0'+i-52;
 36 }
 37 
 38 void pushUp( int index )
 39 {
 40     t[index].size = t[index<<1].size + t[index<<1|1].size;
 41     for ( int i = 0; i < 62; i++ )
 42         t[index].clu[i] = t[index<<1].clu[i] + t[index<<1|1].clu[i];
 43 }
 44 
 45 void build( int l, int r, int index )
 46 {
 47     t[index].lhs = l; t[index].rhs = r;
 48     if( l == r )
 49         { t[index].size = 1; t[index].clu[getI(str[l-1])] = 1; return; }
 50     int mid = (l+r)>>1;
 51     build(l, mid, index<<1);
 52     build(mid+1, r, index<<1|1);
 53     pushUp(index);
 54 }
 55 
 56 int find( int index, int x )
 57 {
 58     int l = t[index].lhs, r = t[index].rhs;
 59     if( l == r ) return l;
 60     if( t[index<<1].size >= x ) return find( index<<1, x );
 61     else return find( index<<1|1, x-t[index<<1].size );
 62 }
 63 
 64 void change( int index, int l, int r, int x ) 
 65 {
 66     int L = t[index].lhs, R = t[index].rhs;
 67     if ( r < L || l > R ) return;
 68     if ( !t[index].clu[x] ) return;
 69     if ( L == R ) { t[index].size--; t[index].clu[x]--; return; }
 70     change( index<<1, l, r, x );
 71     change( index<<1|1, l, r, x );
 72     t[index].size = t[index<<1].size + t[index<<1|1].size;
 73     t[index].clu[x] = t[index<<1].clu[x] + t[index<<1|1].clu[x];
 74 }
 75 
 76 void print( int i )
 77 {
 78     int L=t[i].lhs,R=t[i].rhs;
 79     if ( L==R )
 80     {
 81         for ( int j = 0; j < 62; j++ )
 82             if ( t[i].clu[j] ) printf("%c",getC(j));
 83         return;
 84     }
 85     print(i<<1);
 86     print(i<<1|1);
 87 
 88 }
 89 
 90 int main()
 91 {
 92     int len, q;
 93     cin >> len >> q;
 94     scanf("%s", str);
 95     build(1, len, 1);
 96 
 97     int x, y;
 98     char c;
 99     for ( int i = 1; i <= q; i++ )
100     {
101         scanf( "%d %d %c", &x, &y, &c );
102         int l = find( 1, x );
103         int r = find( 1, y );
104         change( 1, l, r, getI(c) );
105     }
106     print(1);
107     printf("
");
108     return 0;
109 }

View Code