比賽的時候一頓wa啊！好傷
先將兩個數組對位比較，相等為1，否則為零，把這個01數組掛在線段樹的末節點上，然後就是向上更新啦
線段樹，線段有兩個屬性，ml存放該線段左邊最大連續長度，mr存放該線段右邊最大連續長度，在向上更新的時候是a[i].mr=a[i*2+1].mr; a[i].ml=a[i*2].ml; 這個好理解吧,但如果左孩子是全連續（這條線段的長度等於左連續長度等於右連續長度），a[i].ml=a[i*2].ml（其實這個值就是這條線段的長度）+a[i*2+1].ml; 右孩子是全連續的情況同理
insert比較好弄，就是往那個末節點改成1或0，然後同理向上更新
query的時候，如果查詢x，就找到以x為右節點的線段，因為值查詢x右邊的連續個數，找到那條線段之後，向上加右邊線段的ml（左連續值），當右邊線段不是全連續的時候，再向上就不加值了，因為左連續已經斷了
程序中的query全寫成querry了，好囧
[cpp]
#include<iostream>
#include<cstdio>
#include<string.h>
using namespace std;
#define N 1000005
struct node{
int l,r,ml,mr;
}a[N*3];
char ca[N],cb[N];
int sum,num[N],x,sign;
void build(int i,int left,int right){
a[i].l=left;
a[i].r=right;
if(a[i].l==a[i].r) {
if(num[a[i].l]==1)
a[i].ml=a[i].mr=1;
else
a[i].ml=a[i].mr=0;
return ;
}
int mid=(a[i].l+a[i].r)>>1;
build(i*2,left,mid);
build(i*2+1,mid+1,right);
if(a[i*2+1].r-a[i*2+1].l+1==a[i*2+1].ml)
a[i].mr=a[i*2].mr+a[i*2+1].ml;
else
a[i].mr=a[i*2+1].mr;
if(a[i*2].r-a[i*2].l+1==a[i*2].ml)
a[i].ml=a[i*2].ml+a[i*2+1].ml;
else
a[i].ml=a[i*2].ml;
}
void insert(int i,int x,int y){
if(a[i].l==a[i].r&&a[i].l==x){
a[i].ml=a[i].mr=y;
return ;
}
int mid=(a[i].l+a[i].r)>>1;
if(x<=mid) insert(i*2,x,y);
else insert(i*2+1,x,y);
if(a[i*2+1].r-a[i*2+1].l+1==a[i*2+1].ml)
a[i].mr=a[i*2].mr+a[i*2+1].ml;
else
a[i].mr=a[i*2+1].mr;
if(a[i*2].r-a[i*2].l+1==a[i*2].ml)
a[i].ml=a[i*2].ml+a[i*2+1].ml;
else
a[i].ml=a[i*2].ml;
}
void querry(int i,int x){
if(a[i].r==x){
sum=1;
return ;
}
int mid=(a[i].l+a[i].r)>>1;
if(x<=mid) querry(i*2,x);
else querry(i*2+1,x);
if(a[i*2].mr!=0&&a[i*2+1].ml!=0&&sign==0&&x<a[i*2+1].l)//如果要查詢的點到了右邊線段，就不能在加該線段的右面線段了，以為不是一個樹枝上的
sum+=a[i*2+1].ml;
if((a[i*2+1].r-a[i*2+1].l+1)!=a[i*2+1].ml&&x<=a[i*2].r)
sign=1;
}
int main(){
// freopen("in.txt","r",stdin);
int t,pp=1;
scanf("%d",&t);
while(t--){
printf("Case %d:\n",pp++);
scanf("%s%s",ca,cb);
int lena=strlen(ca);
int lenb=strlen(cb);
int len=lena>lenb? lena:lenb;
for(int i=0;i<len;i++){
if(ca[i]==cb[i])
num[i]=1;
else
num[i]=0;
}
build(1,0,len-1);
int q,y,z;
char te[2];
scanf("%d",&q);
while(q--){
scanf("%d",&z);
if(z==2){
scanf("%d",&x);
if(num[x]==0){
printf("0\n");
continue;
} www.2cto.com
sum=0,sign=0;
querry(1,x);
printf("%d\n",sum);
}else{
scanf("%d%d%s",&x,&y,te);
if(x==1){
ca[y]=te[0];
if(ca[y]==cb[y]) num[y]=1;
else num[y]=0;
} www.2cto.com
else{
cb[y]=te[0];
if(ca[y]==cb[y]) num[y]=1;
else num[y]=0;
}
insert(1,y,num[y]);
}
}
}
return 0;
}
作者：youngyangyang04
