HDU 4339 Query

线段树
  1 #include <cstdio>
  2 #include <cstring>
  3 #include <cstdlib>
  4 #include <algorithm>
  5 
  6 #define lson l, m, rt << 1
  7 #define rson m + 1, r, rt << 1 | 1
  8 
  9 using namespace std;
 10 
 11 const int MAXN = 1000010;
 12 
 13 char str1[MAXN];
 14 char str2[MAXN];
 15 bool flag[ MAXN << 2 ];
 16 int len1, len2;
 17 
 18 void PushUp( int rt, int l )
 19 {
 20     int lc = rt << 1;
 21     int rc = rt << 1 | 1;
 22     flag[rt] = flag[lc] && flag[rc];
 23     return;
 24 }
 25 
 26 void Update( int L, int num, char c, int l, int r, int rt )
 27 {
 28     if ( L == l && r == L )
 29     {
 30         if ( num == 1 ) str1[L] = c;
 31         else str2[L] = c;
 32         if ( str1[L] == str2[L] ) flag[rt] = true;
 33         else flag[rt] = false;
 34 
 35         return;
 36     }
 37 
 38     int m = ( l + r ) >> 1;
 39     if ( L <= m ) Update( L, num, c, lson );
 40     else Update( L, num, c, rson );
 41 
 42     PushUp( rt, l );
 43     return;
 44 }
 45 
 46 void build( int l, int r, int rt )
 47 {
 48     if ( l == r )
 49     {
 50         if ( str1[l] == str2[l] )
 51             flag[rt] = true;
 52         else
 53             flag[rt] = false;
 54         return;
 55     }
 56     int m = ( l + r ) >> 1;
 57     build( lson );
 58     build( rson );
 59     PushUp( rt, l );
 60     return;
 61 }
 62 
 63 int query( int L, int l, int r, int rt )
 64 {
 65     if ( flag[rt] )
 66     {
 67         return r;
 68     }
 69     if ( l == r )
 70     {
 71         return r - 1;
 72     }
 73     int m = ( l + r ) >> 1;
 74     if ( L <= m )
 75     {
 76         int temp = query( L, lson );
 77         if ( temp == m ) return query( m + 1, rson );
 78         else return temp;
 79     }
 80     else return query( L, rson );
 81 }
 82 
 83 int main()
 84 {
 85     int T;
 86     int cas = 0;
 87     scanf( "%d", &T );
 88     while ( T-- )
 89     {
 90         scanf( "%s", str1 );
 91         scanf( "%s", str2 );
 92 
 93         len1 = strlen( str1 );
 94         len2 = strlen( str2 );
 95 
 96         int len = min( len1, len2 );
 97         build( 0, len - 1, 1 );
 98 
 99         int Q;
100         scanf( "%d", &Q );
101         printf( "Case %d:\n", ++cas );
102         while ( Q-- )
103         {
104             int op;
105             scanf( "%d", &op );
106             char st[10];
107             if ( op == 1 )
108             {
109                 int a, i;
110                 scanf( "%d%d%s", &a, &i, st );
111                 if ( i >= len ) continue;
112                 Update( i, a, st[0], 0, len - 1, 1 );
113             }
114             else
115             {
116                 int i;
117                 scanf( "%d", &i );
118                 printf( "%d\n", query( i, 0, len - 1, 1 ) - i + 1 );
119             }
120         }
121     }
122     return 0;
123 }