题目意思：
给两个字符串，有两种操作。
1、改变一字符串的某个位置的一个字符。
2、查找某一位置开始的最大的连续的两串相同的字符的个数。
解题思路：
线段树维护两个值：该区间最左边连续的最大值，最右边连续的最大值。
每做一道题，停下思考，抽象出一点体会。
代码：
#include #include #include #include #include #include #include #include #include #include #include #include #include #define eps 1e-6 #define INF 0x1f1f1f1f #define PI acos(-1.0) #define ll __int64 #define lson l,m,(rt<<1) #define rson m+1,r,(rt<<1)|1 //#pragma comment(linker, "/STACK:1024000000,1024000000") using namespace std; #define Maxn 1100000 /* freopen("data.in","r",stdin); freopen("data.out","w",stdout); */ struct Node { int ls,rs; }node[Maxn*4]; //线段树维护区间两个值，1、包括左端点位置的最大连续相等的个数， //2、包括右端点位置的最大连续相等的个数 char sa1[Maxn],sa2[Maxn]; int nm,n; void pushup(int rt,int num) //向上更新 { node[rt].ls=node[rt<<1].ls; node[rt].rs=node[rt<<1|1].rs; if(node[rt].ls>=num-(num>>1)) //左孩子区间个数为num-(num>>1) node[rt].ls+=node[rt<<1|1].ls; if(node[rt].rs>=(num>>1)) //右孩子区间个数为num>>1 node[rt].rs+=node[rt<<1].rs; } void build(int l,int r,int rt) { if(l==r) { if(l>1; build(lson); build(rson); pushup(rt,r-l+1); } void update(int k,int l,int r,int rt) { if(l==r) { if(l>1; if(k<=m) update(k,lson); else update(k,rson); pushup(rt,r-l+1); } int query(int k,int l,int r,int rt) { if(l==r) return 1; //该位置一定是相同的 int m=(l+r)>>1; if(k<=m) { if(node[rt<<1].rs>m-k) //只用从该位置向右考虑就行了 return m-k+1+node[rt<<1|1].ls; else return query(k,lson); } else return query(k,rson); } int main() { // scanf("%s",sa1); // scanf("%s",sa1); // printf("%c\n",sa1[5]); int t; int ab,po,m,ki; char s[5]; scanf("%d",&t); for(int ca=1;ca<=t;ca++) { scanf("%s",sa1); scanf("%s",sa2); int len1=strlen(sa1),len2=strlen(sa2); n=max(len1,len2); nm=min(len1,len2); build(0,n-1,1); printf("Case %d:\n",ca); scanf("%d",&m); while(m--) { scanf("%d",&ki); if(ki==1) { scanf("%d%d%s",&ab,&po,s); if(ab==1) sa1[po]=*s; else sa2[po]=*s; update(po,0,n-1,1); } else { scanf("%d",&po); if(po>=nm||sa1[po]!=sa2[po]) { printf("0\n"); continue; } printf("%d\n",query(po,0,n-1,1)); } } } return 0; }