学步园

2012多校题目，线段树求解

输入两个字符串，只要判断相同长度部分即可，多出来的部分可以忽略。转化：判断两个字符串相同位置字符是否相同，如果相同置为1，不同为0

那么问题就变成求 i到末尾的最长连续1的个数，当然起始点是 i

线段树记录左边最长连续1，右边最长连续1，记录右边是因为 query的时候要判断如果 询问的 位置 i 是在左边，那么右区间可不可以合并

#include<iostream>
#include<algorithm>
#include<stdio.h>
#include<string.h>
using namespace std;

#define lson u<<1
#define rson u<<1|1
#define MAXN 1000010
#define for if(0);else for

char s[3][MAXN];
int same[MAXN];

struct Node{
    int lef,rig,lsum,rsum;
}T[MAXN<<2];

void PushUp(int u){
    int len=T[u].rig-T[u].lef+1;
    T[u].lsum=T[lson].lsum;
    T[u].rsum=T[rson].rsum;
    if(T[u].lsum==(len+1)>>1)T[u].lsum+=T[rson].lsum;
    if(T[u].rsum==len>>1)T[u].rsum+=T[lson].rsum;
}

void Build(int u,int l,int r){
    T[u].lef=l;
    T[u].rig=r;
    T[u].lsum=T[u].rsum=0;
    if(l==r){T[u].lsum=T[u].rsum=same[l];return;}
    int mid=(l+r)>>1;
    Build(lson,l,mid);
    Build(rson,mid+1,r);
    PushUp(u);
}

void Update(int u,int index,int val){
    if(T[u].lef==T[u].rig){
        T[u].lsum=T[u].rsum=val;return;
    }
    else {
        if(index<=T[lson].rig)Update(lson,index,val);
        else Update(rson,index,val);
        PushUp(u);
    }
}

int Query(int u,int l,int r){
    if(T[u].lef==l)return T[u].lsum;
    else {
        if(l>=T[rson].lef)return Query(rson,l,r);
        //else return Query(lson,l,)
        else {
            //int len=T[u].rig-T[u].lef+1;
            if(T[lson].rsum>=T[lson].rig-l+1)
                return Query(lson,l,T[lson].rig)+Query(rson,T[rson].lef,r);
            return Query(lson,l,T[lson].rig);
        }
    }
}

int main(){
    int T;
    int Q;
    int cmd;
    int str,pos;
    char reset;
    scanf("%d",&T);
    for(int cas=1;cas<=T;cas++){
        scanf("%s%s",s[1],s[2]);
        int lens1=strlen(s[1]);
        int lens2=strlen(s[2]);
        int len=min(lens1,lens2);
        memset(same,0,sizeof(same));
        int cnt=1;
        for(int i=0;i<len;i++){
            if(s[1][i]==s[2][i])same[cnt++]=1;
            else same[cnt++]=0;
        }
        Build(1,1,cnt);
        scanf("%d",&Q);
        printf("Case %d:\n",cas);
        while(Q--){
            scanf("%d",&cmd);
            if(cmd==1){
                scanf("%d%d %c",&str,&pos,&reset);
                if(pos>=len)continue;
                s[str][pos]=reset;
                if(reset==s[3-str][pos])same[pos+1]=1;
                else same[pos+1]=0;
                Update(1,pos+1,same[pos+1]);
            }
            else {
                scanf("%d",&pos);
                printf("%d\n",Query(1,pos+1,cnt));
            }
        }
    }
}