|
l[0],tree[rs].ll[1]); swap(tree[rs].rr[0],tree[rs].rr[1]); } else if(tree[rs].lazy == 1) { tree[rs].lazy = 0; tree[rs].sum = 0; tree[rs].long0 = tree[rs].ll[0] = tree[rs].rr[0] = r-mid; tree[rs].long1 = tree[rs].ll[1] = tree[rs].rr[1] = 0; } else if(tree[rs].lazy == 0) { tree[rs].lazy = 1; tree[rs].sum = r-mid; tree[rs].long0 = tree[rs].ll[0] = tree[rs].rr[0] = 0; tree[rs].long1 = tree[rs].ll[1] = tree[rs].rr[1] = r-mid; } } tree[v].lazy = -1; } void build(int v, int l, int r) { tree[v].l = l; tree[v].r = r; tree[v].lazy = -1; tree[v].sum = 0; tree[v].ll[0] = tree[v].rr[0] = tree[v].long0 = 0; tree[v].ll[1] = tree[v].rr[1] = tree[v].long1 = 0; if(l == r) { tree[v].sum = a[l]; if(a[l] == 0) tree[v].ll[0] = tree[v].rr[0] = tree[v].long0 = 1; else tree[v].ll[1] = tree[v].rr[1] = tree[v].long1 = 1; return; } int mid = (l+r)>>1; build(v*2,l,mid); build(v*2+1,mid+1,r); push_up(v); } void update(int v, int l, int r, int op) { if(tree[v].l == l && tree[v].r == r) { if(op == 0) { tree[v].lazy = tree[v].sum = 0; tree[v].ll[0] = tree[v].rr[0] = tree[v].long0 = tree[v].r - tree[v].l + 1; tree[v].ll[1] = tree[v].rr[1] = tree[v].long1 = 0; } else if(op == 1) { tree[v].lazy = 1; tree[v].sum = tree[v].r - tree[v].l + 1; tree[v].ll[1] = tree[v].rr[1] = tree[v].long1 = tree[v].r - tree[v].l + 1; tree[v].ll[0] = tree[v].rr[0] = tree[v].long0 = 0; } else if(op == 2) { if(tree[v].lazy == 0) { tree[v].lazy = 1; tree[v].sum = tree[v].r - tree[v].l + 1; tree[v].ll[1] = tree[v].rr[1] = tree[v].long1 = tree[v].r-tree[v].l+1; tree[v].ll[0] = tree[v].rr[0] = tree[v].long0 = 0; } else if(tree[v].lazy == 1) { tree[v].lazy = tree[v].sum = 0; tree[v].ll[1] = tree[v].rr[1] = tree[v].long1 = 0; tree[v].ll[0] = tree[v].rr[0] = tree[v].long0 = tree[v].r-tree[v].l+1; } else if(tree[v].lazy == -1 || tree[v].lazy == 2) { tree[v].lazy = 1-tree[v].lazy; tree[v].sum = tree[v].r-tree[v].l+1-tree[v].sum; swap(tree[v].long0,tree[v].long1); swap(tree[v].ll[0],tree[v].ll[1]); swap(tree[v].rr[0],tree[v].rr[1]); } } return; } push_down(v); int mid = (tree[v].l + tree[v].r) >> 1; if(r <= mid) update(v*2,l,r,op); else if(l > mid) update(v*2+1,l,r,op); else { update(v*2,l,mid,op); update(v*2+1,mid+1,r,op); } push_up(v); } int query(int v, int l, int r,int op) { if(tree[v].l == l && tree[v].r == r) { if(op == 3) return tree[v].sum; else return tree[v].long1; } push_down(v); int mid = (tree[v].l + tree[v].r) >> 1; if(r <= mid) return query(v*2,l,r,op); else if(l > mid) return query(v*2+1,l,r,op); else { if(op == 3) return query(v*2,l,mid,op) + query(v*2+1,mid+1,r,op); else { //求区间[l,r]中最长的连续是1的长度。 int tmp = min(tree[v*2].rr[1],mid-l+1) + min(tree[v*2+1].ll[1],r-mid); return max(tmp,max(query(v*2,l,mid,op),query(v*2+1,mid+1,r,op))); } } } int main() { int test; int n,m; int op,l,r; scanf(%d,&test); while(test--) { scanf(%d %d,&n,&m); for(int i = 1; i <= n; i++) scanf(%d,&a[i]); build(1,1,n); while(m--) { scanf(%d %d %d,&op,&l,&r); l++; r++; if(op <= 2) { update(1,l,r,op); } else { int ans = query(1,l,r,op); printf(%d ,ans); } } } return 0; }
?
?
|