hdu 1540 Tunnel Warfare

Problem

Solution

维护一个线段树，对于D和R的操作用单点修改。
对于Q的询问：
发现就是找(x)能最长的延伸出去的长度，那么我们左右两边二分一下即可，check函数就是长度是否等于和。
时间复杂度(mathcal{O}(T cdot m log^2{n}))
注意要多测为啥我都没读出要多测

# include <bits/stdc++.h>
using namespace std;

const int N = 50005;

int n,m;

struct node
{
    int val;
}T[N << 2];

stack <int> Del;

void build(int root,int l,int r)
{
    if(l == r)
    {
        T[root].val = 1;
        return;
    }
    int mid = (l + r) >> 1;
    build(root << 1,l,mid);
    build(root << 1 | 1,mid + 1,r);
    T[root].val = T[root << 1].val + T[root << 1 | 1].val;
    return;
}

void update(int root,int l,int r,int x,int d)
{
    if(l == x && r == x)
    {
        T[root].val = d;
        return;
    }
    int mid = (l + r) >> 1;
    if(l <= x && x <= mid) update(root << 1,l,mid,x,d);
    if(mid + 1 <= x && x <= r) update(root << 1 | 1,mid + 1,r,x,d);
    T[root].val = T[root << 1].val + T[root << 1 | 1].val;
    return;
}

int query(int root,int l,int r,int s,int t)
{
    if(l <= s && t <= r) return T[root].val;
    int mid = (s + t) >> 1;
    int ans = 0;
    if(l <= mid) ans += query(root << 1,l,r,s,mid);
    if(r > mid) ans += query(root << 1 | 1,l,r,mid + 1,t);
    return ans;
}

int left_qfind(int x)
{
    int l = 1,r = x;
    int ans = 114514;
    while(l <= r)
    {
        int mid = (l + r) >> 1;
        if(query(1,mid,x,1,n) == (x - mid + 1)) 
        {
            r = mid - 1;
            ans = mid;
        }
        else l = mid + 1;
    }
    return ans;
}

int right_qfind(int x)
{
    int l = x + 1,r = n;
    int ans = 114514;
    while(l <= r)
    {
        int mid = (l + r) >> 1;
        if(query(1,x,mid,1,n) == (mid - x + 1)) 
        {
            l = mid + 1;
            ans = mid;
        }
        else r = mid - 1;
    }
    return ans;
}

int main(void)
{
    while(~scanf("%d%d",&n,&m))
    {
        build(1,1,n);
        while(m--)
        {
            char opt;
            int x;
            cin >> opt;
            if(opt == 'D')
            {
                scanf("%d",&x);
                Del.push(x);
                update(1,1,n,x,0);
            }
            else
            {
                if(opt == 'Q')
                {
                    scanf("%d",&x);
                    int lf = left_qfind(x),rf = right_qfind(x);
                    if(lf == 114514 && rf == 114514) 
                    {
                        printf("0
");
                    } 
                    else
                    {
                        if(rf == 114514)
                        {
                            printf("%d
",x - lf + 1);
                        }
                        else 
                        {
                            if(lf == 114514)
                            {
                                printf("%d
",rf - x + 1);
                            }
                            else 
                            {
                                printf("%d
",rf - lf + 1);
                            }
                        }
                    }
                }
                else
                {
                    if(!Del.empty()) 
                    {
                        update(1,1,n,Del.top(),1);
                        Del.pop();
                    }
                }
            }
        }
    }
    
    return 0;
}