鬼子进村|P1503

https://www.luogu.com.cn/problem/P1503

题目背景

小卡正在新家的客厅中看电视。电视里正在播放放了千八百次依旧重播的《亮剑》，剧中李云龙带领的独立团在一个县城遇到了一个鬼子小队，于是独立团与鬼子展开游击战。

题目描述

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

  1. 若消息为 D x：鬼子将 xxx 号房子摧毁了，地道被堵上。
  2. 若消息为 R ：村民们将鬼子上一个摧毁的房子修复了。
  3. 若消息为 Q x：有一名士兵被围堵在 xxx 号房子中。

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

说明/提示

1 ≤ n, m ≤ 50000

若士兵被围堵在摧毁了的房子中，那只能等死了。。。。。。

怎么做呢？

首先我们看几眼题，把这个题抽象成：

oooooooooooooooooooooooooooooooooooo

有一条长链链，

操作会把链上的o变成x（或变回来），将链分成多块（或合并），

每次询问一个位置，问它所在块的长度。

先看问题能不能解：

弱智都会，没脸讲

询问的位置往左循环找到第一个x或边界，右侧同理，相加后再加自己本身即可

接下来证明不能这么做：

如果没有一个x，询问50000次，程序就会轮循50000长的链50000次，2500000000对电脑来说要运行25s。。。

接下来看优化点：

oxooooooooooooooooooo0ooooooooooooooooooxoxooo

假设询问0处，先往左搜，竟然要一个一个挨着跑过去

看着都急

于是干脆把x的位置记下来不就好了

x：2 40 42

我只要知道询问的位置夹在那两个x中间就行了

这件事我们可以用二分查找解决，在一个有序的数组中找到最后一个小于给定数和第一个大于给定数的位置。

（上py）

二分不难，但坏事是这并不是固定的数组，它会插入与删除元素

这时需要c++的STL发光熠彩

引出#include <set>

对于一个set<int> s;我们能做些什么呢？

s.insert(x);//插入一个数
s.erase(x);//删除一个数
s.lower_bound(x);//返回第一个大于等于x的迭代器
s.upper_bound(x);//返回第一个大于x的迭代器

后两者也是二分解决的，由于c++的set是树形构造，所以兼顾了链表可插入和数组可二分的优点（虽然要慢一些）

这时候就可以愉快AC了

你发现它竟然要求修复的是上一个摧毁的房屋，而不是指定的，，，

这时候需要再引入一个数据结构，叫栈

简单理解，就是一个有口无肛的腔肠动物罢了

示意图
示意图

对于栈，如果要求不多，STL也是个很好的选择：

#include <stack>
stack <int> sta;
sta.push(x);//在栈顶加一个元素
sta.top(x);//函数返回栈顶的的元素
sta.pop(x);//弹出栈顶元素

你会发现，栈顶的元素永远是最后一个加进去的

听起来很好用对吧\`\`\`

补充：关于迭代器

上面说过函数会返回一个迭代器，那迭代器是什么呢？

其实简单来说是一个封装好的指针

用*对它取值后返回的就是该元素的值了

也可以用++,--运算符来让它指向前一个/后一个元素

由于set是有序容器，所以用迭代器遍历后是有序的

去AC吧。
#include<iostream>
#include<cstdio>
#include<set>
#include<stack>
using namespace std;
inline int read(){//快读
    int s=0,f=1;
    char c=getchar();
    while(c<48 || c>57){if(c=='-')f=-f;c=getchar();}
    while(c>=48 && c<=57)s=s*10+c-48,c=getchar();
    return s*f;
}
set <int> s;
stack <int> sta;
int n,m;
signed main(){
    n=read();
    m=read();
    char op;
    int x;
    s.insert(0);
    s.insert(n+1);
    for(int i=0;i<m;i++){
        op=getchar();
        char t=getchar();
        if(op=='D'){
            x=read();
            s.insert(x);
            sta.push(x);
        }
        else if(op=='R'){
            s.erase(sta.top());
            sta.pop();
        }
        else {
            x=read();
            if(x<=0 || x>=n+1)return 0;//别管。。。
            auto it=s.upper_bound(x);
            it--;
            if(*it==x){
                cout<<0<<endl;
            }
            else{
                int tmp=*it;
                int ans=*(++it);
                cout<<ans-tmp-1<<endl;
            }
        }
    }
    return 0;
}