D - 秋实大哥与战争

Time Limit: 1 Sec Memory Limit: 256 MB

题目连接

http://acm.uestc.edu.cn/#/contest/show/59

Description

男儿何不带吴钩，收取关山五十州。

征战天下是秋实大哥一生的梦想，所以今天他又在练习一个对战游戏。

秋实大哥命令所有士兵从左到右排成了一行来抵挡敌人的攻击。

敌方每一次会攻击一个士兵，这个士兵就会阵亡，整个阵列就会从这个位置断开；同时有的时候已阵亡的士兵会受人赢气息感染而复活。

秋实大哥想知道某一时刻某一个士兵所在的阵列的长度是多少。

Input

第一行包含两个整数n，m，表示秋实大哥的士兵数目和接下来发生的事件数目。

接下来m行，每一行是以下三种事件之一：

0 x : 表示x位置的士兵受到攻击阵亡
1 x : 表示x位置的士兵受人赢气息感染复活
2 x : 秋实大哥想知道第x个士兵所在阵列的长度

1≤n，m≤100000，1≤x≤n。

Output

对于每一个2 x事件，输出对应的答案占一行。

Sample Input

5 3
2 2
0 3
2 2

Sample Output

5
2

HINT

题意

题解：

set算法～

代码：

//qscqesze

#include <cstdio>

#include <cmath>

#include <cstring>

#include <ctime>

#include <iostream>

#include <algorithm>

#include <set>

#include <vector>

#include <sstream>

#include <queue>

#include <typeinfo>

#include <fstream>

#include <map>

typedef long long ll;

using namespace std;

//freopen("D.in","r",stdin);

//freopen("D.out","w",stdout);

#define sspeed ios_base::sync_with_stdio(0);cin.tie(0)

#define maxn 200001

#define mod 10007

#define eps 1e-9

//const int inf=0x7fffffff;   //无限大

const int inf=0x3f3f3f3f;

/*

int buf[10];

inline void write(int i) {

  int p = 0;if(i == 0) p++;

  else while(i) {buf[p++] = i % 10;i /= 10;}

  for(int j = p-1; j >=0; j--) putchar('0' + buf[j]);

  printf("\n");

}

*/

//**************************************************************************************

inline ll read()

{

    int x=,f=;char ch=getchar();

    while(ch<''||ch>''){if(ch=='-')f=-;ch=getchar();}

    while(ch>=''&&ch<=''){x=x*+ch-'';ch=getchar();}

    return x*f;

}

set<int> s;

int flag[maxn],n,m,a,b,c,d;

int main()

{

    n=read(),m=read();

    s.insert(),s.insert(n+);

    for(int i=;i<m;i++)

    {

        scanf("%d%d",&a,&b);

        {

            if(a==)

            {

                if(!flag[b])

                {

                    s.insert(b);

                    flag[b]=;

                }

            }

            else if(a==)

            {

                if(flag[b])

                {

                    s.erase(b);

                    flag[b]=;

                }

            }

            else

            {

                if(flag[b])

                {

                    printf("0\n");

                }

                else

                {

                    c=*s.lower_bound(b);

                    d=*--s.lower_bound(b);

                    printf("%d\n",c-d-);

                }

            }

        }

    }

}

秋实大哥

2015 UESTC 数据结构专题D题 秋实大哥与战争 ＳＥＴ的妙用