補題鏈接：?碼蹄集

一道經典線段樹板子題。

區間修改01置換，區間查詢子串權值。

唯一區別，權值要求的是相鄰字符都不同所需修改的最小字符個數。

我們在線段樹節點上分別維護當前連續區間：

奇數位是0的個數（j0），奇數位是1的個數（j1）。

偶數位是0的個數（o0），偶數位是1的個數（o1）。

以及當前區間的答案ans，是否往子區間延遲lazy。

考慮如何通過維護的信息進行pushup。

如圖所示：

黑色三角：表示虛線左右子區間各自的奇數位置

紅色三角：表示合并后奇數位置。

當左區間是奇數時，黑色三角=紅色三角

要想變成10間斷，要不變成101010...，要不變成0101010....

令 ls是左區間，rs是右區間。

如果變成101010，那就是ans=tr[ls].j0+tr[ls].o1+tr[rs].j0+tr[rs].o1

如果變成010101，那就是ans=總長度-(tr[ls].j0+tr[ls].o1+tr[rs].j0+tr[rs].o1)

取個max就行。

但當左區間不是奇數，黑色三角!=紅色三角

如果變成101010，那就是ans=tr[ls].j0+tr[ls].o1+tr[rs].j1+tr[rs].o0

如果變成010101，那就是ans=總長度-(tr[ls].j0+tr[ls].o1+tr[rs].j1+tr[rs].o0)

到這里我們就解決了從子區間到大區間的pushup問題，代碼如下所示。
?

void pushup(int p){int len=tr[p].r-tr[p].l+1;int lenls=tr[ls].r-tr[ls].l+1;if (lenls&1){int sum=tr[ls].j0+tr[ls].o1+tr[rs].j1+tr[rs].o0;tr[p].ans=min(sum,len-sum);tr[p].j0=tr[ls].j0+tr[rs].o0;tr[p].j1=tr[ls].j1+tr[rs].o1;tr[p].o0=tr[ls].o0+tr[rs].j0;tr[p].o1=tr[ls].o1+tr[rs].j1;}else{int sum=tr[ls].j0+tr[ls].o1+tr[rs].j0+tr[rs].o1;tr[p].ans=min(sum,len-sum);tr[p].j0=tr[ls].j0+tr[rs].j0;tr[p].j1=tr[ls].j1+tr[rs].j1;tr[p].o0=tr[ls].o0+tr[rs].o0;tr[p].o1=tr[ls].o1+tr[rs].o1;}
}

pushdown問題，其實比較常規，就是01置換，異或一下就行，代碼如下所示。

void pushdown(int p){tr[ls].laz=tr[ls].laz^tr[p].laz;tr[rs].laz=tr[rs].laz^tr[p].laz;swap(tr[ls].j0,tr[ls].j1);swap(tr[ls].o0,tr[ls].o1);swap(tr[rs].j0,tr[rs].j1);swap(tr[rs].o0,tr[rs].o1);tr[p].laz=0;
}

當我們維護的東西不只是ans的時候，query需要返回一個結構體，因為當查詢的x，y在左右區間都有的時候，需要向上手動合并。

全部問題解決完后，完整代碼如下所示。?

#include<bits/stdc++.h>
using namespace std;
const int N=2e6+5;
#define ls p<<1
#define rs p<<1|1
struct tree{int l,r;int j0,j1,o0,o1;int laz,ans;
}tr[N];
char s[N];
int n,q;
void pushup(int p){int len=tr[p].r-tr[p].l+1;int lenls=tr[ls].r-tr[ls].l+1;if (lenls&1){int sum=tr[ls].j0+tr[ls].o1+tr[rs].j1+tr[rs].o0;tr[p].ans=min(sum,len-sum);tr[p].j0=tr[ls].j0+tr[rs].o0;tr[p].j1=tr[ls].j1+tr[rs].o1;tr[p].o0=tr[ls].o0+tr[rs].j0;tr[p].o1=tr[ls].o1+tr[rs].j1;}else{int sum=tr[ls].j0+tr[ls].o1+tr[rs].j0+tr[rs].o1;tr[p].ans=min(sum,len-sum);tr[p].j0=tr[ls].j0+tr[rs].j0;tr[p].j1=tr[ls].j1+tr[rs].j1;tr[p].o0=tr[ls].o0+tr[rs].o0;tr[p].o1=tr[ls].o1+tr[rs].o1;}
}
void pushdown(int p){tr[ls].laz=tr[ls].laz^tr[p].laz;tr[rs].laz=tr[rs].laz^tr[p].laz;swap(tr[ls].j0,tr[ls].j1);swap(tr[ls].o0,tr[ls].o1);swap(tr[rs].j0,tr[rs].j1);swap(tr[rs].o0,tr[rs].o1);tr[p].laz=0;
}
void build(int p,int l,int r){tr[p].l=l;tr[p].r=r;tr[p].laz=0;if (l==r){tr[p].j0=0;tr[p].j1=0;if (s[l]=='0') tr[p].j0=1;else if (s[l]=='1') tr[p].j1=1;			tr[p].ans=0;return;}int mid=(l+r)>>1;build(ls,l,mid);build(rs,mid+1,r);pushup(p);
}
void update(int p,int x,int y){int l=tr[p].l,r=tr[p].r;if (x<=l&&r<=y){tr[p].laz=tr[p].laz^1;swap(tr[p].j0,tr[p].j1);swap(tr[p].o0,tr[p].o1);return;}if (tr[p].laz) pushdown(p);int mid=(l+r)>>1;if (x<=mid) update(ls,x,y);if (y>mid) update(rs,x,y);pushup(p);
}
tree query(int p,int x,int y){int l=tr[p].l,r=tr[p].r;if (x<=l&&r<=y){return tr[p];}if (tr[p].laz) pushdown(p);int mid=(l+r)>>1;if (y<=mid) return query(ls,x,y);else if (x>mid) return query(rs,x,y);else{struct tree T,a,b;a=query(ls,x,y);b=query(rs,x,y);T.l=a.l;T.r=b.r;int len=T.r-T.l+1;int lenls=a.r-a.l+1;if (lenls&1){int sum=a.j0+a.o1+b.j1+b.o0;T.ans=min(sum,len-sum);T.j0=a.j0+b.o0;T.j1=a.j1+b.o1;T.o0=a.o0+b.j0;T.o1=a.o1+b.j1;}else{int sum=a.j0+a.o1+b.j0+b.o1;T.ans=min(sum,len-sum);T.j0=a.j0+b.j0;T.j1=a.j1+b.j1;T.o0=a.o0+b.o0;T.o1=a.o1+b.o1;}return T;}
}
void co(){for (int i=1;i<=9;i++){cout<<tr[i].l<<" "<<tr[i].r<<" "<<tr[i].laz<<" "<<tr[i].ans<<"||";cout<<"S:";for (int j=1;j<=n;j++){cout<<s[j];}cout<<"\n";cout<<"奇數 0:"<<tr[i].j0<<"| 1:"<<tr[i].j1<<"|||";cout<<"偶數 0:"<<tr[i].o0<<"| 1:"<<tr[i].o1<<"\n";}
}
void work(){cin>>n>>q;for (int i=1;i<=n;i++) cin>>s[i];build(1,1,n);for (int i=1;i<=q;i++){int t,l,r;cin>>t>>l>>r;if (t==1) update(1,l,r);else cout<<query(1,l,r).ans<<"\n";	}
}
signed main(){ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);work();return 0;
} 
/*
10101
000
*/