ZJOI 第K大数查询

发表于 | 阅读数

给定$n$个空集合，有$2$操作。

  • 在$[l,r]$集合中加入$x$,$|x|\leq n$

  • 查询$[l,r]$集合中所有元素的第$k$大,$k\leq 2^{63}$

  • 注意是第$k$大

权值线段树套区间线段树

考虑在权值线段树二分寻找答案时，可以在动态在每一个点建立区间选段树$sum=query(tree[rs],ql,qr)$,若$k<=sum$,往右跳，反之往左挑。（$n\log^2 n$常数，内存过大，开$O2$才过得去）。

树状数组套主席树

考虑之前求第$k$大时主席树的建立。通过对比$tr[ql],tr[qr]$,这两个主席树从而确定答案，而这次要通过$tr[ql,qr]$,这些主席树确定答案。考虑吧用树状数组差分维护区间修改，区间查询。

整体二分

整体二分模版题，把树状数组的修改查询，改成线段树的，或则差分树状数组。

权值线段树套区间线段树 
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
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
#include <iostream>
#include <cstdio>
#include <algorithm>
#include <queue>
#include <cmath>
#include <cstring>
#include <vector>
#include <map>
using namespace std;
typedef long long ll;
#define ls tr[pos].l
#define rs tr[pos].r
const int N = 5e4 + 10;
const int mod = 1e9 + 7;
struct xi
{
    int l, r;
} tree[N * 400];
ll sum[N * 400];
int tt[N][4], te[N], num, li[N], tcnt, ti[N][2];
int lowbit(int x)
{
    return (-x) & x;
}
void add(int &pos, int x, int w, int l = 1, int r = num)
{
    if (!pos)
        pos = ++tcnt;
    sum[pos] += w;
    if (l == r)
        return;
    int mid = (l + r) >> 1;
    if (x <= mid)
        add(tree[pos].l, x, w, l, mid);
    else
    {
        add(tree[pos].r, x, w, mid + 1, r);
    }
}
int query(ll k, int x, int y, int l = 1, int r = num)
{
    if (l == r)
        return l;
    ll R = 0, L = 0;
    //cout << te[0] << " " << te[1] << " " << te[2] << " " << te[3] << endl;
    for (int i = 1; i <= te[0]; i++)
        R -= 1ll * (x + 1) * sum[tree[tt[i][0]].r]; //ti[0]维护差分(x+1)*(d[1]+d[2]...d[x])
    for (int i = 1; i <= te[1]; i++)
        R += 1ll * (y + 1) * sum[tree[tt[i][1]].r];
    for (int i = 1; i <= te[2]; i++) // ti[1维护(1*d[1]-2*d[2]...x*d[x])
        L -= 1ll * sum[tree[tt[i][2]].r];
    for (int i = 1; i <= te[3]; i++)
        L += 1ll * sum[tree[tt[i][3]].r];
    ll res = R - L;
    //cout << x << " " << y << " " << res << endl;
    int mid = (l + r) >> 1;
    if (k <= res)
    {
        for (int i = 1; i <= te[0]; i++)
            tt[i][0] = tree[tt[i][0]].r;
        for (int i = 1; i <= te[1]; i++)
            tt[i][1] = tree[tt[i][1]].r;
        for (int i = 1; i <= te[2]; i++) // ti[1维护(1*d[1]-2*d[2]...x*d[x])
            tt[i][2] = tree[tt[i][2]].r;
        for (int i = 1; i <= te[3]; i++)
            tt[i][3] = tree[tt[i][3]].r;
        return query(k, x, y, mid + 1, r);
    }

    else
    {
        for (int i = 1; i <= te[0]; i++)
            tt[i][0] = tree[tt[i][0]].l;
        for (int i = 1; i <= te[1]; i++)
            tt[i][1] = tree[tt[i][1]].l;
        for (int i = 1; i <= te[2]; i++) // ti[1维护(1*d[1]-2*d[2]...x*d[x])
            tt[i][2] = tree[tt[i][2]].l;
        for (int i = 1; i <= te[3]; i++)
            tt[i][3] = tree[tt[i][3]].l;
        return query(k - res, x, y, l, mid);
    }
}
int pre_query(int l, int r, ll k)
{
    for (int i = 0; i < 4; i++)
        te[i] = 0;

    l--;
    int x = l, y = r;
    while (l)
    {
        tt[++te[0]][0] = ti[l][0];
        tt[++te[2]][2] = ti[l][1];
        l -= lowbit(l);
    }
    while (r)
    {
        tt[++te[1]][1] = ti[r][0];
        tt[++te[3]][3] = ti[r][1];
        r -= lowbit(r);
    }

    return li[query(k, x, y)];
}
int n;
void update(int l, int r, int x)
{
    //cout<<x<<endl;
    r++;
    int rr = r;
    int ll = l;
    while (r <= n)
    {
        add(ti[r][0], x, -1);
        add(ti[r][1], x, -rr);
        r += lowbit(r);
    }
    while (l <= n)
    {
        //cout << l << endl;
        add(ti[l][0], x, 1);
        add(ti[l][1], x, ll);
        l += lowbit(l);
    }
    //cout << ti[2][0] << endl;
}
struct node
{
    int op, l, r;
    ll k;
} q[N];
int m;
int main()
{
    scanf("%d%d", &n, &m);
    for (int i = 1; i <= m; i++)
    {
        scanf("%d%d%d%lld", &q[i].op, &q[i].l, &q[i].r, &q[i].k);
        if (q[i].op == 1)
            li[++num] = q[i].k;
    }
    sort(1 + li, li + 1 + num);
    num = unique(1 + li, li + 1 + num) - li - 1;
    for (int i = 1; i <= m; i++)
        if (q[i].op == 1)
            q[i].k = lower_bound(1 + li, 1 + li + num, q[i].k) - li;

    for (int i = 1; i <= m; i++)
    {
        if (q[i].op == 1)
            update(q[i].l, q[i].r, q[i].k);
        else
        {
            printf("%d\n", pre_query(q[i].l, q[i].r, q[i].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
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
#include <iostream>
#include <cstdio>
#include <algorithm>
#include <queue>
#include <cmath>
#include <cstring>
#include <vector>
#include <map>
using namespace std;
typedef long long ll;
#define ls tr[pos].l
#define rs tr[pos].r
const int N = 5e4 + 10;
const int mod = 1e9 + 7;
struct segtree
{
    int l, r, lazy;
    ll sum;
} tr[N * 32 * 20];
int li[N], tcnt, num, n, ti[N << 2];
void pushup(int pos)
{
    tr[pos].sum = tr[ls].sum + tr[rs].sum;
}
void pushdown(int pos, int l, int r)
{
    int v = tr[pos].lazy, mid = (l + r) >> 1;

    if (v)
    {
        if (!tr[pos].l)
            tr[pos].l = ++tcnt;
        if (!tr[pos].r)
            tr[pos].r = ++tcnt;
        tr[ls].sum += v * (mid - l + 1);
        tr[rs].sum += v * (r - mid);
        tr[ls].lazy += v;
        tr[rs].lazy += v;
        tr[pos].lazy = 0;
    }
}
int add(int pos, int ql, int qr, int l = 1, int r = n)
{
    if (!pos)
        pos = ++tcnt;
    if (ql <= l && r <= qr)
    {
        tr[pos].lazy++;
        tr[pos].sum += (r - l + 1);
        return pos;
    }
    pushdown(pos, l, r);
    int mid = (l + r) >> 1;
    if (ql <= mid)
        tr[pos].l = add(tr[pos].l, ql, qr, l, mid);
    if (qr > mid)
        tr[pos].r = add(tr[pos].r, ql, qr, mid + 1, r);
    //tr[pos].sum = tr[ls].sum + tr[rs].sum;
    pushup(pos);
    return pos;
}
ll calc(int pos, int ql, int qr, int l = 1, int r = n)
{
    if (!pos)
        return 0;
    if (ql <= l && r <= qr)
    {
        return tr[pos].sum;
    }
    pushdown(pos, l, r);
    int mid = (l + r) >> 1;
    ll res = 0;
    if (ql <= mid)
        res += calc(tr[pos].l, ql, qr, l, mid);
    if (qr > mid)
        res += calc(tr[pos].r, ql, qr, mid + 1, r);
    return res;
}
void update(int ql, int qr, int x, int pos = 1, int l = 1, int r = num)
{
    ti[pos] = add(ti[pos], ql, qr);
    if (l == r)
        return;
    int mid = (l + r) >> 1;
    if (x <= mid)
        update(ql, qr, x, pos << 1, l, mid);
    else
        update(ql, qr, x, pos << 1 | 1, mid + 1, r);
}

int query(int ql, int qr, ll k, int pos = 1, int l = 1, int r = num)
{
    if (l == r)
        return l;
    ll sum = calc(ti[pos << 1 | 1], ql, qr);
    // cout << pos << " " << ql << " " << qr << " " << sum << "---" << tr[2].lazy << endl;
    int mid = (l + r) >> 1;
    if (k <= sum)
        return query(ql, qr, k, pos << 1 | 1, mid + 1, r);
    else
        return query(ql, qr, k - sum, pos << 1, l, mid);
}
struct node
{
    int op, l, r;
    ll k;
} q[N];
int m;
int main()
{
    scanf("%d%d", &n, &m);
    for (int i = 1; i <= m; i++)
    {
        scanf("%d%d%d%lld", &q[i].op, &q[i].l, &q[i].r, &q[i].k);
        if (q[i].op == 1)
            li[++num] = q[i].k;
    }
    sort(1 + li, li + 1 + num);
    num = unique(1 + li, li + 1 + num) - li - 1;
    for (int i = 1; i <= m; i++)
        if (q[i].op == 1)
            q[i].k = lower_bound(1 + li, 1 + li + num, q[i].k) - li;
    //cout << num << endl;
    for (int i = 1; i <= m; i++)
    {
        if (q[i].op == 1)
            update(q[i].l, q[i].r, q[i].k);
        else
        {
            printf("%d\n", li[query(q[i].l, q[i].r, q[i].k)]); //这里是第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
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
127
128
129
130
131
132
133
134
135
136
137
138
#include <iostream>
#include <cstdio>
#include <algorithm>
#include <queue>
#include <cmath>
#include <cstring>
#include <vector>
#include <map>
using namespace std;
typedef long long ll;
#define ls tr[pos].l
#define rs tr[pos].r
const int N = 1e5 + 10;
const int mod = 1e9 + 7;
struct node
{
    int op, l, r, id;
    ll k;
} q[N], ql[N], qr[N];
int ans[N];
struct seg
{
    ll sum;
    ll lazy;
} tree[N << 2];
int n;
void pushdown(int pos, int l, int r)
{
    if (tree[pos].lazy)
    {
        int mid = (l + r) >> 1;
        int w = tree[pos].lazy;
        tree[pos << 1].lazy += w;
        tree[pos << 1 | 1].lazy += w;
        tree[pos << 1].sum += 1ll * w * (mid - l + 1);
        tree[pos << 1 | 1].sum += 1ll * w * (r - mid);
        tree[pos].lazy = 0;
    }
}
void pushup(int pos)
{
    tree[pos].sum = tree[pos << 1].sum + tree[pos << 1 | 1].sum;
}
void update(int ql, int qr, int w, int pos, int l, int r)
{
    if (ql <= l && r <= qr)
    {
        tree[pos].lazy += w;
        tree[pos].sum += 1ll * (r - l + 1) * w;
        return;
    }
    pushdown(pos, l, r);
    int mid = (l + r) >> 1;
    if (ql <= mid)
        update(ql, qr, w, pos << 1, l, mid);
    if (qr > mid)
        update(ql, qr, w, pos << 1 | 1, mid + 1, r);
    pushup(pos);
}
ll query(int ql, int qr, int pos, int l, int r)
{
    if (ql <= l && r <= qr)
    {
        return tree[pos].sum;
    }
    pushdown(pos, l, r);
    ll res = 0;
    int mid = (l + r) >> 1;
    if (ql <= mid)
        res += query(ql, qr, pos << 1, l, mid);
    if (qr > mid)
        res += query(ql, qr, pos << 1 | 1, mid + 1, r);

    return res;
}
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 == 2)
                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].k > mid)
            {
                update(q[i].l, q[i].r, 1, 1, 1, n);
                qr[++cntr] = q[i];
            }
            else
            {
                ql[++cntl] = q[i];
            }
        }
        else
        {
            ll sum = query(q[i].l, q[i].r, 1, 1, n);

            if (q[i].k <= sum)
                qr[++cntr] = q[i];
            else
                ql[++cntl] = q[i], ql[cntl].k -= sum;
        }
    }
    for (int i = 1; i <= cntr; i++)
        if (qr[i].op == 1)
            update(qr[i].l, qr[i].r, -1, 1, 1, n);
    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 m, Q;
int main()
{
    scanf("%d%d", &n, &m);
    for (int i = 1; i <= m; i++)
    {
        scanf("%d%d%d%lld", &q[i].op, &q[i].l, &q[i].r, &q[i].k);
        if (q[i].op == 2)
            q[i].id = ++Q;
    }
    solve(-n, n, 1, m);
    for (int i = 1; i <= Q; i++)
    {
        printf("%d\n", ans[i]);
    }
}