分块

序列分块

对于单点加区间和显然可以 \(O(1)-O(\sqrt n)\) 或者 \(O(\sqrt n)-O(1)\)，用 BIT 区间修改的技巧可以用相同的复杂度处理区间加区间和。

单点 check min 区间 min 显然可以 \(O(1)-O(\sqrt n)\)，但也可以 \(O(\sqrt n)-O(1)\)，方法是 st 表套分块。

值域分块

对于某些值域上的操作（例如，将区间中所有数字 \(x\) 修改为数字 \(y\)），可以使用值域分块求解。

P3834 【模板】可持久化线段树 2

查询静态区间第 \(k\) 小。

考虑对值域分块，查询时先暴力求出答案在哪个大块中，然后暴力在大块中查询答案。这需要我们维护出区间中某一值域块中的数字数量 \(\sum_{i\in [l,r]}{[blo(a_i)=y]}\) 以及区间中某一个值出现的次数 \(\sum_{i\in [l,r]}{[a_i=y]}\)。

考虑进行序列分块。整块是容易维护的，只需记录 \(s_{1\ x,y}=\sum_{blo1(i)\le x}{[blo2(a_i)= y]}\) 和 \(s_{2\ x,y}=\sum_{blo1(i)\le x}{[a_i=y]}\)，占用 \(O(V\sqrt n)\) 的空间。考虑如何处理边角料，容易发现每次查询时边角料的大小不会超过 \(O(\sqrt n)\)。给边角料单独开两个桶 \(f_{1\ y}=\sum[a_i=y]\) 和 \(f_{2\ y}=\sum[blo2(a_i)=y]\)，暴力扫一遍边角料，统计出 \(f_1\) 和 \(f_2\)。查询时将边角料的贡献也加入即可。

时间复杂度 \(O\big(m\sqrt n + m\sqrt V\big)\)。

代码

#include<iostream>
#include<cmath>
#include<algorithm>
using namespace std;
const int N = 2e5 + 10;
const int N2 = 5e2 + 10;
const int V = 2e5;

struct my_istream {
    char ch;
    template<typename _Tp>
    inline my_istream& operator>>(_Tp& x) {
        while(!isdigit(ch = getchar_unlocked()));
        x = ch - 48;
        while(isdigit(ch = getchar_unlocked())) x = x * 10 + ch - 48;
        return *this;
    }
} fin;

struct my_ostream {
    char buf[60], nb;
    inline my_ostream() { nb = 0; }
    inline my_ostream& operator<<(char c) {
        putchar(c);
        return *this;
    }
    template<typename _Tp>
    inline my_ostream& operator<<(_Tp x) {
        do buf[++nb] = x % 10, x /= 10; while(x);
        while(nb) putchar(buf[nb--] + 48);
        return *this;
    }
} fout;

int n, m;
int a[N];

int num[N], nn;

void lisanhua() {
    for(int i = 1; i <= n; i++) num[++nn] = a[i];
    sort(num + 1, num + 1 + nn);
    nn = unique(num + 1, num + 1 + nn) - (num + 1);
    for(int i = 1; i <= n; i++) a[i] = lower_bound(num + 1, num + 1 + nn, a[i]) - num;
}

int blen, bcnt;
int blo[N], bg[N2], ed[N2];
int s1[N2][N], s2[N2][N2];

int f1[N], f2[N2];
int sta[2 * N2], top;
int query(int l, int r, int k) {
    if(blo[l] == blo[r]) {
        for(int i = l; i <= r; i++) {
            sta[++top] = a[i];
            ++f1[a[i]];
            ++f2[blo[a[i]]];
        }
        l = blo[l];
        r = l - 1;
    } else {
        if(l != bg[blo[l]]) {
            for(int i = l; i <= ed[blo[l]]; i++) {
                sta[++top] = a[i];
                ++f1[a[i]];
                ++f2[blo[a[i]]];
            }
            l = ed[blo[l]] + 1;
        }
        if(r != ed[blo[r]]) {
            for(int i = bg[blo[r]]; i <= r; i++) {
                sta[++top] = a[i];
                ++f1[a[i]];
                ++f2[blo[a[i]]];
            }
            r = bg[blo[r]] - 1;
        }
        l = blo[l];
        r = blo[r];
    }
    int res = 0, sum = 0;
    while(true) {
        if(sum + s2[r][res + 1] - s2[l - 1][res + 1] + f2[res + 1] >= k) break;
        ++res;
        sum += s2[r][res] - s2[l - 1][res] + f2[res];
    }
    res = ed[res];
    while(true) {
        ++res;
        if(sum + s1[r][res] - s1[l - 1][res] + f1[res] >= k) break;
        sum += s1[r][res] - s1[l - 1][res] + f1[res];
    }
    while(top) {
        f1[sta[top]] = 0;
        f2[blo[sta[top--]]] = 0;
    }
    return num[res];
}

