/* //不想写题解了,就直接把人家的粘过来了 线段树节点中保存这一段中的空位数，然后倒序对pos插入： 例如： 0 77 1 51 1 33 2 69 先取： 2 69 —— —— —69— —— （需要前面有3个空位才能插入） 然后取： 1 33 —— —33— —69— —— （需要前面有2个空位才能插入） 然后取： 1 51 —— —33— —69— —51— （需要前面有2个空位才能插入） 前面只有1个空位 故插入后面空格 然后取： 0 77 —77— —33— —69— —51— （需要前面有1个空位才能插入）#include<cstdio>#include<cstring>#include<cstdlib>#include<iostream>#include<algorithm>using namespace std;#define maxn 200005#define lson l,m,rt<<1#define rson m+1,r,rt<<1|1int sum[maxn<<2],a,b;struct qw{int a,val,num;}an[maxn];int cmp(struct qw x,struct qw y){return x.num<y.num;}void push_up(int rt){sum[rt]=sum[rt<<1]+sum[rt<<1|1];}void build(int l,int r,int rt){if(l==r){sum[rt]=1; return;}int m=(l+r)>>1;build(lson); build(rson);push_up(rt);}void update(int p,int l,int r,int rt){if(l==r){sum[rt]=0; return;}int m=(l+r)>>1;if(p<=m) update(p,lson);else update(p,rson);push_up(rt);}int q;//二分查找q,使得sum(1,q)==p; i就是此点要插入的位置void bina_query(int p,int l,int r,int rt){if(l==r&&p==sum[rt]){//刚开始少了(l==r)这个条件,因为必须是确定到某点之后恰好为p,所以不加会错q=r; return;}int m=(l+r)>>1;if(p<=sum[rt<<1]) bina_query(p,lson);else bina_query(p-sum[rt<<1],rson);}int main(){int i,j,n;while(~scanf("%d",&n)){build(1,n,1);for(i=1;i<=n;i++) scanf("%d%d",&an[i].a,&an[i].val);//倒着插入for(i=n;i>=1;i–){bina_query(an[i].a+1,1,n,1);an[i].num=q;update(q,1,n,1);}sort(an+1,an+1+n,cmp);for(i=1;i<n;i++) printf("%d ",an[i].val);printf("%d\n",an[i].val);}return 0;} 由于某个人想要插入posi位置，插入后他就在posi位置上了，但是可能其他人会插到他前面来，他的位置就会变成[在他后面且插在他位置及以前的人数]+posi 如果这样就开始求了，当然用线段树就可以做了，就跟求逆序数对一样。 但是我们可以反着来考虑，只要从后面开始站，假设后面的人都已经站在正确的位置上了，那么到那个人站的时候，现在的位置上已经都是后面的那些人了， 只要数posi个空格，那那个人站的位置能确定了。确定之后就可以求下一个了，所以这个前提和结论都成立了。 所以我们只要从后面人站起，数posi个空格站上去就行了。 线段树的话跟求和线段树一样，初始化时全部初始化为1，，然后查找的时候可以“二分”查找*/
属于自己的不要放弃，已经失去的留作回忆。
