题解 P1503 【鬼子进村】

66666a · 2017-08-17 16:29:22 · 题解

这题用线段树，平衡树都能过

但是其实我们可以用STL中的set

设一个set记录当前被炸的房子编号，并且维护编号从小到大，当我们查询x时，找到在s中比x大的第一个和比x小的最后一个，位置之差减1即为答案。

代码出奇的短

#include<bits/stdc++.h>
#define M 50010
using namespace std;
int q[M],tail,n,m;
set<int> s;
set<int>:: iterator it;
int main()
{
    scanf("%d%d",&n,&m);
    s.insert(0);
    s.insert(n+1);
    for(int i=1;i<=m;i++)
    {
        char c;
    cin>>c;//用scanf会把空格读进来
        if(c=='D')
        {
            int x;                      // 加入x
            scanf("%d",&x);
            s.insert(x);
            q[++tail]=x;
        }
        if(c=='Q')
        {
            int x;                       //查询
            scanf("%d",&x);
            it=s.lower_bound(x);
            if(*it==x)
            {
                printf("0\n");
                continue;
            }
            int ans=*it-*(--it);
            printf("%d\n",ans-1);
        }
        if(c=='R')                    //删除
        {
            it=s.find(q[tail--]);
            s.erase(it);
        }
    }
    return 0;
}