HDU 4046 树状数组-白红宇

HDU 4046 树状数组

阅读量：2439 次

发布时间：2019-05-10

本文共 3077 字，大约阅读时间需要 10 分钟。

/*******************************************************************************   WA了N多次。。。结果是忘记初始化st数组了。。。悲剧得1B。。。   解法就是考虑修改位置id的字符，观察左右"wbw"是否被更改，如果被更改了，那么就更新下，这个地方要特别小心。。。具体可以见代码～*******************************************************************************/#include 
   
    #include 
    
     #include 
     
      #include 
      
       #include 
       
        #include 
        
         #include 
         
          #include 
          
           #include 
           
            #include 
            
             #include 
             
              #include 
              
               #include 
               
                #include 
                
                 #include 
                 
                  #include 
                  
                   #include 
                   
                    #include 
                    
                     #include 
                     
                      #include 
                      
                       #include 
                       
                        #include 
                        
                         #include 
                         #include 
                          
                           using namespace std;#define LOWBIT(x) ( (x) & ( (x) ^ ( (x) - 1 ) ) )#define CLR(x, k) memset((x), (k), sizeof(x))#define CPY(t, s) memcpy((t), (s), sizeof(s))#define SC(t, s) static_cast
                           
                            (s)#define LEN(s) static_cast
                            
                             ( strlen((s)) )#define SZ(s) static_cast
                             
                              ( (s).size() )typedef double LF;typedef __int64 LL; //VCtypedef unsigned __int64 ULL;typedef pair
                              
                                PII;typedef pair
                               
                                 PLL;typedef pair
                                
                                  PDD;typedef vector
                                 
                                   VI;typedef vector
                                  
                                    VC;typedef vector
                                   
                                     VF;typedef vector
                                    
                                      VS;template 
                                     
                                      T sqa(const T & x){ return x * x;}template 
                                      
                                       T gcd(T a, T b){ if (!a || !b) { return max(a, b); } T t; while (t = a % b) { a = b; b = t; } return b;};const int INF_INT = 0x3f3f3f3f;const LL INF_LL = 0x7fffffffffffffffLL; //15fconst double oo = 10e9;const double eps = 10e-7;const double PI = acos(-1.0);#define ONLINE_JUDGEconst int MAXN = 50004 << 1;int test, n, m;char ch[MAXN];int st[MAXN];bool judge(int ind) //判断ind是为"wbw"中的b位置{ if (1 <= ind && ind < n - 1) //显然ind=0和ind=n-1的时候是不存在"wbw"的 { if ('b' == ch[ind] && 'w' == ch[ind - 1] && 'w' == ch[ind + 1]) { return true; } } return false;}void update(int x, int inc){ for (int i = x; i < MAXN; i += LOWBIT(i)) { st[i] += inc; } return ;}int query(int x){ int res = 0; for (int i = x; i > 0; i -= LOWBIT(i)) { res += st[i]; } return res;}void ace(){ int cas = 1; int op, x, y; char cc[4]; for (scanf("%d", &test); test--; ++cas) { scanf("%d %d%*c%s", &n, &m, ch); //printf("ch: %s\n", ch); CLR(st, 0); for (int i = 1; i < n - 1; ++i) //超级杯具的初始化。。。 { if (judge(i)) { update(i, 1); } } printf("Case %d:\n", cas); while (m--) { scanf("%d %d", &op, &x); if (0 == op) { scanf("%d", &y); if (x > y) { swap(x, y); } if (y - x + 1 < 3) { puts("0"); continue ; } printf("%d\n", query(y - 1) - query(x)); } else { scanf("%s", cc); if (cc[0] == ch[x]) { continue ; } if ('w' == cc[0]) //以下全是坑 { if (judge(x)) { update(x, -1); } ch[x] = 'w'; if (judge(x - 1)) { update(x - 1, 1); } if (judge(x + 1)) { update(x + 1, 1); } } else { if (judge(x - 1)) { update(x - 1, -1); } if (judge(x + 1)) { update(x + 1, -1); } ch[x] = 'b'; if (judge(x)) { update(x, 1); } } } } } return ;}int main(){#ifndef ONLINE_JUDGE freopen("in.txt", "r", stdin); freopen("out.txt", "w", stdout);#endif ace(); return 0;}/*******************************************************************************Test Data...45 2bwbwb0 0 40 1 35 5wbwbw0 0 40 0 20 2 41 2 b0 0 411 11wbwbbwbwbwb0 0 100 0 10 0 20 1 20 1 30 1 50 1 60 1 70 2 60 2 70 2 109 10bwbbwbwbw0 2 60 2 50 2 7*******************************************************************************/