二分+树状数组/线段树(区间更新) HDOJ 4339 Query-白红宇

二分+树状数组/线段树(区间更新) HDOJ 4339 Query

阅读量：6933 次

发布时间：2019-06-27

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

题意：给两串字符串，操作1：替换其中一个字符串的某个位置的字符操作2：查询从p开始相等的最长连续长度

分析：树状数组可以维护一个区间内公共长度(连续)的情况，查询时用二分查找最远的端点即可。还可以用线段树去做，线段树能处理的问题很多，这题只要往右区间合并就行了。

收获：1.线段树的区间合并又做一题(虽然我写的还没AC) 2. 树状数组写起来方便又奇效！

代码1(树状数组)：

/************************************************* Author        :Running_Time* Created Time  :2015-8-26 9:46:09* File Name     :I.cpp ************************************************/#include 
     
      #include 
      
       #include 
       
        #include 
        
         #include 
         
          #include 
          
           #include 
           
            #include 
            
             #include 
             
              #include 
              
               #include 
               
                #include 
                
                 #include 
                 #include 
                  
                   #include 
                   
                    #include 
                    
                     #include 
                     
                      using namespace std;#define lson l, mid, rt << 1#define rson mid + 1, r, rt << 1 | 1typedef long long ll;const int N = 1e6 + 10;const int Q = 1e5 + 10;const int INF = 0x3f3f3f3f;const int MOD = 1e9 + 7;char s1[N], s2[N];int L;struct BIT { int c[N]; void init(void) { memset (c, 0, sizeof (c)); } void updata(int i, int x) { while (i <= L) { c[i] += x; i += (i & (-i)); } } int query(int i) { int ret = 0; while (i) { ret += c[i]; i -= (i & (-i)); } return ret; } int bsearch(int p, int l, int r) { while (l <= r) { int mid = (l + r) >> 1; if (query (mid) - query (p-1) == mid - p + 1) l = mid + 1; else r = mid - 1; } return l - p; }}bit;int main(void) { int T, cas = 0; scanf ("%d", &T); while (T--) { scanf ("%s%s", s1 + 1, s2 + 1); int q; scanf ("%d", &q); int len1 = strlen (s1 + 1), len2 = strlen (s2 + 1); L = min (len1, len2); bit.init (); for (int i=1; i<=L; ++i) { if (s1[i] == s2[i]) bit.updata (i, 1); } printf ("Case %d:\n", ++cas); while (q--) { int op; scanf ("%d", &op); if (op == 1) { int x, p; char c; scanf ("%d%d %c", &x, &p, &c); ++p; if (p > L) continue; bool same = (s1[p] == s2[p]); if (x == 1) { s1[p] = c; if (same && s1[p] != s2[p]) bit.updata (p, -1); else if (!same && s1[p] == s2[p]) bit.updata (p, 1); } else { s2[p] = c; if (same && s1[p] != s2[p]) bit.updata (p, -1); else if (!same && s1[p] == s2[p]) bit.updata (p, 1); } } else { int p; scanf ("%d", &p); ++p; if (p > L) { puts ("0"); continue; } printf ("%d\n", bit.bsearch (p, p, L)); } } } return 0;}

代码2(线段树)：

