POJ 2892-Tunnel Warfare【树状数组+二分】

ゞ浴缸里的玫瑰 2023-08-17 17:35 80阅读 0赞

题意：

有几个村庄，D a表示a村庄被摧毁，R表示修复上一个村庄，Q a表示包含a的连续村庄有多少个，如果a被摧毁则输出0。

1.  D x: The *x*\-th village was destroyed.
2.  第x个村庄被摧毁
3.  Q x: The Army commands requested the number of villages that *x*\-th village was directly or indirectly connected with including itself.
4.  输出包含x的连续村庄有多少个。
5.  R: The village destroyed last was rebuilt.
6.  上一个摧毁的村庄被修复了。

思路：这题可以用树状数组来实现，首先删除不用说，我们只需要记录一下方便以后恢复，主要是查询，我们可以考虑二分往左右最远能延伸的边界，然后就可以得到答案了，也是比较水的题

#include<cstdio>
    #include<cstring>
    #include<iostream>
    #include<algorithm>
    using namespace std;
    typedef long long ll;
    #define ls rt << 1
    #define rs rt << 1|1
    #define mid ((l + r) >> 1)
    #define lson l, mid, ls
    #define rson mid + 1, r, rs
    const int maxn = 1e5 + 10;
    const int mod = 1e9 + 7;
    int c[maxn], d[maxn], vis[maxn];
    int n;
    
    int lowbit(int i)
    {
        return (i & (-i));
    }
    void add(int i, int x)
    {
        while(i <= n)
        {
            c[i] += x;
            i += lowbit(i);
        }
    }
    int ask(int i)
    {
        int ret = 0;
        while(i > 0)
        {
            ret += c[i];
            i -= lowbit(i);
        }
        return ret;
    }
    
    int main()
    {
        int m;
        scanf("%d%d", &n, &m);
        for(int i = 1; i <= n; ++i)
            add(i, 1);
        int tot = 0;
        while(m--)
        {
            char s[2];
            int x;
            scanf("%s", s);
            if(s[0] == 'D')
            {
                scanf("%d", &x);
                add(x, -1);
                d[++tot] = x; //记录第几次修改的内容
                vis[x] = 1;
            }
            else if(s[0] == 'R')
            {
                add(d[tot], 1);
                vis[d[tot--]] = 0;
            }
            else if(s[0] == 'Q')
            {
                scanf("%d", &x);
                if(vis[x])
                {
                    printf("0\n");
                    continue;
                }
                int l = 1, r = x;
                int L = r;
                while(l <= r)
                {
                    if(ask(r) - ask(mid - 1) >= r - mid + 1)
                        L = mid, r = mid - 1;
                    else
                        l = mid + 1;
                }
                l = x, r = n;
                int R = l;
                while(l <= r)
                {
                    if(ask(mid) - ask(l - 1) >= mid - l + 1)
                        R = mid, l = mid + 1;
                    else
                        r = mid - 1;
                }
                int ans = R - L + 1;
                printf("%d\n", ans);
            }
        }
        return 0;
    }