【HDU】3727 Jewel

操作：

1，从数列结尾插入一个数。

2，查询区间第k小。

3，查询一个数在当前序列是第几小。

4，查询当前序列第k小。

1，离线。因为结尾插入一个数并不会对当前查询的区间造成影响。

2和4，划分树。

3，其实就是划分树的逆过程。

划分树就是二分一个区间，把小于等于区间中心的数放到左边，否则放到右边。

同时还需要记录一个位置，在它位置之前（包括它的位置），有多少个被放到了左区间。

当完全递归到区间长度是1时，就把一个数列排好序了。

  1 #include<cstdio>
  2 #include<algorithm>
  3 #define MAXM 20
  4 #define MAXN 300010
  5 typedef long long LL;
  6 using namespace std;
  7 struct node {
  8     int kind;
  9     int x, st, nd;
 10 };
 11 node p[MAXN];
 12 int tree[MAXM][MAXN], num[MAXM][MAXN], sorted[MAXN];
 13 void Build(int depth, int L, int R) {
 14     if (L == R)
 15         return;
 16     int same, mid, i, left, right;
 17     mid = (L + R) >> 1;
 18     same = mid - L + 1;
 19     left = L;
 20     right = mid + 1;
 21     for (i = L; i <= R; i++) {
 22         if (tree[depth][i] < sorted[mid])
 23             same--;
 24     }
 25     for (i = L; i <= R; i++) {
 26         if (tree[depth][i] < sorted[mid])
 27             tree[depth + 1][left++] = tree[depth][i];
 28         else if (tree[depth][i] == sorted[mid] && same) {
 29             tree[depth + 1][left++] = tree[depth][i];
 30             same--;
 31         } else
 32             tree[depth + 1][right++] = tree[depth][i];
 33         num[depth][i] = num[depth][L - 1] + left - L;
 34     }
 35     Build(depth + 1, L, mid);
 36     Build(depth + 1, mid + 1, R);
 37 }
 38 int Kth(int depth, int L, int R, int x, int y, int k) {
 39     if (L == R)
 40         return tree[depth][L];
 41     int mid, left, pre;
 42     mid = (L + R) >> 1;
 43     left = num[depth][y] - num[depth][x - 1];
 44     pre = num[depth][x - 1] - num[depth][L - 1];
 45     if (left >= k)
 46         return Kth(depth + 1, L, mid, L + pre, L + pre + left - 1, k);
 47     else {
 48         k -= left;
 49         pre = x - L - pre;
 50         left = y - x + 1 - left;
 51         return Kth(depth + 1, mid + 1, R, mid + pre + 1, mid + pre + left, k);
 52     }
 53 }
 54 int Value(int depth, int L, int R, int x, int y, int val) {
 55     if (L == R)
 56         return 1;
 57     int mid, pre, left;
 58     mid = (L + R) >> 1;
 59     left = num[depth][y] - num[depth][x - 1];
 60     pre = num[depth][x - 1] - num[depth][L - 1];
 61     if (val <= sorted[mid])
 62         return Value(depth + 1, L, mid, L + pre, L + pre + left - 1, val);
 63     else {
 64         pre = x - L - pre;
 65         return left
 66                 + Value(depth + 1, mid + 1, R, mid + 1 + pre,
 67                         mid + pre + y - x + 1 - left, val);
 68     }
 69 }
 70 int main() {
 71     char cmd[10];
 72     int ca = 1;
 73     int n, cnt, q, i;
 74     LL ans1, ans2, ans3;
 75     while (~scanf("%d", &q)) {
 76         ans1 = ans2 = ans3 = 0;
 77         for (i = n = 0; i < q; i++) {
 78             scanf(" %s", cmd);
 79             if (cmd[0] == 'I') {
 80                 p[i].kind = 0;
 81                 scanf("%d", &p[i].x);
 82                 n++;
 83                 sorted[n] = tree[0][n] = p[i].x;
 84             } else {
 85                 p[i].kind = cmd[6] - '0';
 86                 if (p[i].kind == 1)
 87                     scanf("%d%d%d", &p[i].st, &p[i].nd, &p[i].x);
 88                 else
 89                     scanf("%d", &p[i].x);
 90             }
 91         }
 92         sort(sorted + 1, sorted + n + 1);
 93         Build(0, 1, n);
 94         for (i = cnt = 0; i < q; i++) {
 95             if (p[i].kind == 0)
 96                 cnt++;
 97             else if (p[i].kind == 1)
 98                 ans1 += Kth(0, 1, n, p[i].st, p[i].nd, p[i].x);
 99             else if (p[i].kind == 2)
100                 ans2 += Value(0, 1, n, 1, cnt, p[i].x);
101             else
102                 ans3 += Kth(0, 1, n, 1, cnt, p[i].x);
103         }
104         printf("Case %d:\n", ca++);
105         printf("%I64d\n%I64d\n%I64d\n", ans1, ans2, ans3);
106     }
107     return 0;
108 }