int main() {

    fin >> n >> m;
    for(int i = 1; i <= n; i++) fin >> a[i];

    lisanhua();

    blen = sqrt(n);
    bcnt = (n + blen - 1) / blen;
    for(int i = 1; i <= n; i++) blo[i] = (i + blen - 1) / blen;
    for(int i = 1; i <= bcnt; i++) bg[i] = (i - 1) * blen + 1;
    for(int i = 1; i <= bcnt; i++) ed[i] = min(n, i * blen);

    for(int i = 1; i <= n; i++) {
        ++s1[blo[i]][a[i]];
        ++s2[blo[i]][blo[a[i]]];
    }

    for(int i = 1; i <= bcnt; i++) {
        for(int j = 1; j <= n; j++) s1[i][j] += s1[i - 1][j];
        for(int j = 1; j <= bcnt; j++) s2[i][j] += s2[i - 1][j];
    }

    while(m--) {
        int l, r, k;
        fin >> l >> r >> k;
        fout << query(l, r, k) << '\n';
    }

    return 0;
}

P7811 [JRKSJ R2] 你的名字。

根号分治，对于较小的 \(k\) 相同的放到一起做，总共 \(B\) 次重构，\(q\) 次修改，用线段树即可。

对于较大的 \(k\)，可以枚举倍数，转化为 \(\frac{qV}{B}\) 次 \(4\)-side 查询，这玩意太强了可能做不了，发现我们是要查询一个维度的最小值，所以将区间查询弱化为后缀查询，随后对后缀扫描线，用分块 st 表随便维护即可。

P4119 [Ynoi2018] 未来日记

给定一个长为 \(n\) 的序列。有 \(m\) 次操作：

• 1 l r x y：把区间 \([l,r]\) 中所有数字 \(x\) 变成 \(y\)；
• 2 l r k：查询区间 \([l,r]\) 中的 \(k\) 小值；

考虑修改操作：对于边角料，直接暴力修改即可；对于对于整块，我们可以直接修改前缀和数组 \(s_1\) 和 \(s_2\) 中所有受到影响的位置。

然而查询操作的边角料会用到原数组 \(a\)。如何保证查询时边角料内的 \(a\) 数组最新？

如果枚举所有修改操作，将它们按顺序更新在当前块上，则无异于暴力修改，最劣时间复杂度将达到 \(O(n^2)\)。

考虑如何将同一个块的多次修改合并到一起，实现单次单块 \(O(\sqrt n)\) 的快速重构。由于无需考虑下标限制，整块的修改操作等价于染色问题（将所有数值 \(a\) 更改为数值 \(b\)），可以直接使用并查集维护。重构时暴力查询每个点在哪个集合即可。

具体的，我们始终保持并查集的根节点 \(rt\) 的 \(a[rt]\) 处于最新状态。find(x) 找到根后，根的值就是当前节点的值。

代码

AC 代码baoli.cppgen.cpp

#include<iostream>
#include<cmath>
using namespace std;
const int N = 1e5 + 10;
const int N2 = 500;
const int V = 1e5;

struct fast_istream {
    char ch;
    template<typename _Tp>
    inline fast_istream& operator>>(_Tp &x) {
        while(!isdigit(ch = getchar_unlocked()));
        x = ch - 48;
        while(isdigit(ch = getchar_unlocked())) x = x * 10 + ch - 48;
        return *this;
    }
} fin;

struct fast_ostream {
    int buf[60], nb;
    inline fast_ostream& operator<<(char c) {
        putchar_unlocked(c);
        return *this;
    }
    template<typename _Tp>
    inline fast_ostream& operator<<(_Tp x) {
        do buf[++nb] = x % 10, x /= 10; while(x);
        while(nb) putchar_unlocked(buf[nb--] + 48);
        return *this;
    }
} fout;

int n, m;
int a[N];

int blen1, bcnt1, blo1[N];
int bg1[N2], ed1[N2];

int blen2, bcnt2, blo2[N];
int bg2[N2], ed2[N2];

int s1[N2][N], s2[N2][N2];

int rt[N2][N], fa[N];
inline int find(int x) {
    if(fa[x] == x) return x;
    return fa[x] = find(fa[x]);
}
inline void merge(int x, int y) {
    fa[find(y)] = find(x);
}
// 将 p 加入 v 并查集中
inline void insert(int b, int v, int p) {
    if(rt[b][v] == 0) {
        rt[b][v] = p;
    } else merge(rt[b][v], p);
}

