HDU - 1540 Tunnel Warfare(线段树 + 二分)

题目链接

思路：
前提：0表示未摧毁，1表示摧毁
1. D操作单点修改即可，R操作将删除的点存入栈每次恢复栈顶的点
2. Q操作就是要查询x点往左的第一个删除点l_del和往右走第一个删除点r_del，删除点即为值为1的点，ans = del - r_del - 1;
当x为1或n时要特判，用两个不同的二分分别查询l_del和r_del即可。
3.二分的check即为Query(区间值查询)，当区间值大于0区间必有被摧毁的，往里面分，当区间值等于0就可以跳过了。
复杂度大概是O(lognlognm)

代码：

#include <bits/stdc++.h>
#define fastio ios::sync_with_stdio(false), cin.tie(NULL), cout.tie(NULL)
#define debug(a) cout << "debug : " << (#a) << " = " << a << endl
#define lson idx << 1
#define rson idx << 1 | 1

using namespace std;

typedef long long ll;
typedef pair<ll, ll> PII;

const int N = 5e4 + 10;
const int INF = 0x3f3f3f3f;
const double eps = 1e-6;
const int mod = 998244353;

int n, m;
struct node
{
    int l, r;
    ll w;
} tree[N << 2];
bool flag;

inline void PushUp(int idx)
{
    tree[idx].w = tree[lson].w + tree[rson].w;
}

void Build(int idx, int l, int r)
{
    tree[idx].l = l;
    tree[idx].r = r;
    if (l == r)
    {
        tree[idx].w = 0;
        return;
    }
    int mid = l + r >> 1;
    Build(lson, l, mid);
    Build(rson, mid + 1, r);
    PushUp(idx);
}

inline void Update(int idx, int i, int k)
{
    if (tree[idx].l == tree[idx].r && tree[idx].l <= i)
    {
        tree[idx].w = k;
        return;
    }
    int mid = tree[idx].l + tree[idx].r >> 1;
    if (i <= mid)
        Update(lson, i, k);
    else
        Update(rson, i, k);
    PushUp(idx);
}

inline ll Query(int idx, int l, int r)
{
    if (tree[idx].l >= l && tree[idx].r <= r)
        return tree[idx].w;
    ll sum = 0;
    if (tree[lson].r >= l)
        sum += Query(lson, l, r);
    if (tree[rson].l <= r)
        sum += Query(rson, l, r);
    return sum;
}

int B_Search(int l, int r, int k)
{
    if (l == r)
        return Query(1, l, r);
    if (k == 0) //k=0查询左左边第一个点
    {
        while (l < r)
        {
            int mid = l + r >> 1;
            if (Query(1, mid + 1, r) > 0)
                l = mid + 1;
            else if (Query(1, l, mid) > 0)
                r = mid;
            else
            {
                flag = false;
                break;
            }
        }
    }
    else if (k == 1) //k=1查询右边第一个点
    {
        while (l < r)
        {
            int mid = l + r >> 1;
            if (Query(1, l, mid) > 0)
                r = mid;
            else if (Query(1, mid + 1, r) > 0)
                l = mid + 1;
            else
            {
                flag = false;
                break;
            }
        }
    }
    return l;
}

int main()
{
    fastio;
    while (cin >> n >> m)
    {
        stack<int> sk;
        Build(1, 1, n);
        while (m--)
        {
            char op;
            int x;
            cin >> op;
            if (op == 'D')
            {
                cin >> x;
                Update(1, x, 1);
                sk.push(x);
            }
            else if (op == 'R')
            {
                x = sk.top();
                sk.pop();
                Update(1, x, 0);
            }
            else
            {
                cin >> x;
                if (Query(1, x, x) == 1)
                    cout << 0 << endl;
                else
                {
                    int l, r;
                    if (x == 1)
                        l = 0;
                    else
                    {
                        flag = true;
                        l = B_Search(1, x - 1, 0);
                        if (!flag)
                            l = 0;
                    }
                    if (x == n)
                        r = n + 1;
                    else
                    {
                        flag = true;
                        r = B_Search(x + 1, n, 1);
                        if (!flag)
                            r = n + 1;
                    }
                    cout << r - l - 1 << endl;
                }
            }
        }
    }

    return 0;
}