题目网址
题目大意
请你设计一个数据结构，支持单点修改，区间查询排名k。
感想（以下省略脏话inf个字）
真的强力吹爆洛谷数据，一般的树套树还给我T了一般的点，加强的待修主席树还给我卡了几发空间。
我一共交了15发，正确率被这道题目拉低了。。。
……
分析
好像有人用了分块水过这道题目，然后被管理员的加强数据卡到怀疑人生。。。 （不讲骚话了）
考虑最简单的树套树，二逼平衡树的那个，【传送门】。
但是这里肯定是T掉了。
nlog3n在加强数据中会跑到\(4 \times 10^8\)。别想用这个方法水过去了。
附加去世代码：
#include <bits/stdc++.h>
#define ll long long
#define ms(a, b) memset(a, b, sizeof(a))
#define inf 0x3f3f3f3f
#define N 100005
#define lc (nod << 1)
#define rc (nod << 1 | 1)
using namespace std;
template <typename T>
inline void read(T &x) {
x = 0; T fl = 1; char ch = 0;
for (; ch < '0' || ch > '9'; ch = getchar())
if (ch == '-') fl = -1;
for (; ch >= '0' && ch <= '9'; ch = getchar())
x = (x << 1) + (x << 3) + (ch ^ 48);
x *= fl;
}
struct node {
int cnt, val, sz, ch[2], rd;
void init(int x) {
val = x; sz = cnt = 1; ch[1] = ch[0] = 0; rd = rand() % 100;
}
}tr[N * 20];
int tot = 0;
int rt[N], a[N];
struct treap {
#define ls(x) tr[x].ch[0]
#define rs(x) tr[x].ch[1]
void pushup(int nod) {
tr[nod].sz = tr[ls(nod)].sz + tr[rs(nod)].sz + tr[nod].cnt;
}
void rotate(int &nod, int d) {
int k = tr[nod].ch[d];
tr[nod].ch[d] = tr[k].ch[d ^ 1];
tr[k].ch[d ^ 1] = nod;
pushup(nod); pushup(k); nod = k;
}
void ins(int &nod, int val) {
if (!nod) {
tr[nod = ++ tot].init(val); return;
}
tr[nod].sz ++;
if (tr[nod].val == val) tr[nod].cnt ++;
else {
int d = val > tr[nod].val;
ins(tr[nod].ch[d], val);
if (tr[nod].rd > tr[tr[nod].ch[d]].rd) rotate(nod, d);
}
}
void del(int &nod, int val) {
if (!nod) return;
if (tr[nod].val == val) {
if (tr[nod].cnt > 1) {
tr[nod].cnt --; tr[nod].sz --; return;
}
int d = tr[ls(nod)].rd > tr[rs(nod)].rd;
if (ls(nod) == 0 || rs(nod) == 0) nod = ls(nod) + rs(nod);
else rotate(nod, d), del(nod, val);
}
else tr[nod].sz --, del(tr[nod].ch[tr[nod].val < val], val);
}
int rk(int nod, int val) {
if (!nod) return 0;
if (tr[nod].val == val) return tr[ls(nod)].sz;
if (tr[nod].val > val) return rk(ls(nod), val);
else return tr[ls(nod)].sz + tr[nod].cnt + rk(rs(nod), val);
}
}tp[N << 2];
int n, m;
void build(int nod, int l, int r) {
for (int i = l; i <= r; i ++) tp[nod].ins(rt[nod], a[i]);
if (l == r) return;
int mid = (l + r) >> 1;
build(lc, l, mid); build(rc, mid + 1, r);
}
int query_rk(int nod, int l, int r, int ql, int qr, int k) {
if (ql <= l && r <= qr) return tp[nod].rk(rt[nod], k);
int mid = (l + r) >> 1, res = 0;
if (ql <= mid) res += query_rk(lc, l, mid, ql, qr, k);
if (qr > mid) res += query_rk(rc, mid + 1, r, ql, qr, k);
return res;
}
void update(int nod, int l, int r, int k, int val) {
tp[nod].del(rt[nod], a[k]); tp[nod].ins(rt[nod], val);
if (l == r) return;
int mid = (l + r) >> 1;
if (k <= mid) update(lc, l, mid, k, val);
else update(rc, mid + 1, r, k, val);
}
int query_fd(int ql, int qr, int k) {
int l = 0, r = 1e8, res = -1;
while (l <= r) {
int mid = (l + r) >> 1;
if (query_rk(1, 1, n, ql, qr, mid) + 1 <= k) res = mid, l = mid + 1;
else r = mid - 1;
}
return res;
}
int main() {
srand(time(NULL));
read(n); read(m);
for (int i = 1; i <= n; i ++) read(a[i]);
build(1, 1, n);
while (m --) {
char opt[5];
int x, y, z;
scanf("%s", opt);
if (opt[0] == 'Q') {
read(x); read(y); read(z);
printf("%d\n", query_fd(x, y, z));
}
else {
read(x); read(y);
update(1, 1, n, x, y);
a[x] = y;
}
}
return 0;
}那么不管上面的东西了。
区间查询排名k，听到这个东西我们就可以想到主席树。
主席树实现这个操作就是，对于每一个数的插入都建一棵线段树，然后每一次查询差值，也就是查询前缀和之间的差。
这个方法依旧适用于这一道题目。
因为有修改的操作，所以普通的主席树就过不掉。
可以比较容易的想到用树状数组来维护前缀和。
前缀和维护的是每一个棵主席树的纵向的前缀和。
然后修改就只需要减掉在修改在加回去。
这个思路是我看着别人代码学到的。
还要离散化一下，因为数据比较大，主席树维护的权值线段树可能会炸掉。
#include <bits/stdc++.h>
#pragma GCC optimize(2)
#define ll long long
#define ms(a, b) memset(a, b, sizeof(a))
#define inf 0x3f3f3f3f
#define N 4000005
#define lowbit(x) (x & -x)
using namespace std;
template <typename T>
inline void read(T &x) {
x = 0; T fl = 1; char ch = 0;
for (; ch < '0' || ch > '9'; ch = getchar())
if (ch == '-') fl = -1;
for (; ch >= '0' && ch <= '9'; ch = getchar())
x = (x << 1) + (x << 3) + (ch ^ 48);
x *= fl;
}
struct qus_rec {
int x, y, z;
}qus[N];
int tot = 0, dtot, n, m, a, b;
int v[N], disc[N], rt[N], fg[N], sz[N], ls[N], rs[N], L[N], R[N];
char opt[5];
int find(int x) {
int l = 1, r = dtot;
while (l <= r) {
int mid = (l + r) >> 1;
if (disc[mid] < x) l = mid + 1;
else r = mid - 1;
}
return l;
}
void upd(int lst, int l, int r, int &rt, int w, int x) {
rt = ++ tot;
sz[rt] = sz[lst] + x; ls[rt] = ls[lst]; rs[rt] = rs[lst];
if (l == r) return;
int mid = (l + r) >> 1;
if (w <= mid) upd(ls[lst], l, mid, ls[rt], w, x);
else upd(rs[lst], mid + 1, r, rs[rt], w, x);
}
int query(int l, int r, int k) {
if (l == r) return l;
int sum = 0, mid = (l + r) >> 1;
for (int i = 1; i <= a; i ++) sum -= sz[ls[L[i]]];
for (int i = 1; i <= b; i ++) sum += sz[ls[R[i]]];
if (k <= sum) {
for (int i = 1; i <= a; i ++) L[i] = ls[L[i]];
for (int i = 1; i <= b; i ++) R[i] = ls[R[i]];
return query(l, mid, k);
}
else {
for (int i = 1; i <= a; i ++) L[i] = rs[L[i]];
for (int i = 1; i <= b; i ++) R[i] = rs[R[i]];
return query(mid + 1, r, k - sum);
}
}
int main() {
read(n); read(m);
for (int i = 1; i <= n; i ++) {
read(v[i]);
disc[++ dtot] = v[i];
}
for (int i = 1; i <= m; i ++) {
scanf("%s", opt);
scanf("%d%d", &qus[i].x, &qus[i].y);
if (opt[0] == 'Q') {
scanf("%d", &qus[i].z);
fg[i] = 1;
}
else disc[++ dtot] = qus[i].y;
}
sort(disc + 1, disc + 1 + dtot);
dtot = unique(disc + 1, disc + 1 + dtot) - disc - 1;
for (int i = 1; i <= n; i ++) {
int t = find(v[i]);
for (int j = i; j <= n; j += lowbit(j))
upd(rt[j], 1, dtot, rt[j], t, 1);
}
for (int i = 1; i <= m; i ++) {
if (fg[i]) {
a = 0, b = 0; qus[i].x --;
for (int j = qus[i].x; j; j -= lowbit(j))
L[++ a] = rt[j];
for (int j = qus[i].y; j; j -= lowbit(j))
R[++ b] = rt[j];
printf("%d\n", disc[query(1, dtot, qus[i].z)]);
}
else {
int t = find(v[qus[i].x]);
for (int j = qus[i].x; j <= n; j += lowbit(j))
upd(rt[j], 1, dtot, rt[j], t, -1);
v[qus[i].x] = qus[i].y;
t = find(qus[i].y);
for (int j = qus[i].x; j <= n; j += lowbit(j))
upd(rt[j], 1, dtot, rt[j], t, 1);
}
}
return 0;
}关于整体二分，我不会，如果有时间那么我就把他补上。