1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
| #include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <cmath>
using namespace std;
struct Node
{
int x,y,id;
}a[50005];
int n,f[50005][17],pos[50005][17],fa[50005],Ls[50005],Rs[50005];
inline void Init(void)
{
int i,j;
for(i=1;i<=n;++i)
{
f[i][0]=a[i].y;
pos[i][0]=i;
}
for(j=1;j<=16;++j)
{
for(i=1;i+(1<<j)-1<=n;++i)
{
if(f[i][j-1]<f[i+(1<<(j-1))][j-1])
{
f[i][j]=f[i][j-1];
pos[i][j]=pos[i][j-1];
}
else if(f[i][j-1]>f[i+(1<<(j-1))][j-1])
{
f[i][j]=f[i+(1<<(j-1))][j-1];
pos[i][j]=pos[i+(1<<(j-1))][j-1];
}
}
}
return;
}
inline int Ask(int L,int R)
{
int x=log2(R-L+1);
if(f[L][x]<=f[R-(1<<x)+1][x])return pos[L][x];
else return pos[R-(1<<x)+1][x];
}
inline int dfs(int L,int R,int pre)
{
if(L>R)return 0;
int mid=Ask(L,R),x=a[mid].id;
fa[x]=pre;
Ls[x]=dfs(L,mid-1,x);
Rs[x]=dfs(mid+1,R,x);
return x;
}
inline bool cmp(const Node& a,const Node& b)
{
return a.x<b.x;
}
int main(void)
{
int i,x,y,rt;
scanf("%d",&n);
for(i=1;i<=n;++i)
{
scanf("%d%d",&x,&y);
a[i]=(Node){x,y,i};
}
sort(a+1,a+n+1,cmp);
Init();
rt=dfs(1,n,0);
printf("YES\n");
for(i=1;i<=n;++i)printf("%d %d %d\n",fa[i],Ls[i],Rs[i]);
return 0;
}
|