解題區/解題區 - Zerojudge

d476. 區間查詢

contents

  1. 1. Problem
  2. 2. Sample Input
  3. 3. Sample Output
  4. 4. Solution
    1. 4.1. 前言
    2. 4.2. 開始
      1. 4.2.1. 應用

Problem

一個長度為 n 的序列，支持兩種操作：

  1. 输出 $[A, B]$ 區間第 k 小的數 (從小到大排序後第 k 個)
  2. 修改第 I 個數為 W

Sample Input

1
2
3
4
5
5 3
1 2 3 4 5
Q 1 4 2
C 2 5
Q 1 4 2

Sample Output

1
2
2
3

Solution

前言

在討論用一些雜七雜八的樹類結構去跟莫隊算法搏鬥之餘，用了轉幾何方向去兜資料結構，隨後發現題目尋找的是 unique 而非計數，因此很多想法就垮台，當然出成另一道題目也是不錯。決定尋找其他想法！

開始

整體二分是什麼呢？假設操作只有修改、詢問，不包含插入、刪除，而且詢問是一個數值結果，這個數值結果可以藉由二分 + 掃描來完成，那就可以使用整體二分來離線支持。

對答案值域分治，將相關操作分治在一起，同時要保留順序性，分治過程中會不斷地累加每一個詢問的掃描數值，最後滿溢時紀錄答案。每一個操作最多在 $\log \text{MAXV}$ 層計算，因此複雜度是 $O(Q \log \text{MAXV})$。

好處是可以用常數較低的結構，所以會比較快？

應用

這一道經典題有很多作法，如持久化線段樹、塊狀鏈表、歸併樹、劃分樹、 … 等。其中能支持修改的有塊狀鏈表、複雜的持久化線段樹 (主席樹)。

帶修改的區間 K 小，概略說明二分答案 $x$，然後去查找小於等於 $x$ 的數字在區間 $[l, r]$ 內出現的次數是否大於等於 $K$。然後修改元素有加入跟移除，二分答案 mid，要將加入、移除會影響的 $A[i] \le mid$，加入或移除時對該數字的索引值 $i$ 建造統計方案。

對於(位置, 值) $\left \langle i, A[i] \right \rangle$ 來說，一開始的前 $N$ 個操作是加入 $\left \langle i, A[i] \right \rangle$，二分答案時，用一個 binary indexed tree 去維護 index 的個數，也就是說，對於修改元素 $\left \langle i, A[i] \right \rangle$ 相當於在二分答案 mid 時，插入 BIT.add(i, 1)，那對於區間詢問，相當於查找 BIT.query([l, r]) 如此一來就能知道區間 $[l, r]$ 在 mid 以內有幾個數字符合。

假設計數大於 k，詢問往左放，反之扣除已知 mid 以內的數量，詢問往右放，如此一來就完成了。

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
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
#include <bits/stdc++.h> 
using namespace std;
const int MAXQ = 65536;
const int MAXN = 65536;
const int INF = 0x3f3f3f3f;
class Offline {
public:
    struct Event {
        int x, y, k, qtype, qid;
        int calc; //
        Event(int a = 0, int b = 0, int c = 0, int d = 0, int e = 0, int f = 0):
            x(a), y(b), k(c), qtype(d), qid(e), calc(f) {}
    };
    vector<Event> event;
    int N, ret[MAXQ];
    void init(int N) {
        this->N = N;
        event.clear();
    }
    void addEvent(int qtype, int qid, int x, int y, int k) {
        event.push_back(Event(x, y, k, qtype, qid));
    }
    void run() {
        DC(0, event.size()-1, 0, INF);
    }
private:
    // buffer
    int buf[MAXQ];
    Event ebuf1[MAXQ], ebuf2[MAXQ];
    // binary indexed tree
    int bit[MAXN];
    void add(int x, int val) {
        while (x <= N) {
            bit[x] += val;
            x += (x)&(-x);
        }
    }
    int query(int x) {
        int ret = 0;
        while (x) {
            ret += bit[x];
            x -= (x)&(-x);
        }
        return ret;
    }
    void DC(int q_l, int q_r, int val_l, int val_r) {
        if (q_l > q_r)	return ;
        if (val_l == val_r) {	// find
            for (int i = q_l; i <= q_r; i++)
                if (event[i].qtype == 2)
                    ret[event[i].qid] = val_l;
            return ;
        }
        int mid = (val_l + val_r)/2;
        for (int i = q_l; i <= q_r; i++) {
            if (event[i].qtype == 0 && event[i].y <= mid)
                add(event[i].x, 1);
            else if (event[i].qtype == 1 && event[i].y <= mid)
                add(event[i].x, -1);
            else if (event[i].qtype == 2)
                buf[i] = query(event[i].y) - query(event[i].x-1);
        }
        for (int i = q_l; i <= q_r; i++) { // resume
            if (event[i].qtype == 0 && event[i].y <= mid)
                add(event[i].x, -1);
            else if (event[i].qtype == 1 && event[i].y <= mid)
                add(event[i].x, 1);
        }
        int lidx = 0, ridx = 0;
        for (int i = q_l; i <= q_r; i++) {
            if (event[i].qtype == 0 || event[i].qtype == 1) {
                if (event[i].y <= mid)
                    ebuf1[lidx++] = event[i];
                else
                    ebuf2[ridx++] = event[i];
            } else {
                if (event[i].calc + buf[i] > event[i].k - 1)
                    ebuf1[lidx++] = event[i];
                else {
                    event[i].calc += buf[i];
                    ebuf2[ridx++] = event[i];
                }
            }
        }
        for (int i = 0; i < lidx; i++)
            event[q_l+i] = ebuf1[i];
        for (int i = 0; i < ridx; i++)
            event[q_l+lidx+i] = ebuf2[i];
        DC(q_l, q_l+lidx-1, val_l, mid);
        DC(q_l+lidx, q_r, mid+1, val_r);
    }
} off;
int main() {
    int n, m, x, y, k, v;
    int A[65536];
    char cmd[10];
    while (scanf("%d %d", &n, &m) == 2) {
        off.init(n);
        // qtype 0:add, 1:remove, 2: query
        for (int i = 1; i <= n; i++) {
            scanf("%d", &A[i]);
            off.addEvent(0, 0, i, A[i], 0);
        }
        
        int qid = 0;
        for (int i = 0; i < m; i++) {
            scanf("%s", cmd);
            if (cmd[0] == 'Q') {
                scanf("%d %d %d", &x, &y, &k);
                off.addEvent(2, qid++, x, y, k);
            } else {
                scanf("%d %d", &x, &v);
                off.addEvent(1, 0, x, A[x], 0);
                off.addEvent(0, 0, x, v, 0);
                A[x] = v;
            }
        }
        
        off.run();		
        for (int i = 0; i < qid; i++)
            printf("%d\n", off.ret[i]);
    }
    return 0;
}