poj提交数量过万的题，除了水爆了的题就是无比经典的，不得不刷的题。 准备将poj上提交次数过万的题刷个遍。 持续更新中。。。
poj 2828（线段树）
此题乃是Zhu, Zeyuan神牛出的，拿到题目就觉得这题真的是很有意思，苦想一天无果。 感叹大神的思维果真奇妙。 随随便便提出的问题都成为了如此经典。看了下讨论发现貌似不好想，再尝试了下发现有些问题还是没有想出解决掉方法，而且越来越混乱， 无奈只能看题解了。。。
由于插队是具有最高优先级，而且显然最后一个人插在哪里那么他的最终位置就是哪里。 所以可以从后往前看。先将最后一个人放好，再根据最后一个人的位置判断倒数第二个人的位置。 由此如果能在得知后n个点的位置推出从后往前第n+1个点的位置，那么这题就可以得到完美解决。直接模拟的话需要n*n的复杂度，明显不行。
用num[s]表示从l[s]到r[s]中还有多少空格可以放入(l[s]表示这段线段的左端点，r[s]表示这段线段的右端点)
当要插入到当前线段的第i个位置时，其实并不一定能插到i的位置，因为如果从起点到i上已经有点了，那么表示这点必须得后退，且出现一个点后退一步，且后退途中遇到新的点又得多后退一步。
到底是插入到左段还是右段 如果i<=num[2*s] （插入点的位置小于左段可插入的个数）,那么就插入左段，否则插入右段且更新插入位置，i变成i-(cntleft-cnthave) 或者i+cnthave-cntleft其中cntleft表示左端的点个数cnthave表示左端有多少点已经插入了。 这个是用线段树的关键所在，可以举几个例子推一下。
#include <iostream>
#include <stdio.h>
#include <string.h>
#include <string>
#include <algorithm>
#include <math.h>
#include <stdlib.h>
using namespace std;
#define N 200200 int n;
int gp[N],gv[N];
int l[*N],r[*N],num[*N];
int ans[N]; void build(int tl,int tr,int s)
{
l[s]=tl;
r[s]=tr;
if(tl==tr)
{
num[s]=;
return ;
}
int mid=(tl+tr)/;
build(tl,mid,*s);
build(mid+,tr,*s+);
num[s]=num[*s]+num[*s+];
} void update(int x,int w,int s)
{
if(l[s]==r[s])
{
ans[l[s]]=w;
num[s]=;
return ;
}
if(x<=num[*s])//左段又足够的空间，且要插入的位置比较靠前
update(x,w,*s);
else //左段不够，必须得到右边
update(x-num[*s],w,*s+);
num[s]--;
} int main()
{
while(scanf("%d",&n)!=EOF)
{
memset(num,,sizeof(num));
build(,n,);
for(int i=;i<=n;i++)
scanf("%d%d",gp+i,gv+i);
for(int i=n;i>=;i--)
{
update(gp[i]+,gv[i],);
}
for(int i=;i<n;i++)
printf("%d ",ans[i]);
printf("%d\n",ans[n]); }
return ;
}