這個(gè)題是對(duì)可排序數(shù)據(jù)的實(shí)時(shí)增加刪除查找，那天做比賽的時(shí)候一點(diǎn)都不會(huì)，想來(lái)想去覺(jué)得平衡樹(shù)可以做，但是寫(xiě)平衡樹(shù)是件很難的事情。
后面知道線段數(shù)可以做，雖然數(shù)據(jù)的范圍很大，但是可以在全部讀入數(shù)據(jù)后排序再離散化，然后進(jìn)行線段樹(shù)的操作，具體的代碼沒(méi)有寫(xiě)。
今天隊(duì)友在網(wǎng)上發(fā)現(xiàn)一種用map和set可以水掉這題的方法。原來(lái)，這個(gè)方法最主要的使用了map和set里面的upper_bound操作，以前
居然忘記了這個(gè)東西了。既然這樣，map和set也可以查前驅(qū)和后繼了，但是注意low_bound查到的是小于等于的鍵。這個(gè)代碼，注意是用
了一個(gè)map< int, set<int> > 集合把坐標(biāo)都存起來(lái)了，進(jìn)行添加刪除和查找后繼的操作。由于查找需要查找的元素是既比x大又比y大的元
素，就比較麻煩，需要循環(huán)x往后查找，但是這樣就無(wú)情的超時(shí)了。然后，有一個(gè)優(yōu)化，記錄y的數(shù)目，那么當(dāng)出現(xiàn)很大的y的時(shí)候，就不需要
查找了，然后才過(guò)了這個(gè)題。但是，數(shù)據(jù)變成很大的y對(duì)應(yīng)的x很小的話，那么絕對(duì)過(guò)不了這個(gè)題了，只能用線段樹(shù)做了。
現(xiàn)在覺(jué)得用map和set查找前驅(qū)和后繼確實(shí)能水掉一些題啊。
代碼如下：
#include <map>
#include <set>
#include <stdio.h>
using namespace std;
map< int, set<int> > ms;//存儲(chǔ)x,y
map< int, set<int> >::iterator it;
map<int, int> my;//存儲(chǔ)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())//會(huì)出現(xiàn)重復(fù)的數(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;
}