题目链接：[点击打开链接](http://poj.org/problem?id=2828) 题意：给n个人依次插队的情况， 要求求出最终的队伍情况。 该题可以用树状数组很方便的维护。 如果从前向后扫的话， 每次插队都会影响这个人后面的情况， 所以我们可以倒着进行， 那么最后一个人的位置就是最终位置， 对于前面的人的位置， 只受后面人的影响， 所以等价于其最终位置是第pos[i]+1个空位。   那么也就是说要快速的找到第pos[i]+1个空位。   显然， 这又可以用二分位置和树状数组维护的方法来优化算法。 细节参见代码： ~~~ #include<cstdio> #include<cstring> #include<algorithm> #include<iostream> #include<string> #include<vector> #include<stack> #include<bitset> #include<cstdlib> #include<cmath> #include<set> #include<list> #include<deque> #include<map> #include<queue> #define Max(a,b) ((a)>(b)?(a):(b)) #define Min(a,b) ((a)<(b)?(a):(b)) using namespace std; typedef long long ll; const double PI = acos(-1.0); const double eps = 1e-6; const int INF = 1000000000; const int maxn = 200000 + 10; int T,n,m,bit[maxn],ans[maxn]; struct node { int pre, v; }a[maxn]; int sum(int x) { int ans = 0; while(x > 0) { ans += bit[x]; x -= x & -x; } return ans; } void add(int x, int d) { while(x <= n) { bit[x] += d; x += x & -x; } } int main() { while(~scanf("%d",&n)) { memset(bit, 0, (n+1)*sizeof(bit[0])); for(int i=1;i<=n;i++) scanf("%d%d",&a[i].pre,&a[i].v); for(int i=n;i>=1;i--) { int l = 1, r = n, mid; while(r > l) { mid = (l + r) >> 1; if(mid - sum(mid) > a[i].pre) r = mid; else l = mid + 1; } ans[l] = a[i].v; add(l, 1); } printf("%d",ans[1]); for(int i=2;i<=n;i++) printf(" %d",ans[i]); printf("\n"); } return 0; } ~~~