題目鏈接：[點擊打開鏈接](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; } ~~~