解題區/解題區 - Zerojudge

a331. K-th Number

contents

  1. 1. Problem
  2. 2. Sample Input
  3. 3. Sample Output
  4. 4. Solution

Problem

You are working for Macrohard company in data structures department. After failing your previous task about key insertion you were asked to write a new data structure that would be able to return quickly k-th order statistics in the array segment.
That is, given an array a[1…n] of different integer numbers, your program must answer a series of questions Q(i, j, k) in the form: “What would be the k-th number in a[i…j] segment, if this segment was sorted?”
For example, consider the array a = (1, 5, 2, 6, 3, 7, 4). Let the question be Q(2, 5, 3). The segment a[2…5] is (5, 2, 6, 3). If we sort this segment, we get (2, 3, 5, 6), the third number is 5, and therefore the answer to the question is 5.

Sample Input

1
2
3
4
5
7 3
1 5 2 6 3 7 4
2 5 3
4 4 1
1 7 3

Sample Output

1
2
3
5
6
3

Solution

之前使用過塊狀鏈表、歸併樹來完成這一題，其中速度快 歸併樹 > 函數式線段樹 > 塊狀鏈表，空間消耗大小 函數式線段樹 > 歸併樹 > 塊狀鏈表。

現在學到了一種可持久化的數據精神，有一種為函數式線段樹，最簡單理解的就是採用修改不改值，而是增加新的節點，而每一次修改最多增加 O(n log n) (延著線段樹走訪路徑增加節點)

也就是說，每一次修改會根據前一次的 root 增加一個新的 root’，這是一個相當重要的一環，每一次修改會產生新的一棵線段樹，而這個新線段樹大部分節點會使用前一個線段樹的節點，因此只要針對走訪不影響的情況下，我們仍然會經過舊有的節點。

為了找到區間 K 大，使用函數式線段樹有點類似於掃描線算法，對於某個時間點依序將數字放進去，然後對於區間查詢 K 大的時候，相當於對某個時間點之間作減法運算。

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
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <algorithm>
#include <vector>
#include <map>
#include <assert.h>
using namespace std;
struct Node {
    int l, r, lson, rson;
    int sum;
} node[2097152];
int nodesize = 0;
int A[131072], B[131072], root[131072];
int build(int l, int r) {
    if (l > r)  return 0;
    int k = nodesize++;
    node[k].l = l, node[k].r = r, node[k].sum = 0;
    node[k].lson = node[k].rson = 0;
    if (l == r) return k;
    int m = (l + r)/2;
    node[k].lson = build(l, m);
    node[k].rson = build(m+1, r);
    return k;
}
int change(int p, int x, int val) {
    int k = nodesize++;
    node[k] = node[p];
    node[k].sum += val;
    if (node[k].l == node[k].r) return k;
    int m = (node[k].l + node[k].r)/2;
    if (x <= m)
        node[k].lson = change(node[p].lson, x, val);
    else
        node[k].rson = change(node[p].rson, x, val);
    return k;
}
int query(int tp, int tq, int k) {
    if (node[tp].l == node[tp].r)
        return node[tp].l;
    int t = node[node[tp].lson].sum - node[node[tq].lson].sum;
    if (k <= t)
        return query(node[tp].lson, node[tq].lson, k);
    else
        return query(node[tp].rson, node[tq].rson, k - t);
}
int main() {
    int n, m, x, y, k;
    while (scanf("%d %d", &n, &m) == 2) {
        map<int, int> R;
        for (int i = 1; i <= n; i++)
            scanf("%d", &A[i]), R[A[i]] = 0;
        
        int size = 0;
        for (map<int, int>::iterator it = R.begin(); it != R.end(); it++) {
            it->second = ++size;
            B[it->second] = it->first;        
        }
        
        nodesize = 1;
        root[0] = build(1, size);
        
        for (int i = 1; i <= n; i++) {
            A[i] = R[A[i]];
            root[i] = change(root[i-1], A[i], 1);
        }
        
        for (int i = 0; i < m; i++) {
            scanf("%d %d %d", &x, &y, &k);
            printf("%d\n", B[query(root[y], root[x-1], k)]);
        }
    }
    return 0;
}
/*
 7 3
 1 5 2 6 3 7 4
 2 5 3
 4 4 1
 1 7 3
 */