HDU1540 Tunnel Warfare（Dec. 30th, 2018） 区间合并

线段树

题目来源

题意

给定一个长度为$n$、初始全为1的序列$s$和$m$个操作：
1. $D(i)$：将$s_i$变为0
2. $R$：将上一个被变为0的元素恢复为1
3. $Q(i)$：求$s_i$所在的连续1区间长度

思路

区间合并，但是在查询上遇到了些许困难。

反思

1. 此次查错耗时过长，需要更新差错算法。
2. 线段树区间合并基本掌握。

代码

// La Lune
#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>
#define il u << 1
#define el u << 1 | 1
#define lson il, l, mid
#define rson el, mid + 1, r
#define root 1, 1, n
#define morb int u, int l, int r
using namespace std;
const int N = 5e4 + 5;
int lu[N << 2], un[N << 2], ne[N << 2], lune[N];
void pushup(int u, int m){
    lu[u] = lu[il];
    ne[u] = ne[el];
    if(lu[il] == (m - (m >> 1)))
        lu[u] += lu[el];
    if(ne[el] == (m >> 1))
        ne[u] += ne[il];
    un[u] = max(ne[il] + lu[el], max(un[il], un[el]));
}
void build(morb){
    lu[u] = un[u] = ne[u] = r - l + 1;
    if(l == r)
        return;
    int mid = l + r >> 1;
    build(lson);
    build(rson);
}
void update(morb, int x, int c){
    if(l == r && l == x){
        lu[u] = un[u] = ne[u] = c;
        return;
    }
    int mid = l + r >> 1;
    if(x <= mid)
        update(lson, x, c);
    else
        update(rson, x, c);
    pushup(u, r - l + 1);
}
int query(morb, int x){
    if(l == r || un[u] == 0 || un[u] == r - l + 1)
        return un[u];
    int mid = l + r >> 1;
    if(x <= mid){
        if(x >= mid - ne[il] + 1)
            return query(lson, x) + query(rson, mid + 1);
        else
            return query(lson, x);
    }
    else{
        if(x <= mid + 1 + lu[el] - 1)
            return query(lson, mid) + query(rson, x);
        else
            return query(rson, x);
    }
}
int main(){
    int n, q;
    while(~scanf("%d %d", &n, &q)){
        int t = 0;
        build(root);
        while(q--){
            char c; int pos;
            scanf("\n%c ", &c);
            if(c == 'D'){
                scanf("%d", &pos);
                update(root, pos, 0);
                lune[++ t] = pos;
            }
            if(c == 'R'){
                if(t > 0)
                    update(root, lune[t--], 1);
            }
            if(c == 'Q'){
                scanf("%d", &pos);
                printf("%d\n", query(root, pos));
            }
        }   
    }
    return 0;
}