inline void update_unf_arr(int b) {
    int l = bg1[b], r = ed1[b];
    for(int i = l; i <= r; i++) {
        a[i] = a[find(i)];
    }
}

int buf[N2], nb;
inline void rebuild_unf(int b, int x, int y) {
    rt[b][x] = 0;
    rt[b][y] = 0;
    int l = bg1[b], r = ed1[b];
    for(int i = l; i <= r; i++) {
        if(a[i] == x || a[i] == y) fa[i] = i, buf[++nb] = i;
    }
    for(int i = 1; i <= nb; i++) {
        insert(b, a[buf[i]], buf[i]);
    }
    nb = 0;
}

inline void init() {
    blen1 = sqrt(n);
    bcnt1 = (n + blen1 - 1) / blen1;
    for(int i = 1; i <= n; i++) blo1[i] = (i + blen1 - 1) / blen1;
    for(int i = 1; i <= bcnt1; i++) bg1[i] = (i - 1) * blen1 + 1;
    for(int i = 1; i <= bcnt1; i++) ed1[i] = i * blen1;
    ed1[bcnt1] = n;

    blen2 = sqrt(V);
    bcnt2 = (n + blen2 - 1) / blen2;
    for(int i = 1; i <= n; i++) blo2[i] = (i + blen2 - 1) / blen2;
    for(int i = 1; i <= bcnt2; i++) bg2[i] = (i - 1) * blen2 + 1;
    for(int i = 1; i <= bcnt2; i++) ed2[i] = i * blen2;
    ed2[bcnt2] = V;

    for(int i = 1; i <= n; i++) {
        ++s1[blo1[i]][a[i]];
        ++s2[blo1[i]][blo2[a[i]]];
    }

    for(int i = 1; i <= bcnt1; i++) {
        for(int j = 1; j <= V; j++) s1[i][j] += s1[i - 1][j];
        for(int j = 1; j <= bcnt2; j++) s2[i][j] += s2[i - 1][j];
    }

    for(int i = 1; i <= n; i++) fa[i] = i;
    for(int i = 1; i <= n; i++) insert(blo1[i], a[i], i);
}

inline void baoli(int l, int r, int x, int y) {
    int bx = blo2[x], by = blo2[y], tmp = 0;
    int b = blo1[l];
    update_unf_arr(b);
    for(int i = l; i <= r; i++) {
        if(a[i] == x) {
            a[i] = y;
            tmp++;
        }
    }
    for(int i = b; i <= bcnt1; i++) {
        s1[i][x] = s1[i][x] - tmp;
        s1[i][y] = s1[i][y] + tmp;
        s2[i][bx] = s2[i][bx] - tmp;
        s2[i][by] = s2[i][by] + tmp;
    }
    rebuild_unf(b, x, y);
}

inline void modify(int l, int r, int x, int y) {
    int bx = blo2[x], by = blo2[y], cnt = 0;
    if(blo1[l] == blo1[r]) {
        baoli(l, r, x, y);
        return;
    }
    if(l != bg1[blo1[l]]) {
        baoli(l, ed1[blo1[l]], x, y);
        l = ed1[blo1[l]] + 1;
    }
    if(r != ed1[blo1[r]]) {
        baoli(bg1[blo1[r]], r, x, y);
        r = bg1[blo1[r]] - 1;
    }
    l = blo1[l];
    r = blo1[r];
    for(int b = l; b <= r; b++) {
        int tmp = cnt;
        cnt += s1[b][x] - s1[b - 1][x];
        s1[b - 1][x] -= tmp;
        s1[b - 1][y] += tmp;
        s2[b - 1][bx] -= tmp;
        s2[b - 1][by] += tmp;
        if(cnt == tmp) continue;
        if(rt[b][y] == 0) {
            rt[b][y] = rt[b][x];
            a[find(rt[b][y])] = y;
        } else merge(rt[b][y], rt[b][x]);
        rt[b][x] = 0;
    }
    for(int i = r; i <= bcnt1; i++) {
        s1[i][x] = s1[i][x] - cnt;
        s1[i][y] = s1[i][y] + cnt;
        s2[i][bx] = s2[i][bx] - cnt;
        s2[i][by] = s2[i][by] + cnt;
    }
}

