来几个不那么模板的题：
对于删除，我们只要给那个元素附上不可能的值即可，关键问题是怎么处理序号变化的问题。
事实上，当我们知道每一个区间有几个元素，我们就可以确定出它的位置，因此我们可以再维护一下前缀和即可，下面是AC代码：
#include<bits/stdc++.h>
using namespace std;
int n,m;
int a[1000100];
struct node{
int maxn,minn,num;
}tree[4001000];
void build(int p,int l,int r){
if(l==r){
tree[p].maxn=a[l];
tree[p].minn=a[l];
tree[p].num=1;
return;
}
int mid=(l+r)/2;
build(p*2,l,mid);
build(p*2+1,mid+1,r);
tree[p].maxn=max(tree[p*2].maxn,tree[p*2+1].maxn);
tree[p].minn=min(tree[p*2].minn,tree[p*2+1].minn);
tree[p].num=tree[p*2].num+tree[p*2+1].num;
}
void del(int p,int l,int r,int x){
if(l==r){
tree[p].maxn=-1e9-10;
tree[p].minn=1e9+10;
tree[p].num=0;
return;
}
int mid=(l+r)/2;
if(tree[p*2].num>=x) del(p*2,l,mid,x);
else del(p*2+1,mid+1,r,x-tree[p*2].num);
//更新
tree[p].maxn=max(tree[p*2].maxn,tree[p*2+1].maxn);
tree[p].minn=min(tree[p*2].minn,tree[p*2+1].minn);
tree[p].num=tree[p*2].num+tree[p*2+1].num;
}
node query(int p,int l,int r,int x,int y){
if(x==1&&y==tree[p].num)
{
return tree[p];
}
int mid=(l+r)/2;
if(tree[p*2].num>=y) return query(p*2,l,mid,x,y);
if(tree[p*2].num<x) return query(p*2+1,mid+1,r,x-tree[p*2].num,y-tree[p*2].num);
node t1=query(p*2,l,mid,x,tree[p*2].num);
node t2=query(p*2+1,mid+1,r,1,y-tree[2*p].num);
t1.maxn=max(t1.maxn,t2.maxn);
t1.minn=min(t1.minn,t2.minn);
return t1;
}
int main(){
cin>>n>>m;
for(int i=1;i<=n;i++) scanf("%d",&a[i]);
build(1,1,n);
for(int i=1;i<=m;i++){
int q,x,y;
scanf("%d",&q);
if(q==1){
scanf("%d",&x);
del(1,1,n,x);//x为相对位置
}
else{
scanf("%d%d",&x,&y);
node ck=query(1,1,n,x,y);
printf("%d %d\n",ck.minn,ck.maxn);
}
}
}接题：
首先我们可以维护3，对于1，0用Lazy标识（4种）即可，对于2我们0的个数就是1的个数。
怎么求4？我们需要知道左区间末尾连续1的个数以及右区间开头连续1的个数，因为有0，那么还要维护连续0.
数10个tag(晕）。
下面是AC代码：
#include<bits/stdc++.h>
using namespace std;
int n,m;
struct node{
int lazy;//0权变0，1全变1，2反转，-1没干
int sum[2],max[2],left[2],right[2];
}tr[400010];
int a[100010];
void pushup(int p,int l,int r){
int mid=(l+r)/2;
for(int i=0;i<=1;i++){
tr[p].sum[i]=tr[p*2].sum[i]+tr[p*2+1].sum[i];
tr[p].max[i]=max(max(tr[p*2].max[i],tr[p*2+1].max[i]),
tr[p*2].right[i]+tr[p*2+1].left[i]);
if(tr[p*2].left[i]==mid-l+1)
tr[p].left[i]=tr[p*2].left[i]+tr[p*2+1].left[i];
else tr[p].left[i]=tr[p*2].left[i];
if(tr[p*2+1].right[i]==r-mid)
tr[p].right[i]=tr[p*2+1].right[i]+tr[p*2].right[i];
else tr[p].right[i]=tr[p*2+1].right[i];
}
}
void build(int p,int l,int r){
tr[p].lazy=-1;
if(l==r){
tr[p].sum[a[l]]=1;
tr[p].max[a[l]]=1;
tr[p].left[a[l]]=1;
tr[p].right[a[l]]=1;
return;
}
int mid=(l+r)/2;
build(p*2,l,mid);
build(p*2+1,mid+1,r);
pushup(p,l,r);
}
void jiaohuan(int p){
swap(tr[p].sum[0],tr[p].sum[1]);
swap(tr[p].max[0],tr[p].max[1]);
swap(tr[p].left[0],tr[p].left[1]);
swap(tr[p].right[0],tr[p].right[1]);
}
void pushdown(int p,int l,int r,int mid){
if(tr[p].lazy==2){
jiaohuan(p*2);
jiaohuan(p*2+1);
if(tr[p*2].lazy==-1) tr[p*2].lazy=2;
else if(tr[p*2].lazy==2) tr[p*2].lazy=-1;
else tr[p*2].lazy^=1;
if(tr[p*2+1].lazy==-1) tr[p*2+1].lazy=2;
else if(tr[p*2+1].lazy==2) tr[p*2+1].lazy=-1;
else tr[p*2+1].lazy^=1;
tr[p].lazy=-1;
}
else{
int a=tr[p].lazy;
tr[2*p].lazy=a;
tr[p*2].sum[a]=mid-l+1;
tr[p*2].max[a]=mid-l+1;
tr[p*2].left[a]=mid-l+1;
tr[p*2].right[a]=mid-l+1;
tr[p*2].sum[a^1]=0;
tr[p*2].max[a^1]=0;
tr[p*2].left[a^1]=0;
tr[p*2].right[a^1]=0;
tr[2*p+1].lazy=a;
tr[p*2+1].sum[a]=r-mid;
tr[p*2+1].max[a]=r-mid;
tr[p*2+1].left[a]=r-mid;
tr[p*2+1].right[a]=r-mid;
tr[p*2+1].sum[a^1]=0;
tr[p*2+1].max[a^1]=0;
tr[p*2+1].left[a^1]=0;
tr[p*2+1].right[a^1]=0;
tr[p].lazy=-1;
}
}
void change(int p,int l,int r,int x,int y,int a){
if(x<=l&&r<=y){
tr[p].lazy=a;
tr[p].sum[a]=r-l+1;
tr[p].max[a]=r-l+1;
tr[p].left[a]=r-l+1;
tr[p].right[a]=r-l+1;
tr[p].sum[a^1]=0;
tr[p].max[a^1]=0;
tr[p].left[a^1]=0;
tr[p].right[a^1]=0;
return;
}
int mid=(l+r)/2;
if(tr[p].lazy!=-1) pushdown(p,l,r,mid);
if(x<=mid) change(p*2,l,mid,x,y,a);
if(y>mid) change(p*2+1,mid+1,r,x,y,a);
pushup(p,l,r);
}
void rev(int p,int l,int r,int x,int y){
if(x<=l&&r<=y){
jiaohuan(p);
if(tr[p].lazy==-1) tr[p].lazy=2;
else if(tr[p].lazy==2) tr[p].lazy=-1;
else tr[p].lazy^=1;
return;
}
int mid=(l+r)/2;
if(tr[p].lazy!=-1) pushdown(p,l,r,mid);
if(x<=mid) rev(p*2,l,mid,x,y);
if(y>mid) rev(p*2+1,mid+1,r,x,y);
pushup(p,l,r);
}
int find1(int p,int l,int r,int x,int y){
if(x<=l&&r<=y){
return tr[p].sum[1];
}
int mid=(l+r)/2;
if(tr[p].lazy!=-1) pushdown(p,l,r,mid);
int ans=0;
if(x<=mid) ans+=find1(p*2,l,mid,x,y);
if(y>mid) ans+=find1(p*2+1,mid+1,r,x,y);
return ans;
}
node find2(int p,int l,int r,int x,int y){
if(x<=l&&r<=y){
return tr[p];
}
int mid=(l+r)/2;
if(tr[p].lazy!=-1) pushdown(p,l,r,mid);
if(y<=mid) return find2(p*2,l,mid,x,y);
if(x>mid) return find2(p*2+1,mid+1,r,x,y);
node ans1=find2(p*2,l,mid,x,mid);
node ans2=find2(p*2+1,mid+1,r,mid+1,y);
ans1.max[1]=max(ans1.max[1],max(ans2.max[1],ans1.right[1]+ans2.left[1]));
if(ans1.left[1]==mid-l+1) ans1.left[1]+=ans2.left[1];
if(ans2.right[1]==r-mid) ans1.right[1]+=ans2.right[1];
else ans1.right[1]=ans2.right[1];
return ans1;
}
int main(){
cin>>n>>m;
for(int i=1;i<=n;i++) scanf("%d",&a[i]);
build(1,1,n);
for(int i=1;i<=m;i++){
int op,a,b;
scanf("%d%d%d",&op,&a,&b);
a++,b++;
if(op==0){
change(1,1,n,a,b,0);
}
if(op==1) change(1,1,n,a,b,1);
if(op==2) rev(1,1,n,a,b);
if(op==3) printf("%d\n",find1(1,1,n,a,b));
if(op==4) printf("%d\n",find2(1,1,n,a,b).max[1]);
}
}
