poj 2201 构造
这个题目的构造方法应该还算是很好想的，先给a按照从小到大排序，然后按顺序插入数据，构造一棵二叉查找树，而且50000的数据，nlogn的做法，应该还是很好的。不过这个题目的编码比想象中要麻烦一点，并且编码完成后居然返回了一个tle。
表示不能理解，生成了一个大数据后，发现如果排序后k也有序，那么就会二叉树退化，n*n的复杂度。简单画画图可以找到一个优化，先找要插入数据的后继或者前驱，然后从哪个位置开始插入，那么可以大大稳定复杂度。找这个东西的工作就交给set来完成即可。
#include <iostream>#include <cstdio>#include <cstring>#include <algorithm>#include <set>using namespace std;const int maxn=5e4+9;int lon,f[maxn];struct D{ int a,k,id; bool operator <(const D & xx) const { return k<xx.k; }}data[maxn];bool cmp(const D &p,const D &q){ return p.a<q.a;}struct{ int l,r,id,fa;}tr[maxn];set <D> s;int maxm;void insert(int t){// cout<<t<<endl; int root; if(t!=1) { if(data[t].k>data[maxm].k) { root=f[data[maxm].id]; maxm=t; } else root=f[s.lower_bound(data[t])->id]; } else { root=1; maxm=1; } while(tr[root].id!=0) {// cout<<root<<endl; if(data[t].k<data[tr[root].id].k) { if(tr[root].l==0) { tr[root].l=++lon; tr[lon].fa=root; } root=tr[root].l; } else { if(tr[root].r==0) { tr[root].r=++lon; tr[lon].fa=root; } root=tr[root].r; } } tr[root].id=t; f[data[t].id]=root; s.insert(data[t]);}int main(){// freopen("in.txt","r",stdin);// freopen("out.txt","w",stdout); int n; while(scanf("%d",&n)!=EOF) { for(int i=1;i<=n;i++) { scanf("%d %d",&data[i].k,&data[i].a); data[i].id=i; } sort(data+1,data+1+n,cmp); memset(tr,0,sizeof(tr)); lon=1; for(int i=1;i<=n;i++) insert(i); printf("YES\n"); for(int i=1;i<=n;i++) { printf("%d %d %d\n",data[tr[tr[f[i]].fa].id].id,data[tr[tr[f[i]].l].id].id,data[tr[tr[f[i]].r].id].id); } } return 0;}