/************************************************* Author        :Running_Time* Created Time  :2015-8-26 9:46:09* File Name     :I.cpp ************************************************/#include 
     
      #include 
      
       #include 
       
        #include 
        
         #include 
         
          #include 
          
           #include 
           
            #include 
            
             #include 
             
              #include 
              
               #include 
               
                #include 
                
                 #include 
                 #include 
                  
                   #include 
                   
                    #include 
                    
                     #include 
                     
                      using namespace std;#define lson l, mid, rt << 1#define rson mid + 1, r, rt << 1 | 1typedef long long ll;const int N = 1e6 + 10;const int Q = 1e5 + 10;const int INF = 0x3f3f3f3f;const int MOD = 1e9 + 7;char s1[N], s2[N];struct ST { int sum[N<<2]; void push_up(int rt, int len) { //sum[rt<<1]表示从左子树线段左端点开始最长连续的公共的长度，如果全是公共的， if (sum[rt<<1] == len - (len >> 1)) sum[rt] = sum[rt<<1] + sum[rt<<1|1]; //合并右子树的线段长度 else sum[rt] = sum[rt<<1]; } void build(int l, int r, int rt) { if (l == r) { sum[rt] = s1[l] == s2[r] ? 1 : 0; return ; } int mid = (l + r) >> 1; build (lson); build (rson); push_up (rt, r - l + 1); } void updata(int p, int c, int l, int r, int rt) { if (l == r) { sum[rt] = c; return ; } int mid = (l + r) >> 1; if (p <= mid) updata (p, c, lson); else updata (p, c, rson); push_up (rt, r - l + 1); } int query(int p, int l, int r, int rt) { if (l == r) return sum[rt]; int mid = (l + r) >> 1; if (p <= mid) { int ret = query (p, lson); if (p + ret - 1 == mid) return ret + sum[rt<<1|1]; else return ret; } else return query (p, rson); }}st;int main(void) { int T, cas = 0; scanf ("%d", &T); while (T--) { scanf ("%s%s", s1 + 1, s2 + 1); int q; scanf ("%d", &q); int len1 = strlen (s1 + 1), len2 = strlen (s2 + 1); int mn = min (len1, len2); st.build (1, mn, 1); printf ("Case %d:\n", ++cas); while (q--) { int op; scanf ("%d", &op); if (op == 1) { int x, p; char c; scanf ("%d%d %c", &x, &p, &c); ++p; if (p > mn) continue; //特殊情况特判 if (x == 1) { s1[p] = c; } else { s2[p] = c; } st.updata (p, (s1[p] == s2[p]), 1, mn, 1); } else { int p; scanf ("%d", &p); ++p; if (p > mn) { //特殊情况特判 puts ("0"); continue; } printf ("%d\n", st.query (p, 1, mn, 1)); } } } return 0;}

代码3(unAC)：

/************************************************* Author        :Running_Time* Created Time  :2015-8-26 9:46:09* File Name     :I.cpp ************************************************/#include 
     
      #include 
      
       #include 
       
        #include 
        
         #include 
         
          #include 
          
           #include 
           
            #include 
            
             #include 
             
              #include 
              
               #include 
               
                #include 
                
                 #include 
                 #include 
                  
                   #include 
                   
                    #include 
                    
                     #include 
                     
                      using namespace std;#define lson l, mid, rt << 1#define rson mid + 1, r, rt << 1 | 1typedef long long ll;const int N = 1e6 + 10;const int Q = 1e5 + 10;const int INF = 0x3f3f3f3f;const int MOD = 1e9 + 7;char s1[N], s2[N];struct ST { int sum[N<<2], lsum[N<<2], rsum[N<<2]; void push_up(int rt, int len) { lsum[rt] = lsum[rt<<1]; rsum[rt] = rsum[rt<<1|1]; sum[rt] = max (sum[rt<<1], sum[rt<<1|1]); if (lsum[rt] == len - (len >> 1)) lsum[rt] += lsum[rt<<1|1]; if (rsum[rt] == len >> 1) rsum[rt] += rsum[rt<<1]; sum[rt] = max (rsum[rt<<1] + lsum[rt<<1|1], max (sum[rt<<1], sum[rt<<1|1])); } void build(int l, int r, int rt) { if (l == r) { sum[rt] = lsum[rt] = rsum[rt] = s1[l] == s2[r] ? 1 : 0; return ; } int mid = (l + r) >> 1; build (lson); build (rson); push_up (rt, r - l + 1); } void updata(int p, int c, int l, int r, int rt) { if (l == r) { sum[rt] = lsum[rt] = rsum[rt] = c; return ; } int mid = (l + r) >> 1; if (p <= mid) updata (p, c, lson); else updata (p, c, rson); push_up (rt, r - l + 1); } int query(int p, int l, int r, int rt) { if (l == r) return sum[rt]; int mid = (l + r) >> 1; if (p <= mid) { if (p + rsum[rt<<1] - 1 >= mid) return mid - p + 1 + query (p, rson); else return query (p, lson); } else return query (p, lson); }}st;int main(void) { int T, cas = 0; scanf ("%d", &T); while (T--) { scanf ("%s%s", s1 + 1, s2 + 1); int q; scanf ("%d", &q); int len1 = strlen (s1 + 1), len2 = strlen (s2 + 1); int mn = min (len1, len2); st.build (1, mn, 1); printf ("Case %d:\n", ++cas); while (q--) { int op; scanf ("%d", &op); if (op == 1) { int x, p; char c; scanf ("%d%d %c", &x, &p, &c); if (p + 1 > mn) continue; if (x == 1) { s1[p+1] = c; } else { s2[p+1] = c; } st.updata (p+1, (s1[p+1] == s2[p+1]), 1, mn, 1); } else { int p; scanf ("%d", &p); if (p + 1 > mn) { puts ("0"); continue; } printf ("%d\n", st.query (p + 1, 1, mn, 1)); } } } return 0;}