Query
Time Limit: 20000/10000 MS (Java/Others) Memory Limit: 65536/65536 K (Java/Others)
Total Submission(s): 2063 Accepted Submission(s): 707
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].
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.
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.
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
ps：此题解法有两种，线段树和set。
set解法：
将每个不相同的位置加入set中，利用set的成员函数lower_bound()就很好找到j了。更新的话，用erase()、insert()就ok了。
感想：
这题男神教的，感觉好经典。自己是会set的，但是就是不能把问题抽象出来，转化为某个数据结构或者模型，所以比赛时是做不出来的。抽象、建模好重要，独立思考也很重要，做一道题要举一反三，要将这道题用的知识提取出来，想一想这些知识能解决哪一类的问题，这样才能一题顶十题！
代码：
#include <iostream>
#include <cstdio>
#include <cstring>
#include <set>
#include <algorithm>
#define maxn 1000005
using namespace std;
int n,m,q,ans,l,l1,l2;
char s1[maxn],s2[maxn];
set<int>s;
set<int>::iterator its;
void solve()
{
int i,j,a,t,pos;
char c[5],prec;
scanf("%d",&q);
while(q--)
{
scanf("%d",&t);
if(t==1)
{
scanf("%d%d%s",&a,&pos,c);
if(pos>=l) continue ;// 这个位置很重要 如果pos>l的话就没意义了 还好自己debug出来了 O(∩_∩)O
if(a==1)
{
prec=s1[pos];
s1[pos]=c[0];
if(prec!=s2[pos]&&c[0]==s2[pos]) s.erase(pos);
else if(prec==s2[pos]&&c[0]!=s2[pos]) s.insert(pos);
}
else
{
prec=s2[pos];
s2[pos]=c[0];
if(prec!=s1[pos]&&c[0]==s1[pos]) s.erase(pos);
else if(prec==s1[pos]&&c[0]!=s1[pos]) s.insert(pos);
}
}
else
{
scanf("%d",&pos);
its=s.lower_bound(pos);
if(its!=s.end()) printf("%d\n",*its-pos);
else printf("%d\n",l-pos);
}
}
}
int main()
{
int i,j,k,t;
scanf("%d",&t);
for(k=1;k<=t;k++)
{
scanf("%s%s",s1,s2);
l1=strlen(s1);
l2=strlen(s2);
l=l1<l2?l1:l2;
s.clear();
for(i=0;i<l;i++)
{
if(s1[i]!=s2[i]) s.insert(i);
}
printf("Case %d:\n",k);
solve();
}
return 0;
}