HDU-3397(統合)
3544 ワード
5つの操作があります.
このうち、前の3つは、改、区間改1、改0、区間0、および区間0、1が、現在押下すべきマークが変更されるかどうかを反転させる場合であり、2つの場合である.
クエリは、2つの差区間1の和であり、区間の最大連続が1の区間である.
このうち、前の3つは、改、区間改1、改0、区間0、および区間0、1が、現在押下すべきマークが変更されるかどうかを反転させる場合であり、2つの場合である.
クエリは、2つの差区間1の和であり、区間の最大連続が1の区間である.
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <iostream>
using namespace std;
#define lson l,m,rt<<1
#define rson m+1,r,rt<<1|1
#define rep(i,n) for(int (i)=0;(i)<(n);(i)++)
const int N = 1e5+1000;
struct node{
int l,r,Max[2],sum,pre[2],suf[2];
}a[N<<2];
int col[N<<2],rot[N<<2],b[N];
node push_up(node A,node B){
node te;
te.l=A.l; te.r=B.r;
te.sum=A.sum+B.sum;
for(int i=0;i<=1;i++){
te.Max[i] = max(A.Max[i],B.Max[i]);
te.Max[i] = max(te.Max[i],A.suf[i]+B.pre[i]);
te.pre[i] = A.pre[i];
if(te.pre[i] == A.r-A.l+1) te.pre[i]+=B.pre[i];
te.suf[i] = B.suf[i];
if(te.suf[i] == B.r-B.l+1) te.suf[i]+=A.suf[i];
}
return te;
}
void build(int l,int r,int rt){
rot[rt]=0; col[rt]=-1;
if(l==r){
scanf("%d",&b[l]);
a[rt].l=l; a[rt].r=r;
a[rt].sum= b[l];
rep(i,2){
int v= 0; if(b[l]==i) v=1;
a[rt].Max[i]=a[rt].pre[i]=a[rt].suf[i]=v;
}
return ;
}
int m=(l+r)>>1;
build(lson);
build(rson);
a[rt]=push_up(a[rt<<1],a[rt<<1|1]);
}
void upd_one(int l,int r,int rt,int v1,int v2){
if(v1!=-1){
col[rt]=v1; rot[rt]=v2;
a[rt].sum = (v1 ? r-l+1:0);
if(v2) a[rt].sum = r-l+1-a[rt].sum;
if(a[rt].sum==r-l+1){
a[rt].pre[0]=a[rt].suf[0]=a[rt].Max[0]=0;
a[rt].pre[1]=a[rt].suf[1]=a[rt].Max[1]=r-l+1;
}
else {
a[rt].pre[0]=a[rt].suf[0]=a[rt].Max[0]=r-l+1;
a[rt].pre[1]=a[rt].suf[1]=a[rt].Max[1]=0;
}
}
else if(v2){
rot[rt]^=1;
a[rt].sum = r-l+1 -a[rt].sum;
swap(a[rt].pre[1],a[rt].pre[0]);
swap(a[rt].suf[1],a[rt].suf[0]);
swap(a[rt].Max[1],a[rt].Max[0]);
}
}
void push_down(int l,int r,int rt){
if(col[rt]!=-1||rot[rt]!=-1){
int m=(l+r)>>1;
upd_one(l,m,rt<<1,col[rt],rot[rt]);
upd_one(m+1,r,rt<<1|1,col[rt],rot[rt]);
col[rt]=rot[rt]=-1;
}
}
void update(int l,int r,int rt,int L,int R,int v){
if(L<=l&&r<=R){
int v1 ,v2;
if(v<2) v1=v,v2=0; else v1=-1,v2=1;
upd_one(l,r,rt,v1,v2);
return ;
}
push_down(l,r,rt);
int m=(l+r)>>1;
if(L<=m) update(lson,L,R,v);
if(R >m) update(rson,L,R,v);
a[rt]=push_up(a[rt<<1],a[rt<<1|1]);
}
int query(int l,int r,int rt,int L,int R){
if(L<=l&&r<=R){
return a[rt].sum;
}
push_down(l,r,rt);
int m=(l+r)>>1;
int res = 0;
if(L<=m) res+=query(lson,L,R);
if(R >m) res+=query(rson,L,R);
return res;
}
node Query(int l,int r,int rt,int L,int R){
if(L<=l&&r<=R){
return a[rt];
}
push_down(l,r,rt);
int m=(l+r)>>1;
node res; int ok=0;
if(L<=m) {res=Query(lson,L,R); ok=1;}
if(R >m) {
if(ok) res=push_up(res,Query(rson,L,R));
else res = Query(rson,L,R);
}
return res;
}
int n,m;
int main()
{
int T;
scanf("%d",&T);
while(T--){
scanf("%d %d",&n,&m);
build(1,n,1);
while(m--){
int cmd,x,y;
scanf("%d %d %d",&cmd,&x,&y);
x++; y++;
if(cmd<=2) update(1,n,1,x,y,cmd);
else if(cmd==3){
printf("%d
",query(1,n,1,x,y));
}
else {
node res = Query(1,n,1,x,y);
printf("%d
",res.Max[1]);
}
}
}
return 0;
}