HDU-1540/洛谷-1503

县城里有 $n$ 个用地道相连的房子，第 $i$ 个只与第 $i-1$ 和第 $i+1$ 个相连。这时有 $m$ 个消息依次传来：

1. 若消息为 D x：鬼子将 $x$ 号房子摧毁了，地道被堵上。

2. 若消息为 R ：村民们将鬼子上一个摧毁的房子修复了。

3. 若消息为 Q x：有一名士兵被围堵在 $x$ 号房子中。

李云龙收到信息很紧张，他想知道每一个被围堵的士兵能够到达的房子有几个。

思路

将房子被摧毁标为 $1$ ，未被摧毁标为 $0$ 。

由于操作二，所以建一个栈来存放每次操作一的操作对象。

对于操作一和二，直接单点修改即可。

对于操作三，若该房子已经被摧毁，则答案就是 $0$ ；否则，需要考虑找到该房子左边第一个和右边第一个没有被摧毁的房子的下标，再由此来计算能够到达的房子的数量。

于是难点就在于如何处理操作三。

我的想法是先查出 $x$ 号房左右各被摧毁的房子的数量 $L$ 和 $R$ ，然后再利用查询 $k$ 大的方法来找到从左数第 $L+1$ 个被摧毁的房子的下标 $r$ 和从右数第 $R+1$ 个被摧毁的房子的下标 $l$ ，最后若 $l=r$ 说明 $x$ 号房已经被摧毁，答案为 $0$ ，否则答案为 $r-l-1$ 。

感觉我这个思路真的好繁琐

代码

#include<bits/stdc++.h>
#define N 50010

using namespace std;

inline int read() {
    int w=1,x=0;
    char ch=0;
    while(ch<'0'||ch>'9') {if(ch=='-') w=-1;ch=getchar();}
    while(ch>='0'&&ch<='9') x=x*10+ch-'0',ch=getchar();
    return w*x;
}

int n,m;
stack<int> s;

class Segment_Tree{
  private:
    int sum[N<<2];
    #define s(x) sum[x]
    #define ls (p<<1)
    #define rs (ls|1)
    #define mid (l+r>>1)
    void update(int p) {
        s(p)=s(ls)+s(rs);
    }
  public:
    void build(int p,int l,int r) {
        if(l==r) {
            s(p)=0;
            return ;
        }
        build(ls,l,mid),build(rs,mid+1,r);
        update(p);
    }
    void modify(int p,int l,int r,int x,int y) {
        if(l>x||r<x) return ;
        if(l==r) {
            s(p)=y;
            return ;
        }
        modify(ls,l,mid,x,y),modify(rs,mid+1,r,x,y);
        update(p);
    }
    int ask_l(int p,int l,int r,int x) {
        if(l>=x) return 0;
        if(r<x) return s(p);
        return ask_l(ls,l,mid,x)+ask_l(rs,mid+1,r,x); 
    }
    int ask_r(int p,int l,int r,int x) {
        if(r<=x) return 0;
        if(l>x) return s(p);
        return ask_r(ls,l,mid,x)+ask_r(rs,mid+1,r,x);
    }
    int ask_L(int p,int l,int r,int x) {
        if(l==r) return l;
        if(s(ls)>=x) return ask_L(ls,l,mid,x);
        return ask_L(rs,mid+1,r,x-s(ls));
    }
    int ask_R(int p,int l,int r,int x) {
        if(l==r) return l;
        if(s(rs)>=x) return ask_R(rs,mid+1,r,x);
        return ask_R(ls,l,mid,x-s(rs));
    }
    int ask(int x) {
        int L=ask_l(1,0,n,x),R=ask_r(1,0,n,x);
        int r=ask_L(1,0,n,L+1),l=ask_R(1,0,n,R+1);
        return l==r?0:r-l-1;
    }
}SMT;
 
int main() {
    n=read()+1,m=read();

    SMT.build(1,0,n);
    SMT.modify(1,0,n,0,1),SMT.modify(1,0,n,n,1);
    for(int i=1;i<=m;i++) {
        char op;
        int x;
        cin>>op;
        if(op=='D') {
            x=read();
            SMT.modify(1,0,n,x,1);
            s.push(x);
        }
        if(op=='R') {
            x=s.top();
            s.pop();
            SMT.modify(1,0,n,x,0);
        }
        if(op=='Q') {
            x=read();
            printf("%d\n",SMT.ask(x));
        }
    }
    system("pause");
    return 0;
}