|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 |
#include <iostream> #include <algorithm> #include <queue> #include <vector> #include <cstdlib> #include <cstdio> #include <string> #include <cstring> #include <ctime> #include <iomanip> #include <cmath> #include <set> #include <map> #include <list> #include <stack> using namespace std; #define MAXN 1100000 int tree[MAXN]; int M = 1; void tree_init(int num){ M = 1; for (; M < num; M <<= 1); memset(tree, 0, sizeof(int)*M*2+2); M--; } void tree_update(unsigned int nodeNum,int delta){ nodeNum += M; tree[nodeNum] += delta; while (nodeNum != 1) { nodeNum >>= 1; tree[nodeNum] = tree[nodeNum << 1] + tree[(nodeNum << 1) + 1]; } } void tree_build(int cnt){ for (int i = 1; i <= cnt; i++) { tree[M+i] = 1; } int cur = M+1; while (cur >>= 1) { for (int i = 0; i < cur; i++) { tree[cur+i] = tree[cur << 1] + tree[(cur << 1) + 1]; } } } int tree_insert(int arg,int cur){ while (cur <= M) { int lch = tree[cur << 1]; if (lch <= arg) { arg -= lch; cur <<= 1; cur++; }else{ cur <<= 1; } } tree_update(cur-M, -1); return cur-M; } int que[200005],sarg1[200005],sarg2[200005]; int main(){ int cnt; while (scanf(" %d",&cnt) != EOF) { tree_init(cnt); memset(que, 0, sizeof(int)*cnt+4); for (int i = 1; i <= cnt; i++) { scanf(" %d %d",&sarg1[i],&sarg2[i]); } tree_build(cnt); for (int i = cnt; i >= 1; i--){ int arg1 = sarg1[i],arg2 = sarg2[i]; que[tree_insert(arg1, 1)] = arg2; } for (int i = 1; i <= cnt; i++) { printf("%d",que[i]); if (i!=cnt) { printf(" "); } } printf("\n"); } return 0; } |
这个是灵活使用线段树了，把线段树当作路径，一边整理有多少个空位，一边按着这些数据快速地插入节点。
注意这个题正难则反的思想，反着来看这个请求序列，是可以做的，正着处理就坏事了，所以当卡题的时候不妨试一试把当前的思考／阅读方向反过来，也许会有灵感。
我已经很尽力地优化了，1600跑过，只能说那些几百跑过的大神真是强，无法比肩。
