hdu 4339 Query 线段树 多校联合赛（四） 第九题
比赛的时候一顿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.zzzyk.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;
补充：软件开发 , C++ ,
