K大数查询

模板题

题目链接

因为有区间修改,所以外层建权值线段树,内层建区间树

处理修改:对所有包含c的外层树节点所对应的内层树的a~b区间+1

处理询问:在外层树上二分,若当前节点的右子树的内层树a~b区间和>c就往左子树走,否则往右


注意:

区间树要标记永久化,不然如果写的不够优秀会 MLE or TLE

此题luogu上时限只有1s,大部分代码包括本人代码会被卡常,获得0~100不等的分数。

在往左子树走时要减掉右子树a~b区间和带来的贡献


在具体实现的时候,我为了图方便用了指针namespace

如果你看不懂指针,可以往下翻,有无指针的代码

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
/*
Author: zxy_hhhh
date: 2018/12/01
*/
#include <algorithm>
#include <cctype>
#include <cmath>
#include <cstdio>
#include <cstring>
#define rep(x, a, b) for (int x = int(a); x <= (int)(b); x++)
#define drp(x, a, b) for (int x = int(a); x >= (int)(b); x--)
#define cross(x, a) for (int x = hd[a]; x; x = nx[x])
#define ll long long
using namespace std;
inline ll rd()
{
ll _x=0;int _ch=getchar(),_f=1;
for(;!isdigit(_ch)&&(_ch!='-')&&(_ch!=EOF);_ch=getchar());
if (_ch=='-'){_f=0;_ch=getchar();}
for(;isdigit(_ch);_ch=getchar()) _x=_x*10+_ch-'0';
return _f?_x:-_x;
}
void write(ll _x){if (_x>=10) write(_x/10),putchar(_x%10+'0'); else putchar(_x+'0'); }
inline void wrt(ll _x,char _p){if (_x<0) putchar('-'),_x=-_x; write(_x); if (_p) putchar(_p);}
#define maxn 50005
#define mid ((l + r) >> 1)
int n, m;
namespace xtree {
struct node {
int lazy;
ll sum;
node *ls, *rs;
};
void insert(node *&u, int l, int r, int ql, int qr) {
if (u == NULL) u = new node;
if (ql == l && r == qr) {
u->lazy++, u->sum += r - l + 1;
return;
}
u->sum += qr - ql + 1;
if (qr <= mid)
insert(u->ls, l, mid, ql, qr);
else if (ql > mid)
insert(u->rs, mid + 1, r, ql, qr);
else
insert(u->ls, l, mid, ql, mid), insert(u->rs, mid + 1, r, mid + 1, qr);
}
ll query(node *u, int l, int r, int ql, int qr) {
if (u == NULL) return 0;
if (ql == l && qr == r) return u->sum;
ll ans = (qr - ql + 1) * u->lazy;
if (qr <= mid)
return ans + query(u->ls, l, mid, ql, qr);
else if (ql > mid)
return ans + query(u->rs, mid + 1, r, ql, qr);
else
return query(u->ls, l, mid, ql, mid) + ans +
query(u->rs, mid + 1, r, mid + 1, qr);
}
}; // namespace xtree
namespace ytree {
struct node {
xtree::node *rt;
} tr[400005];
void insert(int pos, int l, int r, int ql, int qr, int x) {
xtree::insert(tr[pos].rt, 1, n, ql, qr);
if (l == r) return;
if (x <= mid)
insert(pos << 1, l, mid, ql, qr, x);
else
insert(pos << 1 | 1, mid + 1, r, ql, qr, x);
}
int query(int pos, int l, int r, int ql, int qr, ll x) {
if (l == r) return l;
ll sum = xtree::query(tr[pos << 1 | 1].rt, 1, n, ql, qr);
if (sum >= x)
return query(pos << 1 | 1, mid + 1, r, ql, qr, x);
else
return query(pos << 1, l, mid, ql, qr, x - sum);
}
}; // namespace ytree
struct Query {
int op, l, r;
ll c;
} Q[maxn];
int H[maxn], tot;
int main() {
n = rd(), m = rd();
rep(i, 1, m) {
int op = rd(), l = rd(), r = rd();
ll x = rd();
if (op == 1) ytree::insert(1, -n, n, l, r, x);
if (op == 2) wrt(ytree::query(1, -n, n, l, r, x), '\n');
}
}
avatar
初学树套树