這個題是對可排序數(shù)據(jù)的實時增加刪除查找，那天做比賽的時候一點都不會，想來想去覺得平衡樹可以做，但是寫平衡樹是件很難的事情。
后面知道線段數(shù)可以做，雖然數(shù)據(jù)的范圍很大，但是可以在全部讀入數(shù)據(jù)后排序再離散化，然后進行線段樹的操作，具體的代碼沒有寫。
今天隊友在網(wǎng)上發(fā)現(xiàn)一種用map和set可以水掉這題的方法。原來，這個方法最主要的使用了map和set里面的upper_bound操作，以前
居然忘記了這個東西了。既然這樣，map和set也可以查前驅(qū)和后繼了，但是注意low_bound查到的是小于等于的鍵。這個代碼，注意是用
了一個map< int, set<int> > 集合把坐標都存起來了，進行添加刪除和查找后繼的操作。由于查找需要查找的元素是既比x大又比y大的元
素，就比較麻煩，需要循環(huán)x往后查找，但是這樣就無情的超時了。然后，有一個優(yōu)化，記錄y的數(shù)目，那么當出現(xiàn)很大的y的時候，就不需要
查找了，然后才過了這個題。但是，數(shù)據(jù)變成很大的y對應(yīng)的x很小的話，那么絕對過不了這個題了，只能用線段樹做了。
現(xiàn)在覺得用map和set查找前驅(qū)和后繼確實能水掉一些題啊。
代碼如下：
#include <map>
#include <set>
#include <stdio.h>
using namespace std;
map< int, set<int> > ms;//存儲x,y
map< int, set<int> >::iterator it;
map<int, int> my;//存儲y的數(shù)目
set<int>::iterator msit;
int main()
{
int nN;
int nCase = 1;
char szCmd[10];
int nX, nY;
int nTemp;
while(scanf("%d", &nN), nN)
{
if (nCase > 1)
{
printf("\n");
}
printf("Case %d:\n", nCase++);
ms.clear();
my.clear();
while (nN--)
{
scanf("%s", szCmd);
scanf("%d%d", &nX, &nY);
if (szCmd[0] == 'a')
{
if (my.find(nY) == my.end())
{
my[nY] = 1;
}
else
{
my[nY]++;
}
if (ms.find(nX) == ms.end())
{
ms[nX].insert(nY);
}
else
{
msit = ms[nX].find(nY);
if (msit == ms[nX].end())//會出現(xiàn)重復的數(shù)據(jù)
{
ms[nX].insert(nY);
}
}
}
else if (szCmd[0] == 'r')
{
ms[nX].erase(nY);
if(ms[nX].size() == 0)
{
ms.erase(nX);
}
my[nY]--;
if (my[nY] == 0)
{
my.erase(nY);
}
}
else if (szCmd[0] == 'f')
{
if (my.upper_bound(nY) == my.end())
{
printf("-1\n");
continue;
}
while (true)
{
it = ms.upper_bound(nX);
if (it == ms.end())//比nX大的不存在
{
printf("-1\n");
break;
}
nTemp = it->first;
msit = ms[nTemp].upper_bound(nY);
if (msit == ms[nTemp].end())//比nY大的不存在
{
nX = nTemp;
continue;//那么增加x,繼續(xù)往后查
}
else
{
printf("%d %d\n", nTemp, *msit);
break;
}
}
}
}
}
return 0;
}