POJ2828 Buy Tickets（树状数组高级应用：sumseek）

题目链接

题意：n 个人排队，接下来 n 行每行第一个数是这个人的位置，第二个数是他的 value（没卵用）。后来的人如果他的位置已经有人的话，所有他后面的人都向后移动 1，也就是插队的感觉。求最后这些人的顺序。

最后一个人的位置肯定不会变，因为是最后插入的，所以后来的人的位置只受前面的人影响，因此从后往前考虑的话，第 i 个人的位置就是第 pos+1 个空位。将树状数组初始化为 1，来人的话-1，用 sumseek 函数找到插入位置。

//寻找前缀和为k的第一个位置
int sumseek(int k){
    int ans = 0, sum = 0, i;
    for(i = 18; i >= 0; i--){
        ans += (1 << i);
        if (ans >= n || sum + a[ans] >= k) ans -= (1 << i);
        else sum += a[ans];
    }
    return ans+1;
}

第一次知道树状数组还可以这么玩。。

#include<cstdio>
#include<cstring>
#include<cmath>
#include<iostream>
#include<algorithm>
#include<vector>
#include<map>
#include<queue>
#include<stack>
#include<string>
using namespace std;
int n;
struct node{
    int pos, num;
}N[200005];

int a[200005];
int ans[200005];

int lowbit(int x){
    return x&(-x);
}

void add(int pos, int num){
    while(pos <= n){
        a[pos] += num;
        pos += lowbit(pos);
    }
}

int sum(int n){
    int sum = 0;
    while(n > 0){
        sum += a[n];
        n -= lowbit(n);
    }
    return sum;
}

int sumseek(int k){
    int ans = 0, sum = 0, i;
    for(i = 18; i >= 0; i--){
        ans += (1 << i);
        if (ans >= n || sum + a[ans] >= k) ans -= (1 << i);
        else sum += a[ans];
    }
    return ans+1;
}


int main(){
    //freopen("a.txt", "r", stdin);
    while(~scanf("%d", &n)){
        //memset(a, 0, sizeof(a));
        for(int i = 1; i <= n; i++){
            int w; scanf("%d %d", &w, &N[i].num);
            N[i].pos = w+1;
            add(i, 1);
        }

        for(int i = n; i >= 1; i--){
            int k = sumseek(N[i].pos);
            ans[k] =N[i].num;
            add(k, -1);
        }
        for(int i = 1; i <= n; i++){
            cout << ans[i];
            if(i!=n) cout << " ";
        }
        cout << endl;
    }
    return 0;
}

如果不知道 sumseek 函数的话，只能二分找到插入的位置了。