ZOJ 3324 Machine(线段树区间合并）

这道题网上很多代码是错误的，由于后台数据水，他们可以AC。

比如这组数据

10 3

p 0 9

r 0 5

r 6 9

输出应该是 0 1 1

所以有的人直接记录该区间是否被覆盖过的方法是错误的

正确方法应该是记录这段区间的最小高度（就是最接近初始位置的高度），和最小高度对应的最长左区间和右区间

开一个sum记录这段区间最小高度的块数，min_v 记录该区间最小高度

cover作为懒惰标记下推该区间的子区间需要被压几次

KinderRiven

C

Accepted

6776

170

C++ (g++ 4.7.2)

3285

#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
#define lson (pos<<1)
#define rson (pos<<1|1)
const int maxn = 20005;
const int maxd = 55555;
struct Input{
    char op[5];
    int x,y;
}input[maxn];
int Hash[maxd],cnt,ret;
void Hash_init(){
    sort(Hash,Hash + cnt);
    cnt = unique(Hash,Hash + cnt) - Hash;
    int t = cnt;
    for(int i = 1; i < t; i++)
        if(Hash[i - 1] + 1 != Hash[i]) Hash[cnt++] = Hash[i - 1] + 1;
    sort(Hash,Hash + cnt);
}
int HASH(int t){
    return lower_bound(Hash,Hash + cnt,t) - Hash;
}
struct Node{
    int l,r;
    int lx,rx,min_v,sum,cover;
    int mid(){
        return (l + r) >> 1;
    }
    int len(){
        return r - l + 1;
    }
}node[maxd << 2];
void build(int l,int r,int pos){
    node[pos].l = l;
    node[pos].r = r;
    node[pos].lx = node[pos].rx = node[pos].len();
    node[pos].min_v = 0;
    node[pos].sum = 1;
    node[pos].cover = 0;
    if(l == r) return;
    int mid = node[pos].mid();
    build(l,mid,lson);
    build(mid + 1,r,rson);
}
void pushdown(int pos){
    if(node[pos].cover){
        node[lson].cover += node[pos].cover;
        node[rson].cover += node[pos].cover;
        node[lson].min_v += node[pos].cover;
        node[rson].min_v += node[pos].cover;
        node[pos].cover = 0;
    }
}
void pushup(int pos){
    node[pos].min_v = min(node[lson].min_v,node[rson].min_v);
    if(node[lson].min_v == node[rson].min_v){
        node[pos].lx = node[lson].lx;
        node[pos].rx = node[rson].rx;
        if(node[pos].lx == node[lson].len()) node[pos].lx += node[rson].lx;
        if(node[pos].rx == node[rson].len()) node[pos].rx += node[lson].rx;
        node[pos].sum = node[lson].sum + node[rson].sum;
        if(node[lson].rx && node[rson].lx)
            node[pos].sum --;
    }
    else if(node[lson].min_v < node[rson].min_v){
        node[pos].lx = node[lson].lx;
        node[pos].rx = 0;
        node[pos].sum = node[lson].sum;
    }
    else{
        node[pos].rx = node[rson].rx;
        node[pos].lx = 0;
        node[pos].sum = node[rson].sum;
    }
}
void update(int l,int r,int pos,int d){
    if(l <= node[pos].l && node[pos].r <= r){
        node[pos].cover += d;
        node[pos].min_v += d;
        return;
    }
    pushdown(pos);
    int mid = node[pos].mid();
    if(l <= mid)
        update(l,r,lson,d);
    if(r  > mid)
        update(l,r,rson,d);
    pushup(pos);
}
int main(){
    int T,Case = 1;
    scanf("%d",&T);
    while(T--){
        int n,m;
        cnt = 0;
        ret = 0;
        scanf("%d%d",&n,&m);
        Hash[cnt++] = 0;
        Hash[cnt++] = n - 1;
        for(int i = 0; i < m; i++){
            scanf("%s%d%d",input[i].op,&input[i].x,&input[i].y);
            Hash[cnt++] = input[i].x;
            Hash[cnt++] = input[i].y;
        }
        Hash_init();
        build(0,cnt - 1,1);
        printf("Case #%d:\n",Case++);
        for(int i = 0; i < m; i++){
            int l = HASH(input[i].x),r = HASH(input[i].y),c,t = 0,ans;
            if(input[i].op[0] == 'p') c = 1;
            else  c = -1;
            update(l,r,1,c);
            if(node[1].min_v == 0) t = 1;
            ans = t * node[1].sum;
            printf("%d\n",ans);
        }
    }
    return 0;
}
/*
1
10 3
p 0 9
r 0 5
r 6 9
*/