【问题描述】

最近小 R 成立了一个 RP 俱乐部， 吸引了很多热心的同学。 成为这个俱乐部会

员的唯一条件就是要和老会员进行一场比赛， 以证明自己的 RP。

我们假设每个人都有一个固定的 RP 值， 另外， 每个人都有一个唯一的 ID。 为了使

比赛更加好看， 每一个新会员都会选择与他的 RP 最为接近的人比赛， 即双方的 RP 值

之差越小越好， 如果有两个人的 RP 值与他差别相同， 则他会选择更小的那一个人比赛。

现在， 给出所有会员的注册顺序， 你能帮小 R 统计每场比赛双方的 ID

吗？

【输入格式】

第一行一个数 N， 表示俱乐部新来的会员数(不包括小 R)。

以后 N 行每行两个正整数， 按照注册的顺序给出每个人的 ID 和 RP。

一开始小 R 就算是会员， ID 为 1， RP 为 1,000,000,000。 输入保证任意两个人的 RP

都不同。

【输出格式】

N 行， 每行两个数， 为每场比赛双方的 ID， 新会员的 ID 写在前面。

【样例】

club.in club.out

3

2 1

3 3

4 2

club.out

2 1

3 2

4 2

【数据规模】

40%的数据满足： N≤1,000 ID， RP≤1,000,000,000；

100%的数据满足： N≤200,000 ID， RP≤1,000,000,000。

如何快速求出对于每个会员来说RP最接近他且进入俱乐部的时间比他早的会员？

注意到求这个答案的过程是二维单调的，所以可以想到用单调栈来维护

先把所有人按照RP排序，再分别从左到右、从右到左维护进入俱乐部时间从小到大的单调栈，就可以得到符合上述条件的会员。

UPD：这是个二维单调DP，所以不按RP排序应该也可以做，这样时间复杂度就是O(n)了

1 #include 
     
       2 #include 
      
        3 #include 
       
         4 using namespace std; 5 struct P{
   int realid,id,rp,ans;}p[200002]; 6 int a,n,top,sta[200002],trp[200002],real[200002]; 7 void read(int &x) 8 { 9     char ls=getchar();x=0;10     for (;ls<'0'||ls>'9';ls=getchar());11     for (;ls>='0'&&ls<='9';ls=getchar())x=x*10+ls-'0';12 }13 bool cmp1(P a,P b)14 {15     return a.rp
        
         =0&&p[sta[top]].id>p[i].id) top--;38         if (top>=0)39         {40             trp[i]=abs(p[sta[top]].rp-p[i].rp);41             p[i].ans=sta[top];42         }43         sta[++top]=i;44     }45     top=0;sta[0]=n+1;46     for (int i=n;i>=1;i--)47     {48         while (top>=0&&p[sta[top]].id>p[i].id) top--;49         if (abs(p[sta[top]].rp-p[i].rp)