hdu 4399 不错的线段树

Query
Time Limit: 20000/10000 MS (Java/Others) Memory Limit: 65536/65536 K (Java/Others)
Total Submission(s): 1857 Accepted Submission(s): 595

Problem Description
You are given two strings s1[0..l1], s2[0..l2] and Q - number of queries.
Your task is to answer next queries:
1) 1 a i c - you should set i-th character in a-th string to c;
2) 2 i - you should output the greatest j such that for all k (i<=k and k<i+j) s1[k] equals s2[k].

Input
The first line contains T - number of test cases (T<=25).
Next T blocks contain each test.
The first line of test contains s1.
The second line of test contains s2.
The third line of test contains Q.
Next Q lines of test contain each query:
1) 1 a i c (a is 1 or 2, 0<=i, i<length of a-th string, 'a'<=c, c<='z')
2) 2 i (0<=i, i<l1, i<l2)
All characters in strings are from 'a'..'z' (lowercase latin letters).
Q <= 100000.
l1, l2 <= 1000000.

Output
For each test output "Case t:" in a single line, where t is number of test (numbered from 1 to T).
Then for each query "2 i" output in single line one integer j.

Sample Input
1
aaabba
aabbaa
7
2 0
2 1
2 2
2 3
1 1 2 b
2 0
2 3

Sample Output
Case 1:
2
1
0
1
4
1

Source
2012 Multi-University Training Contest 4

Recommend
zhoujiaqi2010

题意：

题意：有两个字符串，给出 Q 个询问，每个询问有两种体式格式：

1 p i c 把第 p 个字符串的第i 个字符换成字符 c，

2i 从第位i 开始，两个字符串连续相同的子串的最大长度为多少。

思路
如果第i个位置上相同，则为0，不同则为1，这样就可以转化成求第i个位置后面一第一个1的位置。
一开始自己不知道如何实现查询函数

参考了大牛的才过了

[cpp]
#include<stdio.h>
#include<string.h>
struct haha
{
    int left;
    int right;
    int r_len;
    int l_len;
}node[1000011*4];
char s1[1000011],s2[1000011];
int a[1000011];
void pushup(int nd)
{
    int rl=node[nd*2+1].right-node[nd*2+1].left+1;
    int ll=node[nd*2].right-node[nd*2].left+1;
    node[nd].l_len=node[nd*2].l_len;
    node[nd].r_len=node[nd*2+1].r_len;
    if(node[nd].l_len==ll) node[nd].l_len+=node[nd*2+1].l_len;
    if(node[nd].r_len==rl) node[nd].r_len+=node[nd*2].r_len;
}
void build(int left,int right,int nd)
{
    int mid;
    mid=(left+right)/2;
    node[nd].left=left;
    node[nd].right=right;
    if(left==right)
    {
        if(s1[left]==s2[left]) {a[left]=1;node[nd].r_len=node[nd].l_len=1;}
        else {a[left]=0;node[nd].r_len=node[nd].l_len=0;}
        return ;
    }
    build(left,mid,nd*2);
    build(mid+1,right,nd*2+1);
    pushup(nd);
}
void update(int pos,int val,int nd)
{
    if(node[nd].left==node[nd].right) {a[pos]=val;node[nd].l_len=node[nd].r_len=val;return;}
    else
    {
        int mid=(node[nd].left+node[nd].right)/2;
        if(pos<=mid) update(pos,val,nd*2);
        else update(pos,val,nd*2+1);

    }
    pushup(nd);
}
int query(int pos,int nd)//主要是这个函数   我一开始没有思路
{
          if(pos==node[nd].left) return node[nd].l_len;
          if(node[nd].left==node[nd].right) return node[nd].l_len;
          if(pos>node[2*nd].right) return query(pos,nd*2+1);//进入右分支
          else
          {
              int len=node[nd*2].right-pos+1;
              if(node[nd*2].r_len<len) return query(pos,nd*2);
              else return len+query(node[nd*2+1].left,nd*2+1);
          }
}
int main()
{
    int cas,k,d2,d1,ccas=0;
    scanf("%d",&cas);
    while(cas--)
    {
        printf("Case %d:\n",++ccas);
        scanf("%s %s",s1+1,s2+1);
        d1=strlen(s1+1);
        d2=strlen(s2+1);
        if(d1>d2) d1=d2;
        build(1,d1,1);
        scanf("%d",&k);
        while(k--)
        {
            int flag;
            scanf("%d",&flag);
            if(flag==1)
            {
                int kk,pos,val;
                char ch;
                scanf("%d %d %c",&kk,&pos,&ch);
                pos++;
                if(pos>d1) continue;//注意题目范围这句很阴啊
                if(kk==1)
                {
                    if(ch==s2[pos]) val=1;

补充：软件开发 , C++ ,