|
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;
}
|