Tunnel Warfare （HDU - 1540，这也能用线段树 ？！）

一.题目链接：

HDU-1540

二.题目大意：

有 n 个村庄排列在一条线上，编号为 1 ~ n.

现有 3 种 m 次操作

D x：摧毁第 x 个村庄

Q x：查询与第 x 个村庄相邻的村庄数.

R：修复上一个被摧毁的村庄.

三.分析：

当查询与第 x 个村庄相邻的村庄数时

只需要查询在 1 ~ x 中被摧毁村庄的最大编号

&& 在 x ~ n 中被摧毁村庄的最小编号.

初始化时，将每个点的最大值赋值为 0，最小值赋值为 n + 1.

那么用线段树来储存就好了.

四.代码实现：

#include <set>
#include <map>
#include <ctime>
#include <queue>
#include <cmath>
#include <stack>
#include <vector>
#include <cstdio>
#include <sstream>
#include <cstring>
#include <cstdlib>
#include <iostream>
#include <algorithm>
#define eps 1e-6
#define pi acos(-1.0)
#define ll long long int
using namespace std;

const int M = (int)5e4;

struct node
{
    int l;
    int r;
    int Min;
    int Max;
} tree[M * 4 + 5];

int Min, Max;
stack <int> st;

void build(int k, int l, int r, int n)
{
    tree[k].l = l;
    tree[k].r = r;
    tree[k].Min = n + 1;
    tree[k].Max = 0;
    if(l == r)
        return;
    int mid = (l + r) / 2;
    build(k * 2, l, mid, n);
    build(k * 2 + 1, mid + 1, r, n);
}

void change(int k, int l, int r, int x, int n, bool flag)
{
    if(l == r && l == x)
    {
        if(!flag)
            tree[k].Max = tree[k].Min = x;
        else
        {
            tree[k].Max = 0;
            tree[k].Min = n + 1;
        }
        return;
    }
    int mid = (l + r) / 2;
    if(x <= mid)
        change(k * 2, l, mid, x, n, flag);
    else
        change(k * 2 + 1, mid + 1, r, x, n, flag);
    tree[k].Max = max(tree[k * 2].Max, tree[k * 2 + 1].Max);
    tree[k].Min = min(tree[k * 2].Min, tree[k * 2 + 1].Min);
}

void query1(int k, int l, int r, int x)
{
    if(tree[k].r <= x)
    {
        Max = max(Max, tree[k].Max);
        return;
    }
    int mid = (l + r) / 2;
    query1(k * 2, l, mid, x);
    if(mid < x)
        query1(k * 2 + 1, mid + 1, r, x);
}

void query2(int k, int l, int r, int x)
{
    if(tree[k].l >= x)
    {
        Min = min(Min, tree[k].Min);
        return;
    }
    if(l == r)
        return;
    int mid = (l + r) / 2;
    if(x <= mid)
        query2(k * 2, l, mid, x);
    query2(k * 2 + 1, mid + 1, r, x);
}

int main()
{
    int n, m;
    while(~scanf("%d %d", &n, &m))
    {
        while(!st.empty())
            st.pop();
        build(1, 1, n, n);
        while((m--) > 0)
        {
            getchar();
            char dir;
            scanf("%c", &dir);
            if(dir == 'D')
            {
                int x;
                scanf("%d", &x);
                change(1, 1, n, x, n, 0);
                st.push(x);
            }
            else if(dir == 'Q')
            {
                Min = n + 1;
                Max = 0;
                int x;
                scanf("%d", &x);
                query1(1, 1, n, x);
                query2(1, 1, n, x);
                if(Min == Max)
                    printf("0\n");
                else
                    printf("%d\n", Min - Max - 1);
            }
            else if(dir == 'R')
            {
                int x = st.top();
                st.pop();
                change(1, 1, n, x, n, 1);
            }
        }
    }
    return 0;
}