哎,线段树这个模型还真难转换过来,其实线段树只要明白了模型,然后什么都简单了。
题意:人们一个一个的来排队并将插队,按人到来的顺序给出每个人插队的位置(插在第几个人后面),并告知每个人的序号,输出最终队伍的情况,并且输出。
这题需要理解一个思想,你如果正着进行插队的话,完全不是一次更新就可以完成的,所以要反过来,倒着插入的位置便是他最后的位置,想不通的可以用笔模拟一下。
结构体需要定义4个值,l,r不用说,还有val和w,val是最后用来存储这个人的序号(只有单个人的结点才用),w用来存储这个区间还有的空位,讲到这里已经很简单了,速速AC吧。
#include<cstdio> #include<cstring> #include<iostream> #define L(u) (u<<1) #define R(u) (u<<1|1) using namespace std; const int N = 200001; struct Node{ int r,l,w,val; }; struct Data{ int pos,num; }; Data sta[N]; Node node[N<<2]; int n; bool flag; void pushUp(int u) { node[u].w = node[L(u)].w + node[R(u)].w; } void build(int u,int left,int right) { node[u].l = left,node[u].r = right; if(node[u].l==node[u].r) { node[u].w = 1; return; } int mid = (node[u].l+node[u].r)>>1; build(L(u),left,mid); build(R(u),mid+1,right); pushUp(u); } void upDate(int u,int p,int x) { if(node[u].l==node[u].r) { node[u].val = x; node[u].w = 0; return; } if(node[L(u)].w>p) { upDate(L(u),p,x); } else { upDate(R(u),p-node[L(u)].w,x); } pushUp(u); } void query(int u) { if(node[u].l==node[u].r) { if(flag) { printf("%d",node[u].val); flag = false; } else { printf(" %d",node[u].val); } return; } query(L(u)); query(R(u)); } int main(void) { while(~scanf("%d",&n)) { flag = true; for(int i=1;i<=n;++i) { scanf("%d %d",&sta[i].pos,&sta[i].num); } build(1,1,n); for(int i=n;i>=1;--i) { upDate(1,sta[i].pos,sta[i].num); } query(1); printf("\n"); } return 0; }