Query
Time Limit: 20000/10000 MS (Java/Others) Memory Limit: 65536/65536 K (Java/Others)
Total Submission(s): 2114 Accepted Submission(s): 735
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
題意：
給兩個字符串，有兩種操作。
1、改變一字符串的某個位置的一個字符。
2、詢問某一位置開始的最大的連續的兩串相同的字符的個數。
解題思路：
首先是簡單容易理解得解法。對於題目的詢問操作。如果詢問的是第p位置。如果我們知道角標大於等於p位置且字符不匹配的第一個位置q。那麼答案就是q-p。比如:
012345
aabbccd
aabeccd
對於p=0時。角標大於等於p且字符不匹配的第一個位置q=3。那麼ans=3-0=3。
現在的問題時怎樣快速維護這一信息。學習過set後知道set有一個強大的功能。
lower_bound(p)函數可以返回鍵值比p大的第一個值。所以這下就好辦了。
開始預處理。掃描一下兩個字符串。把字符不相同的位置加到set中。
對於每一個詢問。只需返回lower_bound(p)-p就行了。
對於每一個修改。如果修改後的狀態和原狀態不同。如果原來匹配現在不匹配了。就把角標加入set。
如果原來不匹配而現在匹配了就將這個角標從set中刪除。
要注意的是預處理是要將最大字符串長度+1的位置加入到set中。因為如果兩個字符完全一樣就悲劇了。
因為set中沒有值，如果詢問的話返回值就是0。於是我就這麼奉獻了一wa。。TT。
詳細見代碼：
#include <iostream>
#include<string.h>
#include<stdio.h>
#include<set>
using namespace std;
set<int> pos;
const int maxn=1000100;
char s[2][maxn];//存兩個字符串
int n,m,len,len1,len2;
int main()
{
int com,a,b,t,q,i,cas=1;
char c[100];
scanf("%d",&t);
while(t--)
{
printf("Case %d:\n",cas++);
scanf("%s%s",s[0],s[1]);
pos.clear();
len1=strlen(s[0]);
len2=strlen(s[1]);
len=max(len1,len2);
pos.insert(len);
for(i=0;i<len;i++)
if(s[0][i]!=s[1][i])
pos.insert(i);
scanf("%d",&q);
while(q--)
{
scanf("%d",&com);
if(com==1)
{
scanf("%d%d%s",&a,&b,c);
a--;
if(s[a][b]==s[a^1][b]&&c[0]!=s[a][b])
pos.insert(b);
else if(s[a][b]!=s[a^1][b]&&c[0]==s[a^1][b])
pos.erase(b);
s[a][b]=c[0];
}
else
{
scanf("%d",&a);
if(s[0][a]!=s[1][a])
{
printf("0\n");
continue;
}
printf("%d\n",*pos.lower_bound(a)-a);
}
}
}
return 0;
}
第二種方法要復雜一點。但要高效許多。用到的是線段樹區間維護。對於線段樹的一個結點。維護兩個信息。
ml，mr。分別表示該結點所代表區間中。
ml從區間左端點開始算起有多少連續個字符匹配。
mr從區間右端點開始算起有多少連續個字符匹配。
要得到這兩個信息很簡單，直接從葉子結點往上更新。
ls為左兒子的下標。rs為右兒子的下標。
k為當前結點的下標。
L,R為當前區間的左右端點。
那麼遞歸更新式就為：
ml[k]=ml[ls];
mr[k]=mr[rs];
if(ml[ls]==mid-L+1)//左區間滿了可以和右區間連在一起
ml[k]+=ml[rs];
if(mr[rs]==R-mid)//右區間滿了。
mr[k]+=mr[ls];
怎麼從維護的這兩個信息得到答案呢？
對於更新操作很簡單。如果狀態改變了。直接從葉子結點往上更新就行了。
對於詢問。假設詢問的位置為pos。那麼pos的位置有3中可能。
1.在右連續的區間內即[R-mr[k]+1,R]。
2.在左連續的區間內即[L,L+ml[k]-1]。
3.在這兩區間中間。
這三種情況依次判斷
對於第一種情況。(如圖p1)
ans+=R-pos+1。並且要標記下。因為右連續的話有可能與右邊的區間連續。到父結點時要ans+=ml[ls]。
對於第二種情況。（如圖p2）
答案是確定的。ans=L+ml[k]-pos。因為第一種情況不成立才會判斷第二種情況。說明pos後面位置至少有一個不匹配。所以ans=L+ml[k]-pos。
對於第三種情況。繼續往下詢問就行了。因為遲早會出現1,2.兩種情況。
詳細見代碼：
#include <iostream>
#include<string.h>
#include<stdio.h>
using namespace std;
const int maxn=1000100;
int ml[maxn<<2],mr[maxn<<2];//左連續。右連續的值
char s[2][maxn];//存兩個字符串
int n,m,len,ans,flag,len1,len2;
void btree(int L,int R,int k)//建樹
{
int ls,rs,mid;
if(L==R)
{
if(s[0][L]==s[1][L])
ml[k]=mr[k]=1;
else
ml[k]=mr[k]=0;
return;
}
ls=k<<1;
rs=k<<1|1;
mid=(L+R)>>1;
btree(L,mid,ls);
btree(mid+1,R,rs);
ml[k]=ml[ls];
mr[k]=mr[rs];
if(ml[ls]==mid-L+1)//若右區間全滿
ml[k]+=ml[rs];//可能變成的值
if(mr[rs]==R-mid)
mr[k]+=mr[ls];
}
void update(int L,int R,int x,int k)//更新x點
{
int ls,rs,mid;
if(L==R)
{
if(s[0][L]==s[1][L])
ml[k]=mr[k]=1;
else
ml[k]=mr[k]=0;
return;
}
ls=k<<1;
rs=k<<1|1;
mid=(L+R)>>1;
if(x>mid)
update(mid+1,R,x,rs);
else
update(L,mid,x,ls);
ml[k]=ml[ls];
mr[k]=mr[rs];
if(ml[ls]==mid-L+1)
ml[k]+=ml[rs];
if(mr[rs]==R-mid)
mr[k]+=mr[ls];
}
void qu(int L,int R,int k,int pos)//詢問pos前有多少相同字符（包括pos）
{
int ls,rs,mid;
if(L==R)
{
ans+=ml[k];
return;
}
ls=k<<1;
rs=k<<1|1;
mid=(L+R)>>1;
if(R-pos+1<=mr[k])//在右連續區間內
{
ans+=R-pos+1;
flag=1;//如果是左兒子才標記的但是。右兒子不會出現這種情況。因為點右連續區間內在父結點處就返回了。所以可以直接加標記
return;
}
if(pos-L+1<=ml[k])//在左連續區間內
{
ans=L+ml[k]-pos;
return;
}
if(pos>mid)
qu(mid+1,R,rs,pos);
else
qu(L,mid,ls,pos);
if(flag)//加上延長的區間
{
ans+=ml[rs];
flag=0;
}
}
int main()
{
int com,a,b,t,q,cas=1;
char c[100],temp;
scanf("%d",&t);
while(t--)
{
printf("Case %d:\n",cas++);
scanf("%s%s",s[0]+1,s[1]+1);//字符從一開始了方便建樹
len1=strlen(s[0]+1);
len2=strlen(s[1]+1);
len=max(len1,len2);//以較大的建樹。開始以小的建樹RE了。。TT
btree(1,len,1);
scanf("%d",&q);
while(q--)
{
scanf("%d",&com);
if(com==1)
{
scanf("%d%d%s",&a,&b,c);
a--;//2->1,1->0
b++;//由於從1開始所以要挪一下
temp=s[a][b];
s[a][b]=c[0];
if(temp==s[a^1][b]&&c[0]!=temp)
update(1,len,b,1);
else if(temp!=s[a^1][b]&&c[0]==s[a^1][b])
update(1,len,b,1);
}
else
{
scanf("%d",&a);
a++;
if(s[0][a]!=s[1][a])
{
printf("0\n");
continue;
}
flag=0;
ans=0;
qu(1,len,1,a);
printf("%d\n",ans);
}
}
}
return 0;
}
