HDU4339 Query（Dec. 11th, 2018）

树状数组

题目描述
题意：给定两个字符串$s_1$，$s_2$和$q$个操作，分别是：
1. 输入$a$，$i$，$x$，把$s_a$的第$i$个字符改为$x$。
2. 输入$i$，求两个字符串从第$i$位开始最长公共子串。

思路（来自题解）：
1. 用树状数组维护字符串，不同为1，同为0。
2. 二分查找坐标最大的能够使$que(ans)-que(i)==0$的$ans$。

代码：

// La Lune
#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>
#define wt(x) (x & -x)
#define rev(x) (x == 1 ? 2 : 1)
using namespace std;
const int N = 1e6 + 5;
int n, c[N]; char s[3][N];
inline void add(int pos, int x) {for(int i = pos; i <= n; i += wt(i)) c[i] += x;}
inline int que(int pos) {int res = 0; for(int i = pos; i >= 1; i -= wt(i)) res += c[i]; return res;}
int main(){
    int T, cnt = 0; scanf("%d", &T);
    while(T--){
        memset(c, 0, sizeof(c));
        scanf("%s\n%s", s[1] + 1, s[2] + 1);
        n = max(strlen(s[1] + 1), strlen(s[2] + 1));
        for(int i = 1; i <= n; i++) if(s[1][i] != s[2][i]) add(i, 1);
        printf("Case %d:\n", ++cnt);
        int q; scanf("%d", &q);
        for(int i = 1; i <= q; i++){
            int ctrl, pos;
            scanf("%d", &ctrl);
            if(ctrl == 1){
                int str; char mv;
                scanf("%d %d %c\n", &str, &pos, &mv); pos++;
                if(s[str][pos] == mv) continue;
                else if(s[str][pos] == s[rev(str)][pos]) add(pos, 1);
                else if(s[rev(str)][pos] == mv) add(pos, -1);
                s[str][pos] = mv;
            }
            else{
                scanf("%d", &pos); pos++;
                int l = pos - 1, r = n, ans = 0, ref = que(pos - 1);
                while(l <= r){
                    int mid = l + r >> 1;
                    if(que(mid) - ref == 0) ans = mid, l = mid + 1;
                    else r = mid - 1;
                }
                printf("%d\n", ans - pos + 1);
            }
        }
    }
    return 0;
}

反思