P3380 【模板】二逼平衡树（树套树） 题解。

大家好，我非常喜欢暴力数据结构，于是我就用带修莫队套分块过了这道题

1. 前置芝士

带修莫队和分块。

2. 题解

发现这题只有一个单点修改，于是考虑带修莫队。

我们把普通莫队强行加上一个时间维 $t$，表示当前经过的修改次数，就变成带修莫队了。

带修莫队的过程如下：

将询问离线，对原序列以 $n^\frac 2 3$ 的块长分块。对于区间 $[l, r, t]$，按照 $l$ 所在块为第一关键字，$r$ 所在块为第二关键字，$t$ 为第三关键字从小到大排序。

顺序处理每个询问，我们暴力从上一个区间转移到下一个区间，从上一个时间转移到下一个时间，这样的复杂度为 $O(n^\frac 5 3)$。

然后我们考虑如何维护答案，我们需要一个能支持如下操作这样的数据结构：

1. 插入 $x$ 数；
2. 删除 $x$ 数；
3. 查询 $x$ 数的排名；
4. 查询排名为 $x$ 的数；
5. 求 $x$ 的前驱；
6. 求 $x$ 的后继。

可以想到用平衡树，或者常数小的权值树状数组维护。这样修改和查询都是 $O(\log n)$ 的，总复杂度 $O(n^\frac 5 3 \log n)$。

但其实可以用分块平衡复杂度，将修改的复杂度减少至 $O(1)$，查询复杂度增加至 $O(\sqrt n)$，总复杂度变为 $O(n^\frac 5 3)$。

具体的，首先对出现的数离散化到 $[1, n]$，然后对值域分块，块内维护每个数出现的次数。

对于操作 1 2，单点修改即可。

                
void insert(int x) { ++val[x], ++sum[belong[x]]; }
void remove(int x) { --val[x], --sum[belong[x]]; }
                
cpp
                

                    
                    
                
                

对于操作 3，直接对 $[1, x - 1]$ 区间求和即可。

                
int queryrank(int x) {
    int res = 0;
    for (int i = 1; i <= belong[x] - 1; i++) res += sum[i];
    for (int i = x - 1; belong[i] == belong[x]; i--) res += val[i];
    return res + 1;
}
                
cpp
                

                    
                    
                
                

对于操作 4，从左到右扫一遍即可。

                
int querykth(int x) {
    int i = 1, j = 1, cur = 0;
    while (cur + sum[i] < x) cur += sum[i++], j += siz;
    while (cur + val[j] < x) cur += val[j++];
    return j;
}
                
cpp
                

                    
                    
                
                

对于操作 5 6，可以转换为操作 2 3。

                
int querypre(int x) { return querykth(queryrank(x) - 1); }
int querynext(int x) { return querykth(queryrank(x + 1)); }
                
cpp
                

                    
                    
                
                

3. Code

                
#include <algorithm>
#include <cmath>
#include <iostream>
#include <limits>
using namespace std;
const int N = 1e5 + 5;
int n, m, m1, m2, l = 1, r, t, a[N], b[N], belong[N], val[N], sum[N], siz, cnt;
struct node {
    int op, l, r, x, k, t, id, ans;
} q[N], u[N];
bool cmp1(node a, node b) {
    if (belong[a.l] != belong[b.l]) return a.l < b.l;
    if (belong[a.r] != belong[b.r]) return a.r < b.r;
    return a.t < b.t;
}
bool cmp2(node a, node b) { return a.id < b.id; }
void build1() {
    siz = pow(n, 2.0 / 3.0);
    for (int i = 1; i <= n; i++) belong[i] = (i - 1) / siz + 1;
}
void build2() {
    siz = sqrt(cnt);
    for (int i = 1; i <= cnt; i++) belong[i] = (i - 1) / siz + 1;
}
void insert(int x) { ++val[a[x]], ++sum[belong[a[x]]]; }
void remove(int x) { --val[a[x]], --sum[belong[a[x]]]; }
void update(int x) {
    if (l <= u[x].x && u[x].x <= r) remove(u[x].x);
    swap(a[u[x].x], u[x].k);
    if (l <= u[x].x && u[x].x <= r) insert(u[x].x);
}
int queryrank(int x) {
    int res = 0;
    for (int i = 1; i <= belong[x] - 1; i++) res += sum[i];
    for (int i = x - 1; belong[i] == belong[x]; i--) res += val[i];
    return res + 1;
}
int querykth(int x) {
    if (x < 1) return cnt + 1;
    if (x > r - l + 1) return cnt + 2;
    int i = 1, j = 1, k = 0;
    while (k + sum[i] < x) k += sum[i++], j += siz;
    while (k + val[j] < x) k += val[j++];
    return j;
}
int querypre(int x) { return querykth(queryrank(x) - 1); }
int querynext(int x) { return querykth(queryrank(x + 1)); }
int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    cin >> n >> m;
    cnt = n;
    for (int i = 1; i <= n; i++) cin >> a[i], b[i] = a[i];
    for (int i = 1, op, l, r, x, k; i <= m; i++) {
        cin >> op;
        if (op == 3) {
            cin >> x >> k;
            u[++m2] = {op, 0, 0, x, k, m2, m1};
        } else {
            cin >> l >> r >> k;
            q[++m1] = {op, l, r, 0, k, m2, m1};
        }
        if (op != 2) b[++cnt] = k;
    }
    sort(b + 1, b + cnt + 1);
    cnt = unique(b + 1, b + cnt + 1) - b - 1;
    for (int i = 1; i <= n; i++) a[i] = lower_bound(b + 1, b + cnt + 1, a[i]) - b;
    for (int i = 1; i <= m1; i++)
        if (q[i].op != 2) q[i].k = lower_bound(b + 1, b + cnt + 1, q[i].k) - b;
    for (int i = 1; i <= m2; i++)
        if (u[i].op != 2) u[i].k = lower_bound(b + 1, b + cnt + 1, u[i].k) - b;
    b[cnt + 1] = numeric_limits<int>::min() + 1;
    b[cnt + 2] = numeric_limits<int>::max();
    build1();
    sort(q + 1, q + m1 + 1, cmp1);
    build2();
    for (int i = 1; i <= m1; i++) {
        while (l > q[i].l) insert(--l);
        while (r < q[i].r) insert(++r);
        while (l < q[i].l) remove(l++);
        while (r > q[i].r) remove(r--);
        while (t < q[i].t) update(++t);
        while (t > q[i].t) update(t--);
        if (q[i].op == 1) q[i].ans = queryrank(q[i].k);
        else if (q[i].op == 2) q[i].ans = b[querykth(q[i].k)];
        else if (q[i].op == 4) q[i].ans = b[querypre(q[i].k)];
        else if (q[i].op == 5) q[i].ans = b[querynext(q[i].k)];
    }
    sort(q + 1, q + m1 + 1, cmp2);
    for (int i = 1; i <= m1; i++) cout << q[i].ans << '\n';
    return 0;
}
                
cpp