zoj 3325 Machine（线段树）

浏览数：21 / 时间：2015年06月20日

题意：0~n-1的数组，初始值为0；执行m个操作，每次操作执行后输出当前值为0的连续段的段数。

操作1： p i j : i~j区间的每个元素值减1

操作2： r i j ：i~j区间的每个元素值加1，每个r操作之前，一定有个相应的p操作

数据范围：1 <= n <= 10⁸, 0 <= m <= 20000

线段树现在已经成了竞赛选手的基本功，但是我这块好弱，写下这个题解，方便自己以后复习。

分析，这很明显是个用线段树来解的题，但是数据范围太大。注意到操作次数最多只有20000次，假想所有操作都执行结束，会发现很多数组元素实际上是“成段”变化的——把所有操作的两个端点位置标记出来，则两相邻标记点之间（不包括端点）的元素值总是相同的，于是把他们缩为一个点，这样问题得以简化，数据范围大致到了 n < 60100,就可以用线段树来解了。

题解：线段树的结点定义如下：

struct Node{
    int cnt, h;//h表示“区间”高度
    bool lf, rf;//标记左右端点是不是等于0
}nd[N<<2];

结点应当有个左右端点的，为了节省内存没写，写函数的时候把端点作为参数传递就可以了（详见代码）。

cnt表示当前段值为0的连续段段数，lf和rf分别标记当前结点对应区间的左端点和右端点的值是否等于0；h是对该段整体操作的高度，事实上，可以证明h就是该区间的最大高度，因为r操作必然是对应一个之前的p操作，也就是先减后加，那么就不可能出现子结点的h比当前结点的h还大的情况，于是h就是一段区间的最大值。这是个很重要的推论，当查询到一段区间，如果它的h值不为0，就没必要往下查找了，因为不可能找到解；反之，如果该结点的h值为0，那么相当于对整体这一段没有做任何操作，换句话说，对子结点没有任何影响，那么就可以用子结点的值来更新当前结点的值了。

代码如下：

#include <cstdio>
#include <algorithm>
using namespace std;
#define N 41000
#define lc (id<<1)
#define rc (id<<1|1)

struct Node{
    int cnt, h;//h表示"区间高度"
    bool lf, rf;//标记左右端点是不是等于0
} nd[N<<2];

void build(int l, int r, int id){
    nd[id].lf = nd[id].rf = true;
    nd[id].cnt = 1;
    nd[id].h = 0;
    if(l == r) return;
    int mid = l+r>>1;
    build(l, mid, lc);
    build(mid+1, r, rc);
}

void pushup(int id,int l, int r){
    if(nd[id].h != 0)//根据题目描述，此时这一段肯定没有高度为0的点
    {           //r操作一定是取消之前的一个p操作。于是，nd[id].h相当于是这一段的最高高度
        nd[id].cnt = 0;
        nd[id].lf = nd[id].rf = false;
        return;
    }
    if(l == r){
        nd[id].cnt = 1;
        nd[id].lf = nd[id].rf = true;
        return;
    }
    else {//注意还是nd[id].h==0,那此时，这段整体相当于没有操作，根据子节点跟新这一结点的值就可以了
        nd[id].lf = nd[lc].lf, nd[id].rf = nd[rc].rf;
        nd[id].cnt = nd[lc].cnt + nd[rc].cnt - (nd[lc].rf && nd[rc].lf);
    }
}

void add(int l, int r, int v, int L, int R, int id)
{
    int mid = L+R>>1;
    if(l <= L && r >= R)
    {
        nd[id].h += v;
        pushup(id, L, R);
        return;
    }
    if(l <= mid) add(l, r, v, L, mid, lc);
    if(r > mid) add(l, r, v, mid+1, R, rc);
    pushup(id, L, R);
}
//-------------------
struct Query{
    char op[3];
    int l, r;
} qry[N>>1];

int x[N];
int xcnt;
//-------------------
int main()
{
    int T, n, q;
    char tm;
    int l, r;
    scanf("%d", &T);
    for(int cas = 1; cas <= T; cas++){
        scanf("%d %d", &n, &q);
        xcnt = 0;
        x[xcnt++] = 0;
        x[xcnt++] = n-1;
        int i;
        for(i = 0; i < q; i++){
            scanf("%s %d %d", qry[i].op, &l, &r);
            qry[i].l = l, qry[i].r = r;
            x[xcnt++] = l;
            x[xcnt++] = r;
        }
        sort(x, x+xcnt);
        xcnt = unique(x, x+xcnt)-x;
        for(i = xcnt-1; i > 0; i--) if(x[i] != x[i-1]+1) x[xcnt++] = x[i-1]+1;
        /*不这样做的反例
        5 2
        p 0 1
        p 3 4
        */
        sort(x, x+xcnt);
        build(0, xcnt-1, 1);
        printf("Case #%d:\n", cas);
        for(i = 0; i < q; i++){
            l = lower_bound(x, x+xcnt, qry[i].l)-x;
            r = lower_bound(x, x+xcnt, qry[i].r)-x;
            add(l, r, qry[i].op[0] == ‘p‘ ? -1 : 1, 0, xcnt-1, 1);
            printf("%d\n", nd[1].cnt);
        }
    }
    return 0;
}