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;
else
val=0;
s1[pos]=ch;
}
else
{
if(ch==s1[pos]) val=1;
else val=0;
s2[pos]=ch;
}
update(pos,val,1);
}
else
{
int left;
scanf("%d",&left);
left++;
printf("%d\n",query(left,1));
}
}
}
return 0;
}
