题目链接:hdu3397
线段树区间合并,和poj3667类似,都是老套路。。。
#include <iostream> #include <queue> #include <cstdio> #include <cstring> #include <algorithm> using namespace std; #define lson l, m, rt<<1 #define rson m+1, r, rt<<1|1 const int N = 200005; struct node { int col; int llen,rlen,mlen; int num;//区间内1的数量 }s[N<<2]; void pushup(int rt, int m)//更新父节点 { s[rt].llen = s[rt<<1].llen; s[rt].rlen = s[rt<<1|1].rlen; if(s[rt].llen == m-(m>>1)) s[rt].llen += s[rt<<1|1].llen; if(s[rt].rlen == (m>>1)) s[rt].rlen += s[rt<<1].rlen; s[rt].mlen = max(s[rt<<1].rlen + s[rt<<1|1].llen, max(s[rt<<1].mlen, s[rt<<1|1].mlen) ); s[rt].num = s[rt<<1].num + s[rt<<1|1].num;//左儿子和右儿子的num和 } void pushdown(int rt, int m)//更新子节点 { if(s[rt].col == 1) { s[rt<<1].num = m - (m>>1); s[rt<<1|1].num = (m>>1); } if(s[rt].col == 0) s[rt<<1].num = s[rt<<1|1].num = 0; if(s[rt].col != -1) { s[rt<<1].llen = s[rt<<1].rlen = s[rt<<1].mlen = (s[rt].col==1?m-(m>>1):0); s[rt<<1|1].llen = s[rt<<1|1].rlen = s[rt<<1|1].mlen = (s[rt].col==1?(m>>1):0); s[rt<<1].col = s[rt<<1|1].col = s[rt].col; s[rt].col = -1; } } void build(int l, int r, int rt) { s[rt].col = -1; if(l == r) { scanf("%d",&s[rt].col); if(s[rt].col == 1) { s[rt].llen = s[rt].rlen = s[rt].mlen = 1; s[rt].num = 1; } else s[rt].llen = s[rt].rlen = s[rt].mlen = s[rt].num = 0; return; } int m = (l+r) >> 1; build(lson); build(rson); pushup(rt, r-l+1); } void change(int l, int r, int rt)//进行操作2,即将区间内的0变为1,1变为0 { if(s[rt].col == 0)//将0变为1 { s[rt].col = 1; s[rt].num = s[rt].llen = s[rt].rlen = s[rt].mlen = r-l+1; return; } if(s[rt].col == 1)//将1变为0 { s[rt].col = 0; s[rt].num = s[rt].llen = s[rt].rlen = s[rt].mlen = 0; return; } if(l == r) return; int m = (l+r) >> 1; change(lson); change(rson); pushup(rt, r-l+1); } void update(int c, int L, int R, int l, int r, int rt) { if(L <= l && r <= R) { if(c == 0)//操作0,将区间内所有数变为0 { s[rt].col = 0; s[rt].num = 0; s[rt].llen = s[rt].rlen = s[rt].mlen = 0; } else if(c == 1)//操作1,将区间内所有数变为1 { s[rt].col = 1; s[rt].num = r-l+1; s[rt].llen = s[rt].rlen = s[rt].mlen = r-l+1; } else if(c == 2) change(l, r, rt); return ; } pushdown(rt, r-l+1); int m = (l+r) >> 1; if(L <= m) update(c, L, R, lson); if(R > m) update(c, L, R, rson); pushup(rt, r-l+1); } int query3(int L, int R, int l, int r, int rt)//操作3,查1的个数 { if(L <= l && r <= R) return s[rt].num; pushdown(rt, r-l+1); int m = (l+r) >> 1; int ans = 0; if(L <= m) ans += query3(L, R, lson); if(m < R) ans += query3(L, R, rson); return ans; } int query4(int L, int R, int l, int r, int rt)//操作4,查连续个1的长度 { if(L <= l && r <= R) return s[rt].mlen; pushdown(rt, r-l+1); int m = (l+r) >> 1; int ans = 0; if(L <= m) ans = max(ans, query4(L, R, lson)); if(m < R) ans = max(ans, query4(L, R, rson)); ans = max(ans, min(m-L+1,s[rt<<1].rlen) + min(R-m, s[rt<<1|1].llen) );//很重要 return ans; } int main() { //freopen("in.txt","r",stdin); int T,n,m; scanf("%d",&T); while(T--) { scanf("%d%d",&n,&m); build(1, n, 1); int x,y,z; while(m--) { scanf("%d%d%d",&x,&y,&z); if(x < 3) update(x, y+1, z+1, 1, n, 1); if(x == 3) printf("%d\n",query3(y+1, z+1, 1, n, 1)); if(x == 4) printf("%d\n",query4(y+1, z+1, 1, n, 1)); } } return 0; }