首页 > ACM题库 > HDU-杭电 > HDU 3911-Black And White-线段树-[解题报告]HOJ
2015
04-14

HDU 3911-Black And White-线段树-[解题报告]HOJ

Black And White

问题描述 :

There are a bunch of stones on the beach; Stone color is white or black. Little Sheep has a magic brush, she can change the color of a continuous stone, black to white, white to black. Little Sheep like black very much, so she want to know the longest period of consecutive black stones in a range [i, j].

输入:

  There are multiple cases, the first line of each case is an integer n(1<= n <= 10^5), followed by n integer 1 or 0(1 indicates black stone and 0 indicates white stone), then is an integer M(1<=M<=10^5) followed by M operations formatted as x i j(x = 0 or 1) , x=1 means change the color of stones in range[i,j], and x=0 means ask the longest period of consecutive black stones in range[i,j]

输出:

  There are multiple cases, the first line of each case is an integer n(1<= n <= 10^5), followed by n integer 1 or 0(1 indicates black stone and 0 indicates white stone), then is an integer M(1<=M<=10^5) followed by M operations formatted as x i j(x = 0 or 1) , x=1 means change the color of stones in range[i,j], and x=0 means ask the longest period of consecutive black stones in range[i,j]

样例输入:

4
1 0 1 0
5
0 1 4
1 2 3
0 1 4
1 3 3
0 4 4

样例输出:

1
2
0

线段树结点结构:
    bl,br,ba 分别表示包括左端点黑石子的连续长度,包括右端点黑石子的连续长度,区间中黑石子的最大连续长度
    wl,wr,wa 分别表示包括左端点白石子的连续长度,包括右端点白石子的连续长度,区间中白石子的最大连续长度
    ta 表示结点的子结点是否需要更新
对于区间[a,b]的更新操作:
    首先找到线段树中相应的区间,将黑变白、白变黑实际上就是把 bl,br,ba 和 wl,wr,wa 互换。但是不对这个区间的子区间再进行更新(如果这样做的话时间复杂度就会达到O(n)),而是将 ta xor 1,记下该区间的子区间没有被跟新,下次如果用到(更新或者查询)该区间的子区间再对其进行更新。对包含被更新区间的所有区间进行更新。

#include <stdio.h>
#include <stdlib.h>
#include <math.h>
#include <string.h>
#include <memory.h>
#include <string>
#include <vector>
#include <map>
#include <set>
#include <queue>
#include <algorithm>
#include <iostream>
using namespace std;

const int N = 100005;

struct Node {
    int l, r;
    int bl, br, ba;
    int wl, wr, wa;
    int ta;
} st[N*3];

int ary[N];

void Update(int p) {
    int lp = p * 2, rp = p * 2 + 1;
    
    if ((st[p].ba = max(st[lp].ba, st[rp].ba)) < st[lp].br + st[rp].bl)
        st[p].ba = st[lp].br + st[rp].bl;
    if ((st[p].wa = max(st[lp].wa, st[rp].wa)) < st[lp].wr + st[rp].wl)
        st[p].wa = st[lp].wr + st[rp].wl;
    int ll = st[lp].r - st[lp].l + 1, rl = st[rp].r - st[rp].l + 1;
    st[p].bl = st[lp].bl; if (st[lp].bl == ll) st[p].bl += st[rp].bl;
    st[p].wl = st[lp].wl; if (st[lp].wl == ll) st[p].wl += st[rp].wl;
    st[p].br = st[rp].br; if (st[rp].br == rl) st[p].br += st[lp].br;
    st[p].wr = st[rp].wr; if (st[rp].wr == rl) st[p].wr += st[lp].wr;
}

void Change(int p) {
    swap(st[p].bl, st[p].wl);
    swap(st[p].br, st[p].wr);
    swap(st[p].ba, st[p].wa);
    st[p].ta ^= 1;
}

void Build(int l, int r, int p) {
    st[p].l = l; st[p].r = r; st[p].ta = 0;
    if (l == r) {
        if (ary[l]) {
            st[p].bl = st[p].br = st[p].ba = 1;
            st[p].wl = st[p].wr = st[p].wa = 0;
        } else {
            st[p].wl = st[p].wr = st[p].wa = 1;
            st[p].bl = st[p].br = st[p].ba = 0;
        }
        return;
    }
    int m = (l + r) / 2;
    Build(l, m, p * 2);
    Build(m + 1, r, p * 2 + 1);
    Update(p);
}

void Update(int l, int r, int p) {
    if (st[p].l == l && st[p].r == r) {
        Change(p);
        return;
    }
    if (st[p].ta) {
        Change(p * 2);
        Change(p * 2 + 1);
        st[p].ta ^= 1;
    }
    int m = (st[p].l + st[p].r) / 2;
    if (r <= m) Update(l, r, p * 2);
    else if (l > m) Update(l, r, p * 2 + 1);
    else Update(l, m, p * 2), Update(m + 1, r, p * 2 + 1);
    Update(p);
}

int Query(int l, int r, int p) {
    // printf("%d %d %d\n", p, st[p].ba, st[p].ta);
    if (st[p].l == l && st[p].r == r) {
        return st[p].ba;
    } 
    if (st[p].ta) {
        Change(p * 2);
        Change(p * 2 + 1);
        st[p].ta ^= 1;
    }
    int m = (st[p].l + st[p].r) / 2;
    if (r <= m) return Query(l, r, p * 2);
    else if (l > m) return Query(l, r, p * 2 + 1);
    else {
        int lr = Query(l, m, p * 2);
        int rr = Query(m + 1, r, p * 2 + 1);
        return max(max(min(st[p*2].br, lr) + min(st[p*2+1].bl, rr), lr), rr);
    }
}

int main() {
    int n, m, i, a, b, c;
    while (scanf("%d", &n) != EOF) {
        for (i = 1; i <= n; i++)
            scanf("%d", ary + i);
        Build(1, n, 1);
        scanf("%d", &m);
        for (i = 0; i < m; i++) {
            scanf("%d %d %d", &a, &b, &c);
            if (a) Update(b, c, 1);
            else printf("%d\n", Query(b, c, 1));
        }
    }
    return 0;
}

版权声明:本文为博主原创文章,未经博主允许不得转载。

参考:http://blog.csdn.net/racebug2010/article/details/6673718


  1. Good task for the group. Hold it up for every yeara??s winner. This is a excellent oppotunity for a lot more enhancement. Indeed, obtaining far better and much better is constantly the crucial. Just like my pal suggests on the truth about ab muscles, he just keeps obtaining much better.