題目鏈接：http://acm.hdu.edu.cn/showPRoblem.php?pid=1540

可能是因為hdu這題的數據造的比較水。。本來以為會TLE的結果一次過了，看來map容器的find函數效率也不是那么低嘛

#include<stdio.h>#include<string.h>#include<stdlib.h>#include<algorithm>#include<map>using namespace std;#define MAXN 50050int n;int main(){    int i, j, m, num, ans, dam[MAXN];    map<int, int> tunnel;    map<int, int>::iterator pos;    char op;    memset(dam, 0, MAXN * sizeof(int));    scanf("%d%d", &n, &m);    tunnel.clear();    ans = 0;    j = 0;    for (i = 1; i <= m; i++)    {        scanf("/n");        scanf("%c", &op);        switch (op) {        case 'D':            scanf("%d", &num);            tunnel.insert(make_pair(num, num));//將摧毀的村莊插入map            dam[++j] = num;//單開一個數組記錄村莊摧毀的順序            break;        case 'R':            if (j > 0)            {                num = dam[j--];                pos = tunnel.find(num);//若有被摧毀的村莊，則從map中刪除它                tunnel.erase(pos);            }            break;        case 'Q':            scanf("%d", &num);            pos = tunnel.find(num);            if ((pos != tunnel.end()) && (pos->first == num))//若當前村莊被摧毀則一個都不連著，直接輸出0            {                printf("0/n");                break;            }            tunnel.insert(make_pair(num, num));            pos = tunnel.find(num);//否則將當前村莊插入map，分別向前向后搜索            ans = n;            if ((pos) != tunnel.begin())            {                pos--;                ans -= pos->first;//減去前方的                pos++;            }            if ((++pos) != tunnel.end())            {                ans -= (n - pos->first + 1);//減去后方的            }            printf("%d/n", ans);//輸出最終結果            tunnel.erase(num);            break;        }    }    return 0;}