学步园

题目链接：http://acm.hdu.edu.cn/showproblem.php?pid=4339

代码风格：http://www.notonlysuccess.com/index.php/segment-tree-complete/

题目大意：操作说明：2 a——两个字符串在a位置后面最多有几个字符完全相同；1 a b c 把第a个字符串的第b个字母改成c

算法：线段树 区间合并

思路：字符相等的位置记录1，不相等记录0，每个节点记录 左边连续相等lsum 和 右边连续相等rsum

#include<cstdio>
#include<cstring>
using namespace std;

#define lson l, m, rt << 1
#define rson m+1, r, rt << 1 | 1
#define mid int m = (l + r) >> 1
const int Max = 1000005;

char str[Max], str1[Max];
int lsum[Max << 2], rsum[Max << 2];

int maxn(int a, int b)
{
    return a > b ? a : b;
}

void PushUp(int rt, int m)
{
    lsum[rt] = lsum[rt << 1];
    rsum[rt] = rsum[rt << 1 | 1];
    if(lsum[rt] == m - (m >> 1))
        lsum[rt] += lsum[rt << 1 | 1];
    if(rsum[rt] == m >> 1)
        rsum[rt] += rsum[rt << 1];
}

void build(int l, int r, int rt)
{
    if(l == r)
    {
        lsum[rt] = rsum[rt] = ((str[l] == str1[l]) ? 1 : 0);
        return ;
    }
    mid;
    build(lson);
    build(rson);
    PushUp( rt, r-l+1);
}

void update(int k, int l, int r, int rt)
{
    if(l == r)
    {
        lsum[rt] = rsum[rt] = ((str[l] == str1[l]) ? 1 : 0);
        return ;
    }
    mid ;
    if(k <= m)
        update(k, lson);
    else update(k, rson);
    PushUp( rt, r-l+1);
}

int query(int k, int l, int r, int rt)
{
    if(l == r)
    {
        return l+1;
    }
    mid;
    if(k <= m)
    {
        if( rsum[rt << 1] >= m-k)
            return m + lsum[rt << 1 | 1]+1;
        else return query(k, lson);
    }
    else
        return query(k, rson);
}

int main()
{
    //freopen("input.txt", "r", stdin);
    //freopen("output.txt", "w", stdout);
    int T;
    scanf("%d", &T);
    int icase = 1;
    while(T --)
    {
        memset(str, 0, sizeof(str));
        memset(str1, 0, sizeof(str));
        memset(rsum, 0, sizeof(rsum));
        memset(lsum, 0, sizeof(lsum));
        printf("Case %d:\n", icase ++);
        scanf("%s", str);
        scanf("%s", str1);
        int num;
        int n = strlen(str);
        int xn = strlen(str1);
        n = maxn(n, xn);
        build(0, n-1, 1);
        scanf("%d", &num);
        while(num --)
        {
            int op;
            int a, b;
            char c[3];
            scanf("%d", &op);
            if(op == 2)
            {
                scanf("%d", &a);
                if(str[a] != str1[a])
                    printf("0\n");
                else
                    printf("%d\n", query(a, 0, n-1, 1) - a);
            }
            else if(op == 1)
            {
                scanf("%d%d%s", &a, &b, c);
                if(a == 1)
                    str[b] = c[0];
                else
                    str1[b] = c[0];
                update(b, 0, n-1, 1);
            }
        }
    }
    return 0;
}