int f1[V], f2[N2];
int sta[2 * N2], top;
int query(int l, int r, int k) {
    int bl, br;
    if(blo1[l] == blo1[r]) {
        update_unf_arr(blo1[l]);
        bl = blo1[l] + 1;
        br = blo1[l];
        for(int i = l; i <= r; i++) {
            ++f1[a[i]];
            ++f2[blo2[a[i]]];
            sta[++top] = a[i];
        }
    } else {
        if(l != bg1[blo1[l]]) {
            update_unf_arr(blo1[l]);
            for(int i = l; i <= ed1[blo1[l]]; i++) {
                ++f1[a[i]];
                ++f2[blo2[a[i]]];
                sta[++top] = a[i];
            }
            l = ed1[blo1[l]] + 1;
        }
        if(r != ed1[blo1[r]]) {
            update_unf_arr(blo1[r]);
            for(int i = bg1[blo1[r]]; i <= r; i++) {
                ++f1[a[i]];
                ++f2[blo2[a[i]]];
                sta[++top] = a[i];
            }
            r = bg1[blo1[r]] - 1;
        }
        bl = blo1[l], br = blo1[r];
    }
    int res = 0, sum = 0;
    while(res <= bcnt2) {
        if(sum + s2[br][res + 1] - s2[bl - 1][res + 1] + f2[res + 1] >= k) {
            break;
        }
        ++res;
        sum += s2[br][res] - s2[bl - 1][res] + f2[res];
    }
    res = ed2[res];
    while(true) {
        ++res;
        if(sum + s1[br][res] - s1[bl - 1][res] + f1[res] >= k) {
            break;
        }
        sum += s1[br][res] - s1[bl - 1][res] + f1[res];
    }
    while(top) {
        f1[sta[top]] = 0;
        f2[blo2[sta[top]]] = 0;
        --top;
    }
    return res;
}

int main() {

    fin >> n >> m;
    for(int i = 1; i <= n; i++) fin >> a[i];

    init();

    while(m--) {
        int op, l, r, k, x, y;
        fin >> op >> l >> r;
        if(op == 1) {
            fin >> x >> y;
            if(x == y) continue;
            modify(l, r, x, y);
        } else {
            fin >> k;
            fout << query(l, r, k) << '\n';
        }
    }

    return 0;
}

#include<iostream>
#include<cmath>
#include<algorithm>
using namespace std;
const int N = 1e5 + 10;
const int N2 = 320;
const int V = 1e5;

struct fast_istream {
    char ch;
    template<typename _Tp>
    inline fast_istream& operator>>(_Tp &x) {
        while(!isdigit(ch = getchar_unlocked()));
        x = ch - 48;
        while(isdigit(ch = getchar_unlocked())) x = x * 10 + ch - 48;
        return *this;
    }
} fin;

struct fast_ostream {
    int buf[60], nb;
    inline fast_ostream& operator<<(char c) {
        putchar(c);
        return *this;
    }
    template<typename _Tp>
    inline fast_ostream& operator<<(_Tp x) {
        do buf[++nb] = x % 10, x /= 10; while(x);
        while(nb) putchar(buf[nb--] + 48);
        return *this;
    }
} fout;

int n, m;
int a[N];

inline void modify(int l, int r, int x, int y) {
    for(int i = l; i <= r; i++) {
        if(a[i] == x) a[i] = y;
    }
}

int num[N];
int query(int l, int r, int k) {
    for(int i = l; i <= r; i++) {
        num[i - l + 1] = a[i];
    }
    int len = r - l + 1;
    sort(num + 1, num + 1 + len);
    return num[k];
}

int main() {

    fin >> n >> m;
    for(int i = 1; i <= n; i++) fin >> a[i];

    while(m--) {
        int op, l, r, k, x, y;
        fin >> op >> l >> r;
        if(op == 1) {
            fin >> x >> y;
            if(x == y) continue;
            modify(l, r, x, y);
        } else {
            fin >> k;
            fout << query(l, r, k) << '\n';
        }
    }

    return 0;
}

#include "testlib.h"
using namespace std;

int n = 500;
int m = 400;
int v = 5;

int main() {

    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);

    cout << n << ' ' << m << '\n';
    for(int i = 1; i <= n; i++) {
        cout << rng() % v + 1 << ' ';
    }
    cout << '\n';

    for(int i = 1; i <= m; i++) {
        int l = rng() % n + 1;
        int r = rng() % n + 1;
        if(l > r) swap(l, r);
        if(rng() & 1) {
            int x = rng() % v + 1;
            int y = rng() % v + 1;
            cout << 1 << ' ' << l << ' ' << r << ' ' << x << ' ' << y << '\n';
        } else {
            int k = rng() % (r - l + 1) + 1;
            cout << 0 << ' ' << l << ' ' << r << ' ' << k << '\n';
        }
    }

    return 0;
}