hdu 1540 Tunnel Warfare

 
线段树的区间更新，求得区间内的最长序列：  
所以可以寻找两个端点，也就是被炸毁的村庄作为端点，然后再把0和n+1这两个点置为1，  
0在这里表示村庄没有没炸毁，1表示被炸毁，-1表示这个区间内既有被炸毁的村庄，也有没有被炸毁的村庄，  
那么查询两次找出两个端点，其区间也就确定了  
  
//#pragma comment(linker, "/STACK:1024000000,1024000000")  
#include <iostream>  
#include <stack>  
#include <queue>  
#include <cstdio>  
#include <cstdlib>  
#include <cmath>  
#include <set>  
#include <vector>  
#include <cstring>  
#include <algorithm>  
  
#define INF 0x3fffffff  
#define N 50010  
#define M (N << 2)  
#define LL long long  
#define mod 95041567  
  
using namespace std;  
  
struct Node{  
    int set;  
    int sum;  
};  
  
int Stack[N], len_stack, p[M];  
bool vis[N];  
  
void build(int rt, int l, int r){  
    p[rt] = 0;  
    if(l == r) {  
        vis[l] = 0;  
        return ;  
    }  
    int mid = (r - l) / 2 + l;  
    int lc = rt << 1;  
    int rc = lc + 1;  
    build(lc, l, mid);  
    build(rc, mid + 1, r);  
}  
  
void pushdown(int rt, int l, int r){  
    if(p[rt] == -1) return ;  
    int lc = rt << 1;  
    int rc = lc + 1;  
    p[lc] = p[rc] = p[rt];  
    if(! p[rt]) return;  
}  
  
void update(int rt, int l, int r, int f){  
    if(l == r){  
        p[rt] = f;  
        return ;  
    }  
    pushdown(rt, l, r);  
    int mid = (r - l) / 2 + l;  
    int lc = rt << 1;  
    int rc = lc + 1;  
    if(Stack[len_stack] <= mid) update(lc, l, mid, f);  
    else if(Stack[len_stack] > mid) update(rc, mid + 1, r, f);  
    if(p[lc] == p[rc] && p[lc] == 1) {  
        p[rt] = 1;  
        return ;  
    }  
    if(p[lc] == p[rc] && p[lc] == 0) {  
        p[rt] = 0;  
        return;  
    }  
    p[rt] = -1;  
}  
  
int dfs(int rt, int l, int r, int f){  
    if(l == r) return l;  
    int mid = (r - l) / 2 + l;  
    int lc = rt << 1;  
    int rc = lc | 1;  
    int val;  
    if(f) {  
        if(p[lc] == 1) val = l;  
        else if(p[lc] == -1) val = dfs(lc, l, mid, f);  
        else {  
            if(p[rc] == 1) val = mid + 1;  
            else if(p[rc] == 0) val = r + 1;  
            else val = dfs(rc, mid + 1, r, f);  
        }  
    }  
    else {  
        if(p[rc] == 1) val = r;  
        else if(p[rc] == -1) val = dfs(rc, mid + 1, r, f);  
        else {  
            if(p[lc] == 1) val = mid;  
            else if(p[lc] == 0) val = l - 1;  
            else val = dfs(lc, l, mid, f);  
        }  
    }  
    return val;  
}  
  
int query(int rt, int l, int r, int pos, bool f){  
    if(! p[rt]){  
        if(f) return r + 1;  
        return l - 1;  
    }  
    if(p[rt] == 1) {  
        if(f) return l;  
        return r;  
    }  
    int lc = rt << 1;  
    int rc = lc + 1;  
    int mid = (r - l) / 2 + l;  
    if(pos > mid) {  
        int val = query(rc, mid + 1, r, pos, f);  
        if(! f && ! vis[val]) {  
            if(p[lc] == -1) val = dfs(lc, l, mid, f);  
            else if(p[lc] == 0)val = l - 1;  
        }  
        return val;  
    }  
    else {  
        int val = query(lc, l, mid, pos, f);  
        if(f && ! vis[val]){  
            if(p[rc] == -1) val = dfs(rc, mid + 1, r, f);  
            else if(p[rc] == 0) val = r + 1;  
        }  
        return val;  
    }  
}  
  
int main() {  
    // freopen("in.txt", "r", stdin);  
    int m, n;  
    while(scanf("%d %d", &n, &m) != EOF){  
        len_stack = 0;  
        build(1, 1, n);  
        vis[0] = vis[n + 1] = 1;  
        while(m --){  
            getchar();  
            char ch;  
            scanf("%c", &ch);  
            if(ch == 'D'){  
                scanf("%d", &Stack[len_stack]);  
                vis[Stack[len_stack]] = 1;  
                update(1, 1, n, 1);  
                ++ len_stack;  
            }  
            else if(ch == 'Q'){  
                int pos;  
                scanf("%d", &pos);  
                if(vis[pos]){  
                    puts("0");  
                    continue;  
                }  
                int v1, v2;  
                v1 = query(1, 1, n, pos, 0);  
                v2 = query(1, 1, n, pos, 1);  
                printf("%d\n", v2 - v1 - 1);  
            }  
            else if(ch == 'R'){  
                if(len_stack){  
                    -- len_stack;  
                    vis[Stack[len_stack]] = 0;  
                    update(1, 1, n, 0);  
                }  
            }  
        }  
    }  
    return 0;  
}