題目：Buy Tickets

#include <stdio.h> #define N 200010#define lson l,m,rt<<1 #define rson m+1,r,rt<<1|1int tree[N<<2]; int pos[N],val[N],ans[N]; int id;void Build(int l,int r,int rt) {tree[rt]=r-l+1;if(l==r)return;int m=(l+r)>>1;Build(lson);Build(rson); }void Update(int p,int l,int r,int rt) {tree[rt]--;if(l==r){id=r;return;}int m=(l+r)>>1;if(tree[rt<<1]>=p)Update(p,lson);else{p-=tree[rt<<1];Update(p,rson);} }int main() {int n,i;while(~scanf("%d",&n)){Build(1,n,1);for(i=1;i<=n;i++)scanf("%d%d",pos+i,val+i);for(i=n;i>=1;i--){Update(pos[i]+1,1,n,1);ans[id]=val[i];}for(i=1;i<=n;i++)printf("%d%c",ans[i],n==i? '\n':' ');}return 0; }

?

總結(jié)

以上是生活随笔為你收集整理的POJ2828线段树 插队(单点更新)的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔推薦給好友。