PKU 2828 Buy Tickets
英雄哪里出来发表于 2011-04-09 07:06:00
题目链接：http://poj.org/problem?id=2828
/**//*
题意： 给定N(1 <= N <= 200000)个整数对(A,B)，表示在A右边的位置插入一个B，经过N次操作后问最后的B序列的排列情况。题解： 树状数组 或者 线段树思路： 这题的数据量比较大，一开始可以模拟一下过程，但是直接暴力肯定是超时的，因为每次插入过程，这个位置的后面的元素必然是要顺序往后移动的。所以总的复杂度高达O(n^2)。 但是这个问题可以转化，我们这样考虑，对于任意两个整数对(A1,B1)和(A2,B2)保证(A1,B1)在(A2,B2)之前出现，如果A1小于A2，后面的整数对是不影响前面整数对的位置关系的，否则B1的位置必然要受到B2的影响而向后移动一位。 于是A1和A2之间就存在一个逆序关系，我们可以联想到树状数组求逆序数时候的做法，从后往前，对于最后一个数，它的位置就是An，因为之后没有插入数了，它已经稳定下来了，然后将这个位置插入到树状数组的相应位置去，每次扫描到当前数的时候二分枚举当前数前面有多少“空位”，空位的统计可以采用树状数组的成段求和，找到后将这个数插入，N次操作后答案就保存下来了。
*/
#include <iostream>using namespace std;#define maxn 200010int n;int c[maxn];struct point 
{ int A, B;}pt[maxn];int lowbit(int x) { return x & (-x);}void add(int pos) {
while(pos <= n) { c[pos] ++; pos += lowbit(pos);
}}int sum(int pos) { int s = 0; while(pos > 0) { s += c[pos]; pos -= lowbit(pos); } return s;}int ans[maxn];int main() { int i; while(scanf("%d", &n) != EOF) { for(i = 1; i <= n; i++) c[i] = 0; for(i = 1; i <= n; i++) { scanf("%d %d", &pt[i].A, &pt[i].B); pt[i].A ++; } for(i = n; i >= 1; i--) { int l = 1; int r = n; int as = 1; while(l <= r) { int m = (l + r) >> 1; if(m - sum(m) >= pt[i].A) { r = m - 1; as = m; }else l = m + 1; } ans[as] = pt[i].B; add(as); } for(i = 1; i <= n; i++) { if(i != 1) printf(" "); printf("%d", ans[i]); } puts(""); } return 0;}