刚学了RMQ算法。
做pku 2201 的时候。刚开始根本没啥好的算法。按照一般的思路走下来肯定是超时。
后来看了讨论，用不熟练的RMQ写了个。（搞惨了，这个程序整了我一整天）
#include<algorithm>
#include<cmath>
#include<stdlib.h>
#include <algorithm>
using namespace std;
#define MAX 50005
struct Node{
int parent;
int left;
int right;
int id;
int key;
int akey;
};
Node tree[MAX];
int n,f[MAX][16];
bool cmpbykey(Node n1,Node n2){
return (n1.key<n2.key);
}
bool cmpbyid(Node n1,Node n2){
return (n1.id<n2.id);
}
void RMQ(){
sort(tree+1,tree+n+1,cmpbykey);
for(int i=1;i<=n;i++){
f[i][0]=i;
}
for(int j=1;j<=log((double)(n))/log(2.0);j++)
for(int i=1;(i+(1<<j)-1)<=n;i++){
f[i][j]=f[i][j-1];
if(tree[f[i+(1<<(j-1))][j-1]].akey<tree[f[i][j]].akey){
f[i][j]=f[i+(1<<(j-1))][j-1];
}
}
/*for(int j=0;j<=log((double)(n-1))/log(2.0);j++)
for(int i=1;i+(1<<j)-1<=n;i++){
printf("%d",f[i][j]);
system("pause");
}*/
}
int Min_setbyRmq(int left,int right){
int m;
m=(log((double)(right-left+1))/log(2.0));
if(tree[f[left][m]].akey<tree[f[right-(1<<(m))+1][m]].akey)
return f[left][m];
else return f[right-(1<<m)+1][m];
}
bool maketree(int left,int right){
if(left==right) {
tree[left].left=0;
tree[left].right=0;
return true;
}
int root,rootleft,rootright;
root=Min_setbyRmq(left,right);
if(root!=left){
rootleft=Min_setbyRmq(left,root-1);
}
if(root!=right){
rootright=Min_setbyRmq(root+1,right);
}
bool check1=true,check2=true;
if(root!=left&&tree[root].key>tree[rootleft].key){
tree[root].left=tree[rootleft].id;
tree[rootleft].parent=tree[root].id;
check1=maketree(left,root-1);
}
if(root!=right&&tree[root].key<tree[rootright].key){
tree[root].right=tree[rootright].id;
tree[rootright].parent=tree[root].id;
check2=maketree(root+1,right);
}
return (check1&&check2);
}
int main(){
int i,t;
scanf("%d",&n);
for(i=1;i<=n;i++){
scanf("%d%d",&tree[i].key,&tree[i].akey);
tree[i].id=i;
}
RMQ();
if(maketree(1,n)){
/* for(i=1;i<=n;i++){
printf("%d %d %d\n",tree[i].parent,tree[i].left,tree[i].right);
system("pause");
}*/
printf("YES\n");
sort(tree+1,tree+n+1,cmpbyid);
for(i=1;i<=n;i++){
printf("%d %d %d\n",tree[i].parent,tree[i].left,tree[i].right);
system("pause");
}
}
else printf("NO\n");
}
//主要是调试的时候，整死就是过不去。
//虽然不是完全独立坐下来的。不过还是感到很高兴、