整体二分

发表于 | 阅读数

浅谈整体二分

查询第$k$大

正常我们的想法主席树。但是如果对一个询问，我们可以这样操作：将$[ql,qr]$区间内数加入权值树状数组。二分$ans\in[-l,r]$,$p=num[i\leq mid]\leq k$,则在左区$[l,mid]$间的第$k$,不然在右区$[mid+1,r]$间的第$p-k$。

但是如果对于$q$个询问需要新建树状数组，复杂度就$O(qn\log n)$。会发现中间有很多重复的过程。

  • 我们只需要将那些$val\leq mid$的进行加入。之后只会对所有需要进入$[l,mid]$产生影响。将这些操作划分左边的操作。
  • 而那些$val>mid$或者进入左区间的查询，之后与其无关，只需要划分为右边的操作
  • 保证时间顺序不改变

整体二分 $[l,r,L,R]$ 表示答案在 $[l,r]$ 中，与操作 $[L,R]$ 有关（操作 $[L,R]$ 不一定对应原来 $[L,R]$ 的操作）

  • 动态第$k$大,就是将它删除再插入，整体二分保证了时间的顺序一致

复杂度都为$O(n\log^2 n)$,但是比树套树常数小。

静态第$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
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
#include <iostream>
#include <cstdio>
#include <algorithm>
#include <queue>
#include <cmath>
#include <cstring>
#include <vector>
#include <map>
using namespace std;
#define lowbit(x) (-x) & x
typedef long long ll;
const int N = 2e5 + 10;
const int mod = 1e9 + 7;
const int inf = 1e9 + 100;
int tr[N], n;
int query(int x)
{
    int res = 0;
    while (x)
    {
        res += tr[x];
        x -= lowbit(x);
    }
    return res;
}
void update(int x, int w)
{
    while (x <= n)
    {
        tr[x] += w;
        x += lowbit(x);
    }
}

struct node
{
    int op, l, r, k, id;
} q[N << 1], ql[N << 1], qr[N << 1];
int ans[N];

void solve(int l, int r, int L, int R)
{
    if (L > R)
        return;
    if (l == r)
    {
        for (int i = L; i <= R; i++)
            if (q[i].op == 0)
                ans[q[i].id] = l;
        return;
    }
    int cntl = 0, cntr = 0;
    int mid = (l + r) >> 1;
    for (int i = L; i <= R; i++)
    {
        if (q[i].op == 1)
        {
            if (q[i].l <= mid)
            {
                int pos = q[i].id;
                update(pos, 1);
                ql[++cntl] = q[i];
            }
            else
                qr[++cntr] = q[i];
        }
        else
        {
            int sum = query(q[i].r) - query(q[i].l - 1);
            if (q[i].k <= sum)
                ql[++cntl] = q[i];
            else
                q[i].k -= sum, qr[++cntr] = q[i];
        }
    }
    for (int i = 1; i <= cntl; i++)
        if (ql[i].op == 1)
            update(ql[i].id, -1);
    for (int i = 1; i <= cntl; i++)
        q[L + i - 1] = ql[i];
    for (int i = 1; i <= cntr; i++)
        q[L + cntl + i - 1] = qr[i];
    solve(l, mid, L, L + cntl - 1);
    solve(mid + 1, r, L + cntl, R);
}
int cnt, m, a[N], num, li[N];
int main()
{
    scanf("%d%d", &n, &m);
    for (int i = 1; i <= n; i++)
    {
        scanf("%d", &a[i]);
        li[++num] = a[i];
        // q[++cnt] = (node){1, a[i], 0, 0, i};
    }
    sort(li + 1, li + num + 1);
    num = unique(li + 1, li + 1 + num) - li - 1;
    for (int i = 1; i <= n; i++)
    {
        a[i] = lower_bound(1 + li, 1 + li + num, a[i]) - li;
        q[++cnt] = (node){1, a[i], 0, 0, i};
    }
    for (int i = 1; i <= n; i++)
    {
        ++cnt;
        scanf("%d%d%d", &q[cnt].l, &q[cnt].r, &q[cnt].k);
        q[cnt].id = i;
    }
    solve(1, num, 1, cnt);
    for (int i = 1; i <= m; i++)
        printf("%d\n", li[ans[i]]);
}