题目链接 https://vjudge.net/problem/POJ-2828
题目大意
?? 有 n 个人, 依次给出这 n 个人进入队列时前面有多少人 p[i], 和它的权值 v[i], 求最终队列的权值序列.
解题思路
?? 用线段树维护一个数组, 最初全是 1, 代表每个位置有没有人. 从后往前推, 最后一个人的位置肯定是他最终的位置, 然后把他删去, 那么消去了最后一个人的影响, 倒数第二个人的位置肯定也是他的最终位置, 再把他删去... 判断每个 \(pos_i\) 直接在线段树上二分对应的位置即可.
代码
- const int maxn = 2e5+10;
- struct Tree {
- int sum, l, r;
- } tree[maxn<<2];
- int n, ans[maxn], a[maxn], b[maxn];
- void build(int rt, int l, int r) {
- tree[rt].l = l, tree[rt].r = r;
- if (l==r) {
- tree[rt].sum = 1; return;
- }
- int mid = (l+r)>>1;
- build(rt<<1, l, mid);
- build(rt<<1|1, mid+1, r);
- tree[rt].sum = tree[rt<<1].sum+tree[rt<<1|1].sum;
- }
- void update(int rt, int pos, int val) {
- if (tree[rt].l==tree[rt].r) {
- ans[tree[rt].l] = val;
- tree[rt].sum = 0; return;
- }
- if (tree[rt<<1].sum>=pos) update(rt<<1, pos, val);
- else update(rt<<1|1, pos-tree[rt<<1].sum, val);
- tree[rt].sum = tree[rt<<1].sum+tree[rt<<1|1].sum;
- }
- int main() {
- while(cin>> n) {
- build(1, 1, n);
- for (int i = 1; i<=n; i++) scanf("%d%d", &a[i], &b[i]);
- for (int i = n; i>=1; i--) update(1, a[i]+1, b[i]);
- for (int i = 1; i<=n; i++) printf(i==n ? "%d\n":"%d", ans[i]);
- }
- return 0;
- }
来源: http://www.bubuko.com/infodetail-3682978.html