最近几天没怎么做线段树了，忙于消化新算法和比赛的题目。
正好比赛出了这道题，所以顺便做了这道题。
题目的大致意思：
现在有n个人，然后分别给出每个人所在的位置pos[i]与val[i]，然后最后让你输出它们所在的位置。
比如说样例：
40 771 511 332 690代表的是当前价值为77的人站在0th人的后面（第0个人就是卖票处）。
同理1代表的是当前价值为51的人站在1th人的后面
但是第三组样例就要注意了，这里会发生更新，也就是说现在33价值的人会站在1th人的后面，所以会把第二个人给挤掉。
同理，第四个人也是如此。
所以最后输出就是如图所示的了。
这里用到线段树的原因是：
我们要快速的找到每个人所在的位置，所以用线段树来定位比较方便。而且，这里还有一个技巧就是从后往前查找，这样子的话就能保证当前覆盖的一定是最新的。
查询的过程很巧妙，详细请参考代码：
#include<stdio.h>#include<string.h>#include<iostream>#include<algorithm>using namespace std;#define maxn 222222int ans[maxn],pos[maxn],val[maxn];struct node{int l,r;int sum;}tree[maxn*4];void pushup(int v){int temp=v<<1;tree[v].sum=tree[temp].sum+tree[temp+1].sum;}void build(int l,int r,int v){tree[v].l=l;tree[v].r=r;if(l==r){tree[v].sum=1;return ;}int mid=(l+r)>>1;int temp=v<<1;build(l,mid,temp);build(mid+1,r,temp+1);pushup(v);}void query(int t,int v,int cnt){if(tree[v].l==tree[v].r){//这里一开始写错了，写成了tree[v].l==t,其实这里查询的是最前的那个子节点就好了 ans[tree[v].l]=cnt;tree[v].sum–;//注意这里区间每次当找到了子节点说明找到了当前那个人的位置，，那么当前点的sum就要减1 return ;}int temp=v<<1;if(t<=tree[temp].sum) query(t,temp,cnt);else query(t-tree[temp].sum,temp+1,cnt);//这里要query(t-tree[temp].sum,temp+1,cnt),别忘了减掉左节点的sum值 pushup(v);}int main(){int n;while(~scanf("%d",&n)){memset(ans,0,sizeof(ans));memset(pos,0,sizeof(pos));memset(val,0,sizeof(val));for(int i=1;i<=n;i++){scanf("%d%d",&pos[i],&val[i]);}build(1,n,1);for(int i=n;i>=1;i–){query(pos[i]+1,1,val[i]);}for(int i=1;i<=n;i++){if(i!=n) printf("%d ",ans[i]);else printf("%d\n",ans[i]);}}}
版权声明：本文为博主原创文章，未经博主允许不得转载。
等待故人的归来。山上的树，大多数是松树比较突出。
