补题链接： 码蹄集
一道经典线段树板子题。
区间修改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
*/
