分块学习笔记

トバリくん镇文。就是这首歌为我开启了海鲜市场的大门。哦还有宝狈让我吸吸

给各位安利这版Cover：https://www.youtube.com/watch?v=V3jzSIYL_7I

每次学点新东西都要找一张好看的封面，多少有点为了这点醋包饺子的感觉了（不是

---

碎碎念

提起数据结构，除去基础的栈、队列等东西，容易想到的就是并查集、树状数组、线段树这些高级结构。这些数据结构在维护信息的时候，往往要求信息具有一定的特殊性质，例如线段树要求信息是半群（满足封闭性和结合律），树状数组要求信息可差分等。那如果我们需要维护的信息不具有这些良好的性质，要怎么维护呢？退而求其次，我们选择一种偏暴力的形式，也就是我们今天要说的分块。

顾名思义，分块就是把一个完整的序列分成若干块，块内预处理一些信息，做区间操作的时候拆成两边的散块和中间的整块，分别进行处理。一般块的大小取$O\left(\sqrt n\right)$ ，这样对应的块的数量也是$O\left(\sqrt n\right)$ ，每次操作的复杂度就可以控制在$O\left(\sqrt n\right)$的级别，这样虽然是暴力，但平衡了查询和修改的复杂度，也相对来讲还能接受。因为复杂度往往带个根号，所以分块也常常叫做“根号数据结构”。

这样就相当于用一点复杂度的代价，换取了较少的心智负担，在比赛场上数据范围不大的情况下，如果想不到正解，拿分块来暴力冲一冲也是一个不错的选择，说不定就过了呢。

正因为是暴力，所以分块对信息的性质基本没有特殊要求，什么都能维护，比较万能。

分块常见的用法：对元素序列分块、对值域分块、对时间序列分块（也就是一种离线做法，类似扫描线），再拓展，有二次分块、分块套分块、分块结合别的数据结构，例如并查集。除了处理朴素的序列，放到树上也可以用分块，也分几种情况，重链剖分以后对dfn序列分块（这个本质还是序列分块）、随机撒点分块（实际没有块了，但是思想类似）、对节点个数分块、以及Top cluster，等等等等。真感兴趣可以深挖，时间紧的话还是学正解吧，很多分块题都有复杂度更好的正解。用相对较少的时间学一套能够相对通用的解法，这样才比较明智。

和别的数据结构不同，分块没有什么模板代码，全部都是见招拆招。关于其结构方面也确实没什么需要着重强调的，所以以题代讲，更好地体会分块的用法吧。

例题

SP18185 GIVEAWAY - Give Away

单点加，区间查询小于v的值的数量。

考虑给序列分块，每个小块内部保持有序，这样查询整块的时候可以通过二分来加速查询。对于散块直接暴力查询。如果有修改就暴力更新数组再排序即可，单次操作复杂度$O(\sqrt{n}\log{\sqrt{n}})$，总复杂度即为$O(m\sqrt{n}\log{\sqrt{n}})$。

#include <bits/stdc++.h>
#define FIO cin.tie(0); ios::sync_with_stdio(false)
#define all(x) (x).begin(), (x).end()
#define fi first
#define se second
#define TEST
#define TESTS int t = 1; cin >> t; while (t--)

using namespace std;
using i64 = long long;
using u32 = unsigned;
using u64 = unsigned long long;
using pii = std::pair<int, int>;

inline char nc() {
    static char buf[1 << 20], *p1, *p2;
    return p1 == p2 && (p2 = (p1 = buf) + fread(buf, 1, 1 << 20, stdin), p1 == p2) ? EOF : *p1++;
}
#ifndef ONLINE_JUDGE
#define nc getchar
#endif
void read() {}
template<typename T, typename... T2> 
inline void read(T &x, T2 &... oth) {
    x = 0; char c = nc(), up = c;
    while(!isdigit(c)) up = c, c = nc();
    while(isdigit(c)) x = x * 10 + c - '0', c = nc();
    up == '-' ? x = -x : 0;
    read(oth...);
}

constexpr int N = 5e5 + 10;
constexpr int MOD = 998244353;

int a[N], v[N], bi[N], bl[N], br[N];
int blen, bnum;

void build(int n) {
    blen = sqrt(n);
    bnum = (n + blen - 1) / blen;
    for (int i = 1; i <= n; ++i) {
        bi[i] = (i - 1) / blen + 1;
    }
    for (int i = 1; i <= bnum; ++i) {
        bl[i] = (i - 1) * blen + 1;
        br[i] = min(n, i * blen);
    }
    for (int i = 1; i <= n; ++i) v[i] = a[i];
    for (int i = 1; i <= bnum; ++i) {
        sort(v + bl[i], v + br[i] + 1);
    }
}

int query(int l, int r, int k) {
    int res = 0;
    if (bi[l] == bi[r]) {
        for (int i = l; i <= r; ++i) res += a[i] >= k;
        return res;
    }
    for (int i = l; i <= br[bi[l]]; ++i) {
        res += a[i] >= k;
    }
    for (int i = bi[l] + 1; i < bi[r]; ++i) {
        auto x = lower_bound(v + bl[i], v + br[i] + 1, k);
        res += (v + br[i] + 1 - x);
    }
    for (int i = bl[bi[r]]; i <= r; ++i) {
        res += a[i] >= k;
    }
    return res;
}

void modify(int x, int k) {
    a[x] = k;
    for (int i = bl[bi[x]]; i <= br[bi[x]]; ++i) {
        v[i] = a[i];
    }
    sort(v + bl[bi[x]], v + br[bi[x]] + 1);
}

void solve() {
    int n;
    read(n);
    for (int i = 1; i <= n; ++i) read(a[i]);
    build(n);
    int q;
    read(q);
    while (q--) {
        int op, a, b, c;
        read(op, a, b);
        if (op == 0) {
            read(c);
            cout << query(a, b, c) << "\n";
        } else {
            modify(a, b);
        }
    }
}

signed main() {
    
    FIO;
    TEST {
        solve();
    }

    return 0;
}

P2801 教主的魔法

区间加，区间查询小于v的值的数量。

跟上面单点加很类似，再维护一个类似线段树的lazy懒更新信息，散块还是暴力更新，整块直接更新这个lazy数组即可。

#include <bits/stdc++.h>
#define FIO cin.tie(0); ios::sync_with_stdio(false)
#define all(x) (x).begin(), (x).end()
#define fi first
#define se second
#define TEST
#define TESTS int t = 1; cin >> t; while (t--)

using namespace std;
using i64 = long long;
using u32 = unsigned;
using u64 = unsigned long long;
using pii = std::pair<int, int>;

inline char nc() {
    static char buf[1 << 20], *p1, *p2;
    return p1 == p2 && (p2 = (p1 = buf) + fread(buf, 1, 1 << 20, stdin), p1 == p2) ? EOF : *p1++;
}
#ifndef ONLINE_JUDGE
#define nc getchar
#endif
void read() {}
template<typename T, typename... T2> 
inline void read(T &x, T2 &... oth) {
    x = 0; char c = nc(), up = c;
    while(!isdigit(c)) up = c, c = nc();
    while(isdigit(c)) x = x * 10 + c - '0', c = nc();
    up == '-' ? x = -x : 0;
    read(oth...);
}
template<typename... T2> 
inline void read(char &x, T2 &... oth) {
    x = nc();
    while (!isalpha(x)) x = nc();
    read(oth...);
}

constexpr int N = 1e6 + 10;
constexpr int MOD = 998244353;

int a[N], v[N], bi[N], bl[N], br[N], lazy[N];

int query(int l, int r, int k) {
    int res = 0;
    if (bi[l] == bi[r]) {
        for (int i = l; i <= r; ++i) {
            res += a[i] >= k - lazy[bi[l]];
        }
        return res;
    }
    for (int i = l; i <= br[bi[l]]; ++i) {
        res += a[i] >= k - lazy[bi[l]];
    }
    for (int i = bi[l] + 1; i < bi[r]; ++i) {
        auto x = lower_bound(v + bl[i], v + br[i] + 1, k - lazy[i]);
        res += (v + br[i] + 1 - x);
    }
    for (int i = bl[bi[r]]; i <= r; ++i) {
        res += a[i] >= k - lazy[bi[r]];
    }
    return res;
}

void modify(int l, int r, int k) {
    if (bi[l] == bi[r]) {
        for (int i = l; i <= r; ++i) {
            a[i] += k;
        }
        sort(v + bl[bi[l]], v + br[bi[l]] + 1);
        return;
    }
    for (int i = l; i <= br[bi[l]]; ++i) {
        a[i] += k;
    }
    sort(v + bl[bi[l]], v + br[bi[l]] + 1);
    for (int i = bi[l] + 1; i < bi[r]; ++i) {
        lazy[i] += k;
    }
    for (int i = bl[bi[r]]; i <= r; ++i) {
        a[i] += k;
    }
    sort(v + bl[bi[r]], v + br[bi[r]] + 1);
}

void solve() {
    int n, q;
    read(n, q);
    for (int i = 1; i <= n; ++i) read(a[i]), v[i] = a[i];
    int blen = sqrt(n);
    int bnum = (n + blen - 1) / blen;
    for (int i = 1; i <= bnum; ++i) {
        bl[i] = (i - 1) * blen + 1;
        br[i] = min(n, i * blen);
        sort(v + bl[i], v + br[i] + 1);
    }
    while (q--) {
        char c;
        int l, r, k;
        read(c, l, r, k);
        if (c == 'A') {
            cout << query(l, r, k) << "\n";
        } else {
            modify(l, r, k);
        }
    }

}

signed main() {
    
    FIO;
    TEST {
        solve();
    }

    return 0;
}

P4168 [Violet] 蒲公英

静态区间众数查询。

这玩意其实很久以前就想学了，当时望而生畏，现在跟着课程看懂了（

还是那句话，分块本身的思想非常trivial，重点是怎么用散块和整块的信息去拼出答案。

对于整块，维护两个信息：$freq[i][j]$表示前i块中数j出现的次数，$mode[i][j]$表示第i块到第j块的众数。查询时，我们先统计散块的信息，也就是散块中各数的词频。通过$mode[i][j]$可以拿到中间整块的众数，在遍历散块中的每一个数，计算其在范围中的出现次数，如果出现次数大于目前的众数的次数则更新答案。这样预处理复杂度$O(n\sqrt{n})$，查询复杂度$O(m\sqrt{n})$。

#include <bits/stdc++.h>
#define FIO cin.tie(0); ios::sync_with_stdio(false)
#define all(x) (x).begin(), (x).end()
#define fi first
#define se second
#define TEST
#define TESTS int t = 1; cin >> t; while (t--

using namespace std;
using i64 = long long;
using u32 = unsigned;
using u64 = unsigned long long;
using pii = std::pair<int, int>;

inline char nc() {
    static char buf[1 << 20], *p1, *p2;
    return p1 == p2 && (p2 = (p1 = buf) + fread(buf, 1, 1 << 20, stdin), p1 == p2) ? EOF : *p1++;
}
#ifndef ONLINE_JUDGE
#define nc getchar
#endif
void read() {}
template<typename T, typename... T2> 
inline void read(T &x, T2 &... oth) {
    x = 0; char c = nc(), up = c;
    while(!isdigit(c)) up = c, c = nc();
    while(isdigit(c)) x = x * 10 + c - '0', c = nc();
    up == '-' ? x = -x : 0;
    read(oth...);
}

constexpr int N = 4e4 + 10;
constexpr int B = 2e2 + 10;
constexpr int MOD = 998244353;

int a[N], v[N], bi[N], bl[B], br[B];
int freq[B][N], mode[B][B];
int cnt[N];

inline int getCnt(int l, int r, int v) {
    return freq[r][v] - freq[l - 1][v];
}

int query(int l, int r) {
    int most = 0;
    if (bi[l] == bi[r]) {
        for (int i = l; i <= r; ++i) {
            cnt[a[i]]++;
        }
        for (int i = l; i <= r; ++i) {
            if (cnt[a[i]] > cnt[most] || (cnt[a[i]] == cnt[most] && a[i] < most)) {
                most = a[i];
            }
        }
        for (int i = l; i <= r; ++i) {
            cnt[a[i]] = 0;
        }
    } else {
        for (int i = l; i <= br[bi[l]]; ++i) {
            cnt[a[i]]++;
        }
        for (int i = bl[bi[r]]; i <= r; ++i) {
            cnt[a[i]]++;
        }
        most = mode[bi[l] + 1][bi[r] - 1];
        int mostCnt = getCnt(bi[l] + 1, bi[r] - 1, most) + cnt[most];
        for (int i = l; i <= br[bi[l]]; ++i) {
            int cur = a[i];
            int curCnt = getCnt(bi[l] + 1, bi[r] - 1, cur) + cnt[cur];
            if (curCnt > mostCnt || (curCnt == mostCnt && cur < most)) {
                most = cur;
                mostCnt = curCnt;
            }
        }
        for (int i = bl[bi[r]]; i <= r; ++i) {
            int cur = a[i];
            int curCnt = getCnt(bi[l] + 1, bi[r] - 1, cur) + cnt[cur];
            if (curCnt > mostCnt || (curCnt == mostCnt && cur < most)) {
                most = cur;
                mostCnt = curCnt;
            }
        }
        for (int i = l; i <= br[bi[l]]; ++i) {
            cnt[a[i]] = 0;
        }
        for (int i = bl[bi[r]]; i <= r; ++i) {
            cnt[a[i]] = 0;
        }
    }
    return v[most];
}

void solve() {
    int n, m;   
    cin >> n >> m;
    for (int i = 1; i <= n; ++i) cin >> a[i], v[i] = a[i];
    sort(v + 1, v + 1 + n);
    int s = unique(v + 1, v + 1 + n) - v - 1;
    for (int i = 1; i <= n; ++i) a[i] = lower_bound(v + 1, v + 1 + s, a[i]) - v;
    int blen = sqrt(n);
    int bnum = (n + blen - 1) / blen;
    for (int i = 1; i <= n; ++i) {
        bi[i] = (i - 1) / blen + 1;
    }
    for (int i = 1; i <= bnum; ++i) {
        bl[i] = (i - 1) * blen + 1;
        br[i] = min(n, i * blen);
    }
    for (int i = 1; i <= bnum; ++i) {
        for (int j = bl[i]; j <= br[i]; ++j) {
            freq[i][a[j]]++;
        }
        for (int j = 1; j <= s; ++j) {
            freq[i][j] += freq[i - 1][j];
        }
    }
    for (int i = 1; i <= bnum; ++i) {
        for (int j = i; j <= bnum; ++j) {
            int most = mode[i][j - 1];
            int mostCnt = getCnt(i, j, most);
            for (int k = bl[j]; k <= br[j]; ++k) {
                int cur = a[k];
                int curCnt = getCnt(i, j, cur);
                if (curCnt > mostCnt || (curCnt == mostCnt && cur < most)) {
                    most = cur;
                    mostCnt = curCnt;
                }
            }
            mode[i][j] = most;
        }
    }
    for (int x, y, lastans = 0; m; m--) {
        cin >> x >> y;
        auto [l, r] = minmax({(x + lastans - 1) % n + 1, (y + lastans - 1) % n + 1});
        cout << (lastans = query(l, r)) << "\n";
    }
}

signed main() {
    
    FIO;
    TEST {
        solve();
    }

    return 0;
}

P5048 [Ynoi2019 模拟赛] Yuno loves sqrt technology III

静态区间众数出现次数查询。

不问众数而问其出现次数，就给了我们优化的可能。本题的空间复杂度可以优化到$O(n)$。事实上不优化完全过不去（

由于特殊的空间限制，上一道题的$freq$数组无法维护，但我们仍然可以维护一个类似的$modeCnt[i][j]$，表示第i块到第j块的众数出现次数。此外再处理一下整个序列，拷贝一份$sortList$，维护其值和原下标，将值作为第一关键字，原下标作为第二关键字进行排序。这样我们就可以把相同的值按照从左到右的顺序依次取得（即再维护一个$listIdx[sortList[i][1]]=i$）。

预处理结束，考虑拼信息。先拿到整块的出现次数作为答案$ans$，散块中的某些值的出现次数可能会超过$ans$，直接遍历散块每个点。如果次数真的超过ans，那么在先前维护的$sortList$中必然会存在一段值相等，下标均在查询范围之内的连续段。我们通过原下标能够拿到这个数在$sortList$中的下标，检查其左边/右边第$ans$个数是否仍为该值即可，考虑到$ans$不会减少，所以$ans$最多更新$O(\sqrt{n}$次，整体查询时间复杂度为$O(m\sqrt{n})$。

#include <bits/stdc++.h>
#define FIO cin.tie(0); ios::sync_with_stdio(false)
#define all(x) (x).begin(), (x).end()
#define fi first
#define se second
#define TEST
#define TESTS int t = 1; cin >> t; while (t--)

using namespace std;
using i64 = long long;
using u32 = unsigned;
using u64 = unsigned long long;
using pii = std::pair<int, int>;

inline char nc() {
    static char buf[1 << 20], *p1, *p2;
    return p1 == p2 && (p2 = (p1 = buf) + fread(buf, 1, 1 << 20, stdin), p1 == p2) ? EOF : *p1++;
}
#ifndef ONLINE_JUDGE
#define nc getchar
#endif
void read() {}
template<typename T, typename... T2> 
inline void read(T &x, T2 &... oth) {
    x = 0; char c = nc(), up = c;
    while(!isdigit(c)) up = c, c = nc();
    while(isdigit(c)) x = x * 10 + c - '0', c = nc();
    up == '-' ? x = -x : 0;
    read(oth...);
}

constexpr int N = 5e5 + 10;
constexpr int B = 800;
constexpr int MOD = 998244353;

int a[N], listIdx[N], bi[N], bl[B], br[B];
int modeCnt[B][B];
int numCnt[N];
int n;
array<int, 2> sortList[N];

int query(int l, int r) {
    int ans = 0;
    if (bi[l] == bi[r]) {
        for (int i = l; i <= r; ++i) {
            ans = max(ans, ++numCnt[a[i]]);
        }
        for (int i = l; i <= r; ++i) {
            numCnt[a[i]] = 0;
        }
    } else {
        ans = modeCnt[bi[l] + 1][bi[r] - 1];
        for (int i = l; i <= br[bi[l]]; ++i) {
            int idx = listIdx[i];
            while (idx + ans <= n && sortList[idx + ans][0] == a[i] && sortList[idx + ans][1] <= r) {
                ans++;
            }
        }
        for (int i = bl[bi[r]]; i <= r; ++i) {
            int idx = listIdx[i];
            while (idx - ans >= 1 && sortList[idx - ans][0] == a[i] && sortList[idx - ans][1] >= l) {
                ans++;
            }
        }
    }
    return ans;
}

void solve() {
    int m;
    cin >> n >> m;
    for (int i = 1; i <= n; ++i) {
        cin >> a[i];
        sortList[i] = {a[i], i};
    }
    sort(sortList + 1, sortList + 1 + n, [&](auto x, auto y) {
        if (x[0] != y[0]) return x[0] < y[0];
        else return x[1] < y[1];
    });
    for (int i = 1; i <= n; ++i) {
        listIdx[sortList[i][1]] = i;
    }
    int blen = sqrt(n);
    int bnum = (n + blen - 1) / blen;
    for (int i = 1; i <= n; ++i) {
        bi[i] = (i - 1) / blen + 1;
    }
    for (int i = 1; i <= bnum; ++i) {
        bl[i] = (i - 1) * blen + 1;
        br[i] = min(n, i * blen);
    }
    for (int i = 1; i <= bnum; ++i) {
        for (int j = i; j <= bnum; ++j) {
            int cnt = modeCnt[i][j - 1];
            for (int k = bl[j]; k <= br[j]; ++k) {
                cnt = max(cnt, ++numCnt[a[k]]);
            }
            modeCnt[i][j] = cnt;
        }
        for (int i = 1; i <= n; ++i) {
            numCnt[a[i]] = 0;
        }
    }
    for (int i = 0, l, r, lastAns = 0; i < m; ++i) {
        cin >> l >> r;
        l ^= lastAns; r ^= lastAns;
        cout << (lastAns = query(l, r)) << "\n";
    }
}

signed main() {
    
    FIO;
    TEST {
        solve();
    }

    return 0;
}

P4135 作诗

静态查询区间出现次数为正偶数的数的个数。

做法和区间众数很类似，还是预处理前i块中数j的出现次数$freq[i][j]$以及块i到块j中出现次数为正偶数的数的个数$even[i][j]$。

查询时统计散块每个点的词频，根据这个范围内这个数的出现次数更新答案即可，很简单不赘述。

#include <bits/stdc++.h>
#define FIO cin.tie(0); ios::sync_with_stdio(false)
#define all(x) (x).begin(), (x).end()
#define fi first
#define se second
#define TEST
#define TESTS int t = 1; cin >> t; while (t--)

using namespace std;
using i64 = long long;
using u32 = unsigned;
using u64 = unsigned long long;
using pii = std::pair<int, int>;

inline char nc() {
    static char buf[1 << 20], *p1, *p2;
    return p1 == p2 && (p2 = (p1 = buf) + fread(buf, 1, 1 << 20, stdin), p1 == p2) ? EOF : *p1++;
}
#ifndef ONLINE_JUDGE
#define nc getchar
#endif
void read() {}
template<typename T, typename... T2> 
inline void read(T &x, T2 &... oth) {
    x = 0; char c = nc(), up = c;
    while(!isdigit(c)) up = c, c = nc();
    while(isdigit(c)) x = x * 10 + c - '0', c = nc();
    up == '-' ? x = -x : 0;
    read(oth...);
}

constexpr int N = 1e5 + 10;
constexpr int B = 400;
constexpr int MOD = 998244353;

int a[N], freq[B][N], even[B][B], bi[N], bl[B], br[B];
int numCnt[N];

inline int getCnt(int l, int r, int v) {
    return freq[r][v] - freq[l - 1][v];
}

inline int delta(int cnt) {
    if (cnt == 0) return 0;
    if (cnt & 1) return 1;
    return -1;
}

int query(int l, int r) {
    int ans = 0;
    if (bi[l] == bi[r]) {
        for (int i = l; i <= r; ++i) {
            ans += delta(numCnt[a[i]]);
            numCnt[a[i]]++;
        }
        for (int i = l; i <= r; ++i) {
            numCnt[a[i]] = 0;
        }
    } else {
        ans = even[bi[l] + 1][bi[r] - 1];
        for (int i = l; i <= br[bi[l]]; ++i) {
            ans += delta(getCnt(bi[l] + 1, bi[r] - 1, a[i]) + numCnt[a[i]]);
            numCnt[a[i]]++;
        }
        for (int i = bl[bi[r]]; i <= r; ++i) {
            ans += delta(getCnt(bi[l] + 1, bi[r] - 1, a[i]) + numCnt[a[i]]);
            numCnt[a[i]]++;
        }
        for (int i = l; i <= br[bi[l]]; ++i) {
            numCnt[a[i]] = 0;
        }
        for (int i = bl[bi[r]]; i <= r; ++i) {
            numCnt[a[i]] = 0;
        }
    }
    return ans;
}

void solve() {
    int n, c, m;
    cin >> n >> c >> m;
    for (int i = 1; i <= n; ++i) {
        cin >> a[i];
    }
    int blen = sqrt(n);
    int bnum = (n + blen - 1) / blen;
    for (int i = 1; i <= n; ++i) {
        bi[i] = (i - 1) / blen + 1;
    }
    for (int i = 1; i <= bnum; ++i) {
        bl[i] = (i - 1) * blen + 1;
        br[i] = min(n, i * blen);
    }
    for (int i = 1; i <= bnum; ++i) {
        for (int j = bl[i]; j <= br[i]; ++j) {
            freq[i][a[j]]++;
        }
        for (int j = 1; j <= c; ++j) {
            freq[i][j] += freq[i - 1][j];
        }
    }
    for (int i = 1; i <= bnum; ++i) {
        for (int j = i; j <= bnum; ++j) {
            even[i][j] = even[i][j - 1];
            for (int k = bl[j]; k <= br[j]; ++k) {
                even[i][j] += delta(numCnt[a[k]]);
                numCnt[a[k]]++;
            }
        }
        for (int j = 1; j <= c; ++j) {
            numCnt[j] = 0;
        }
    }
    for (int x, y, lastAns = 0; m; --m) {
        cin >> x >> y;
        auto [l, r] = minmax({(x + lastAns) % n + 1, (y + lastAns) % n + 1});
        cout << (lastAns = query(l, r)) << "\n";
    }
}

signed main() {
    
    FIO;
    TEST {
        solve();
    }

    return 0;
}

P5356 [Ynoi Easy Round 2017] 由乃打扑克

区间加，区间查询第k小。

考虑前面的教主的魔法，区别在于查询的内容。我们发现那道题查询的数v存在一个单调性，即小于等于其值的数是否小于k。那么分界点正好就是我们要的答案咯，所以在那道题的基础上再套个二分即可。

#include <bits/stdc++.h>
#define FIO cin.tie(0); ios::sync_with_stdio(false)
#define all(x) (x).begin(), (x).end()
#define fi first
#define se second
#define TEST
#define TESTS int t = 1; cin >> t; while (t--)

#if 1
#define int i64
#define inf 0x3f3f3f3f3f3f3f3fLL
#else
#define inf 0x3f3f3f3f
#endif

using namespace std;
using i64 = long long;
using u32 = unsigned;
using u64 = unsigned long long;
using pii = std::pair<int, int>;

inline char nc() {
    static char buf[1 << 20], *p1, *p2;
    return p1 == p2 && (p2 = (p1 = buf) + fread(buf, 1, 1 << 20, stdin), p1 == p2) ? EOF : *p1++;
}
#ifndef ONLINE_JUDGE
#define nc getchar
#endif
void read() {}
template<typename T, typename... T2> 
inline void read(T &x, T2 &... oth) {
    x = 0; char c = nc(), up = c;
    while(!isdigit(c)) up = c, c = nc();
    while(isdigit(c)) x = x * 10 + c - '0', c = nc();
    up == '-' ? x = -x : 0;
    read(oth...);
}

constexpr int N = 1e5 + 10;
constexpr int MOD = 998244353;

int a[N], sortv[N], bi[N], bl[N], br[N];
int lazy[N];

int queryMin(int l, int r) {
    int res = inf;
    if (bi[l] == bi[r]) {
        for (int i = l; i <= r; ++i) res = min(res, a[i] + lazy[bi[l]]);
    } else {
        for (int i = l; i <= br[bi[l]]; ++i) {
            res = min(res, a[i] + lazy[bi[l]]);
        }
        for (int i = bi[l] + 1; i < bi[r]; ++i) {
            res = min(res, sortv[bl[i]] + lazy[i]);
        }
        for (int i = bl[bi[r]]; i <= r; ++i) {
            res = min(res, a[i] + lazy[bi[r]]);
        }
    }
    return res;
}

int queryMax(int l, int r) {
    int res = -inf;
    if (bi[l] == bi[r]) {
        for (int i = l; i <= r; ++i) res = max(res, a[i] + lazy[bi[l]]);
    } else {
        for (int i = l; i <= br[bi[l]]; ++i) {
            res = max(res, a[i] + lazy[bi[l]]);
        }           
        for (int i = bi[l] + 1; i < bi[r]; ++i) {
            res = max(res, sortv[br[i]] + lazy[i]);
        }
        for (int i = bl[bi[r]]; i <= r; ++i) {
            res = max(res, a[i] + lazy[bi[r]]);
        }
    }
    return res;
}

int getBlockCnt(int i, int k) {
    k -= lazy[i];
    int lo = bl[i], hi = br[i];
    if (k < sortv[lo]) return 0;
    if (k >= sortv[hi]) return hi - lo + 1;
    while (lo < hi) {
        int mid = lo + hi + 1 >> 1;
        if (sortv[mid] <= k) lo = mid;
        else hi = mid - 1;
    }
    return lo - bl[i] + 1;
}

// 小于等于k的元素有多少个
int getCnt(int l, int r, int k) {
    int res = 0;
    if (bi[l] == bi[r]) {
        for (int i = l; i <= r; ++i) res += (a[i] + lazy[bi[l]] <= k);
    } else {
        for (int i = l; i <= br[bi[l]]; ++i) res += (a[i] + lazy[bi[l]] <= k);
        for (int i = bl[bi[r]]; i <= r; ++i) res += (a[i] + lazy[bi[r]] <= k);
        for (int i = bi[l] + 1; i < bi[r]; ++i) {
            res += getBlockCnt(i, k);
        }
    }
    return res;
}

int query(int l, int r, int k) {
    if (k < 1 || k > r - l + 1) {
        return -1;
    }
    int lo = queryMin(l, r);
    int hi = queryMax(l, r);
    while (lo < hi) {
        int mid = lo + hi >> 1;
        if (getCnt(l, r, mid) < k) lo = mid + 1;
        else hi = mid;
    }   
    return lo;
}

void innerAdd(int l, int r, int k) {
    for (int i = l; i <= r; ++i) {
        a[i] += k;
    }
    for (int i = bl[bi[l]]; i <= br[bi[l]]; ++i) {
        sortv[i] = a[i];
    }
    sort(sortv + bl[bi[l]], sortv + br[bi[l]] + 1);
}

void modify(int l, int r, int k) {
    if (bi[l] == bi[r]) {
        innerAdd(l, r, k);
    } else {
        innerAdd(l, br[bi[l]], k);
        innerAdd(bl[bi[r]], r, k);
        for (int i = bi[l] + 1; i < bi[r]; ++i) {
            lazy[i] += k;
        }
    }
}

void solve() {
    int n, m;
    cin >> n >> m;
    for (int i = 1; i <= n; ++i) {
        cin >> a[i];
        sortv[i] = a[i];
    }
    int blen = sqrt(n / 2 + 1);
    int bnum = (n + blen - 1) / blen;
    for (int i = 1; i <= n; ++i) {
        bi[i] = (i - 1) / blen + 1;
    }
    for (int i = 1; i <= bnum; ++i) {
        bl[i] = (i - 1) * blen + 1;
        br[i] = min(n, i * blen);
        sort(sortv + bl[i], sortv + br[i] + 1);
    }
    while (m--) {
        int op, l, r, k;
        cin >> op >> l >> r >> k;
        if (op == 1) {
            cout << query(l, r, k) << "\n";
        } else {
            modify(l, r, k);
        }
    }
}

signed main() {
    
    FIO;
    TEST {
        solve();
    }

    return 0;
}

P3863 序列

一个序列，两种操作，第i个操作在第i个时刻发生。第一种操作区间加，第二种查询某个位置的值在该操作发生之前有几个时刻不小于值v。

还是蛮经典的一道题，这次我们不对原序列分块，转而处理时间序列。我们将区间加改成差分，即在左端点加，在右端点右边减。这样我们把所有操作都转为了单点操作，把所有操作挂在序列的对应位置上，然后序列从左到右依次处理所有操作。

从操作角度看这是一种离线做法，从序列从左往右依次处理的角度看这本质上又是对前面的差分求前缀和，或者说类似扫描线的做法，依次扫过去。在这种做法下，我们每次只关心一个时刻某一个位置上的值，所以不妨把区间加的影响视为对所有数的影响，因为处理某个区间加前还没有加，处理完这个区间加（也就是做完其右端点右边的减）之后该区间加操作也再也不会对后续产生影响，所以可以这样等效的看待。这样，在原序列的某个位置加，相当于在时间序列的这个时刻开始到时间序列末尾整个区间加某个数，第二种查询操作相当于查询时间序列开头到这个时刻前的区间大于等于$a[i]-v$的个数。定睛一看，这不就是教主的魔法么？只不过处理的序列变成了时间序列。老做法，不赘述。

#include <bits/stdc++.h>
#define FIO cin.tie(0); ios::sync_with_stdio(false)
#define all(x) (x).begin(), (x).end()
#define fi first
#define se second
#define TEST
#define TESTS int t = 1; cin >> t; while (t--)

#if 1
#define int i64
#define inf 0x3f3f3f3f3f3f3f3fLL
#else
#define inf 0x3f3f3f3f
#endif

using namespace std;
using i64 = long long;
using u32 = unsigned;
using u64 = unsigned long long;
using pii = std::pair<int, int>;

inline char nc() {
    static char buf[1 << 20], *p1, *p2;
    return p1 == p2 && (p2 = (p1 = buf) + fread(buf, 1, 1 << 20, stdin), p1 == p2) ? EOF : *p1++;
}
#ifndef ONLINE_JUDGE
#define nc getchar
#endif
void read() {}
template<typename T, typename... T2> 
inline void read(T &x, T2 &... oth) {
    x = 0; char c = nc(), up = c;
    while(!isdigit(c)) up = c, c = nc();
    while(isdigit(c)) x = x * 10 + c - '0', c = nc();
    up == '-' ? x = -x : 0;
    read(oth...);
}

constexpr int N = 1e5 + 10;
constexpr int MOD = 998244353;

int a[N], t[N], v[N], bi[N], bl[N], br[N], lazy[N];

void innerAdd(int l, int r, int k) {
    for (int i = l; i <= r; ++i) {
        t[i] += k;
    }
    for (int i = bl[bi[l]]; i <= br[bi[l]]; ++i) {
        v[i] = t[i];
    }
    sort(v + bl[bi[l]], v + br[bi[l]] + 1);
}

void modify(int l, int r, int x) {
    if (bi[l] == bi[r]) {
        innerAdd(l, r, x);
    } else {
        innerAdd(l, br[bi[l]], x);
        innerAdd(bl[bi[r]], r, x);
        for (int i = bi[l] + 1; i < bi[r]; ++i) {
            lazy[i] += x;
        }
    }
}

int query(int l, int r, int x) {
    int res = 0;
    if (bi[l] == bi[r]) {
        for (int i = l; i <= r; ++i) res += (t[i] + lazy[bi[l]] >= x);
    } else {
        for (int i = l; i <= br[bi[l]]; ++i) res += (t[i] + lazy[bi[l]] >= x);
        for (int i = bl[bi[r]]; i <= r; ++i) res += (t[i] + lazy[bi[r]] >= x);
        for (int i = bi[l] + 1; i < bi[r]; ++i) {
            res += (v + br[i] + 1 - lower_bound(v + bl[i], v + br[i] + 1, x - lazy[i]));
        }
    }
    return res;
}

void solve() {
    int n, q;
    cin >> n >> q;
    for (int i = 1; i <= n; ++i) {
        cin >> a[i];
    }
    q++;
    int blen = sqrt(q);
    int bnum = (q + blen - 1) / blen;
    for (int i = 1; i <= q; ++i) {
        bi[i] = (i - 1) / blen + 1;
    }
    for (int i = 1; i <= bnum; ++i) {
        bl[i] = (i - 1) * blen + 1;
        br[i] = min(i * blen, q);
    }
    vector<vector<array<int, 4>>> quer(n + 1);
    int cnt = 0;
    for (int i = 1; i < q; ++i) {
        int op, x, y, z = 0;
        cin >> op >> x >> y;
        if (op == 1) {
            cin >> z;
            quer[x].push_back({op, i, z});
            if (y < n) quer[y + 1].push_back({op, i, -z});
        } else {
            quer[x].push_back({op, i, y, cnt++});
        }
    }
    vector<int> ans(cnt);
    for (int i = 1; i <= n; ++i) {
        for (auto [op, t, x, id] : quer[i]) {
            if (op == 1) {
                modify(t + 1, q, x);
            } else {
                ans[id] = query(1, t, x - a[i]);
            }
        }
    }
    for (int i = 0; i < cnt; ++i) cout << ans[i] << "\n";
}

signed main() {
    
    FIO;
    TEST {
        solve();
    }

    return 0;
}

P10590 磁力块

二维平面有若干磁力块，位于(x,y)，质量m，磁力p，吸引半径r。初始有一个磁力块，磁力块能够吸引其他块当且仅当二者距离不大于该磁力块的吸引半径，且该磁力块的磁力不小于其他块的质量。我们站在某个位置不动，可以吸引其他块，得到的其他块也可以再次用来吸其他块，问一共能吸引得到多少新磁力块。

这题本质上就是BFS，分块只是一种优化复杂度，或者说用来剪枝的方式。我们把所有磁力块按照质量升序排序再分块，块内按照其到初始位置的距离重新升序排序。然后就是BFS，每次从队列中取出一个磁力块，对每个分块，判断其最大质量是否小于等于本磁力块的磁力。如果满足，则在分块内部将距离不大于吸引半径的磁力块加入队列，同时同步移动分块左边界（因为加入队列的块无需再次搜索）。如果分块的最大质量大于本磁力块的磁力，那么首先这个分块右边的所有块都无需考虑，但是块内可能还存在满足条件的磁力块，暴力判断加入队列即可。整体复杂度$O(n\sqrt{n})$。

这题是CF远古题，结果洛谷能过，CF被卡掉了，正解是线段树，有更好的$O(n\log{n})$做法。

#include <bits/stdc++.h>
#define FIO cin.tie(0); ios::sync_with_stdio(false)
#define all(x) (x).begin(), (x).end()
#define fi first
#define se second
#define TEST
#define TESTS int t = 1; cin >> t; while (t--)

#if 1
#define int i64
#define inf 0x3f3f3f3f3f3f3f3fLL
#else
#define inf 0x3f3f3f3f
#endif

using namespace std;
using i64 = long long;
using u32 = unsigned;
using u64 = unsigned long long;
using pii = std::pair<int, int>;

inline char nc() {
    static char buf[1 << 20], *p1, *p2;
    return p1 == p2 && (p2 = (p1 = buf) + fread(buf, 1, 1 << 20, stdin), p1 == p2) ? EOF : *p1++;
}
#ifndef ONLINE_JUDGE
#define nc getchar
#endif
void read() {}
template<typename T, typename... T2> 
inline void read(T &x, T2 &... oth) {
    x = 0; char c = nc(), up = c;
    while(!isdigit(c)) up = c, c = nc();
    while(isdigit(c)) x = x * 10 + c - '0', c = nc();
    up == '-' ? x = -x : 0;
    read(oth...);
}

constexpr int N = 3e5 + 10;
constexpr int MOD = 998244353;

int x[N], y[N], m[N], p[N], r[N], a[N], mx[N], vis[N];
int bi[N], bl[N], br[N];

void solve() {
    int n;
    read(x[0], y[0], p[0], r[0], n);
    r[0] *= r[0];
    for (int i = 1; i <= n; ++i) {
        read(x[i], y[i], m[i], p[i], r[i]);
        x[i] -= x[0];
        y[i] -= y[0];
        x[i] *= x[i];
        y[i] *= y[i];
        r[i] *= r[i];
    }
    int blen = min<int>(n, sqrt(2 * n));
    int bnum = (n + blen - 1) / blen;
    for (int i = 1; i <= n; ++i) {
        bi[i] = (i - 1) / blen + 1;
        a[i] = i;
    }
    sort(a + 1, a + 1 + n, [&](auto i, auto j) {
        return m[i] < m[j];
    });
    for (int i = 1; i <= bnum; ++i) {
        bl[i] = (i - 1) * blen + 1;
        br[i] = min(i * blen, n);
        mx[i] = m[a[br[i]]];
        sort(a + bl[i], a + br[i] + 1, [&](auto i, auto j) {
            return x[i] + y[i] < x[j] + y[j];
        });
    }
    queue<int> q;
    q.push(0);
    int ans = -1;
    while (q.size()) {
        int u = q.front();
        q.pop();
        ans++;
        for (int i = 1; i <= bnum; ++i) {
            if (p[u] >= mx[i]) {
                while (bl[i] <= br[i] && (vis[a[bl[i]]] || x[a[bl[i]]] + y[a[bl[i]]] <= r[u])) {
                    if (!vis[a[bl[i]]]) q.push(a[bl[i]]);
                    vis[a[bl[i]]] = 1;
                    bl[i]++;
                }
            } else {
                for (int j = bl[i]; j <= br[i]; ++j) {
                    if (!vis[a[j]] && p[u] >= m[a[j]] && x[a[j]] + y[a[j]] <= r[u]) {
                        vis[a[j]] = 1;
                        q.push(a[j]);
                    }
                }
                break;
            }
        }
    }
    cout << ans << "\n";
}

signed main() {
    
    FIO;
    TEST {
        solve();
    }

    return 0;
}

P5046 [Ynoi2019 模拟赛] Yuno loves sqrt technology I

静态区间逆序对数查询。强制在线。

也是个典中典的大分块，大力分类讨论来拼信息。分为散块对散块、散块对整块、整块对整块的贡献去考虑。

预处理一堆信息：$pre[i]$表示i所在分块的左边界到i的所有逆序对数，$suf[i]$表示i到i所在分块的右边界的所有逆序对数，$cnt[i][j]$表示前i块小于等于数j的数的数量，$dp[i][j]$表示第i块到第j块中逆序对的数量。$sortList$数组就是前面静态区间众数出现次数的那个信息。

还需要定义一个函数$f(x,xl,xr,y,yl,yr)$，计算第一个数在块x中位置$[xl,xr]$，第二个数在块y中位置$[yl,yr]$所能取得的所有逆序对数。这个通过上面的$sortList$数组，搭配双指针，可以快速地在$O(\sqrt{n})$的时间内计算。

查询的时候分类讨论：如果是散块，如果范围左边界刚好是分块左边界，那么答案就是$pre[r]$；如果范围左边界不是分块左边界，答案是$pre[r]-pre[l-1]-f(i,bl[i],l-1,i,l,r)$。如果涉及到整块，先拿到散对散和整对整的贡献，即$suf[l]+pre[r]+f(lb,l,br[lb],rb,bl[rb],r)+dp[lb+1][rb-1]$。然后考虑散块对整块的贡献，这时候预处理的$cnt[i][j]$就派上了用场，根据是左散块还是右散块计算对应的贡献即可。

#include <bits/stdc++.h>
#define FIO cin.tie(0); ios::sync_with_stdio(false)
#define all(x) (x).begin(), (x).end()
#define fi first
#define se second
#define TEST
#define TESTS int t = 1; cin >> t; while (t--)

#if 0
#define int i64
#define inf 0x3f3f3f3f3f3f3f3fLL
#else
#define inf 0x3f3f3f3f
#endif

using namespace std;
using i64 = long long;
using u32 = unsigned;
using u64 = unsigned long long;
using pii = std::pair<int, int>;

inline char nc() {
    static char buf[1 << 20], *p1, *p2;
    return p1 == p2 && (p2 = (p1 = buf) + fread(buf, 1, 1 << 20, stdin), p1 == p2) ? EOF : *p1++;
}
#ifndef ONLINE_JUDGE
#define nc getchar
#endif
void read() {}
template<typename T, typename... T2> 
inline void read(T &x, T2 &... oth) {
    x = 0; char c = nc(), up = c;
    while(!isdigit(c)) up = c, c = nc();
    while(isdigit(c)) x = x * 10 + c - '0', c = nc();
    up == '-' ? x = -x : 0;
    read(oth...);
}

constexpr int N = 1e5 + 10;
constexpr int B = 700 + 10;
constexpr int MOD = 998244353;

// 不愧是lxl 有够毒瘤
// 唉这种东西都是怎么想出来的（ 确实是神仙题

// 哎我错了错了再也不骂您了 别RE了让我过吧 T.T

int a[N], bi[N], bl[B], br[B];
array<int, 2> sortList[N];
int pre[N], suf[N], cnt[B][N];
i64 dp[B][B];
int t[N];
int n;

inline void add(int x, int v) {
    while (x <= n) {
        t[x] += v;
        x += x & -x;
    }
}

inline int querySum(int x) {
    int res = 0;
    while (x) {
        res += t[x];
        x -= x & -x;
    }
    return res;
}

// 计算散块贡献
inline i64 f(int x, int xl, int xr, int y, int yl, int yr) {
    i64 res = 0;
    for (int p1 = bl[x], p2 = bl[y] - 1, cnt = 0; p1 <= br[x]; ++p1) {
        if (sortList[p1][1] >= xl && sortList[p1][1] <= xr) {
            while (p2 + 1 <= br[y] && sortList[p2 + 1][0] < sortList[p1][0]) {
                p2++;
                if (sortList[p2][1] >= yl && sortList[p2][1] <= yr) {
                    cnt++;
                }
            }
            res += cnt;
        }
    }   
    return res;
}

i64 query(int l, int r) {
    i64 res = 0;
    int lb = bi[l], rb = bi[r];
    if (lb == rb) {
        if (l == bl[lb]) res = pre[r];
        else res = pre[r] - pre[l - 1] - f(lb, bl[lb], l - 1, lb, l, r);
    } else {
        res = suf[l] + pre[r] + f(lb, l, br[lb], rb, bl[rb], r) + dp[lb + 1][rb - 1];
        for (int i = l; i <= br[lb]; ++i) {
            res += cnt[rb - 1][a[i]] - cnt[lb][a[i]];
        }
        for (int i = bl[rb]; i <= r; ++i) {
            res += br[rb - 1] - bl[lb + 1] + 1 - (cnt[rb - 1][a[i]] - cnt[lb][a[i]]);
        }
    }
    return res;
}

void solve() {
    int m;
    read(n, m);
    int blen = sqrt(n / 4 + 1);
    int bnum = (n + blen - 1) / blen;
    for (int i = 1; i <= n; ++i) {
        read(a[i]);
        sortList[i] = {a[i], i};
        bi[i] = (i - 1) / blen + 1;
    }
    for (int i = 1; i <= bnum; ++i) {
        bl[i] = (i - 1) * blen + 1;
        br[i] = min(i * blen, n);
        sort(sortList + bl[i], sortList + br[i] + 1, [&](auto x, auto y) {
            if (x[0] != y[0]) return x[0] < y[0];
            return x[1] < y[1];
        });
    }
    for (int i = 1; i <= bnum; ++i) {
        for (int j = bl[i]; j <= br[i]; ++j) {
            cnt[i][a[j]]++;
            if (j != bl[i]) {
                pre[j] = pre[j - 1] + querySum(n) - querySum(a[j]);
            }
            add(a[j], 1);
        }
        for (int j = bl[i]; j <= br[i]; ++j) {
            add(a[j], -1);
        }       
        for (int j = br[i]; j >= bl[i]; --j) {
            if (j != br[i]) {
                suf[j] = suf[j + 1] + querySum(a[j]);
            }
            add(a[j], 1);
        }
        for (int j = br[i]; j >= bl[i]; --j) {
            add(a[j], -1);
        }
        for (int j = 1, tmp = 0; j <= n; ++j) {
            tmp += cnt[i][j];
            cnt[i][j] = tmp + cnt[i - 1][j];
        }
    }
    for (int i = bnum; i >= 1; --i) {
        dp[i][i] = pre[br[i]];
        for (int j = i + 1; j <= bnum; ++j) {
            dp[i][j] = dp[i + 1][j] + dp[i][j - 1] - dp[i + 1][j - 1] + f(i, bl[i], br[i], j, bl[j], br[j]);
        }
    }
    for (i64 x, y, lastAns = 0; m; --m) {
        read(x, y);
        x ^= lastAns;
        y ^= lastAns;
        cout << (lastAns = query(x, y)) << "\n";
    }
}

signed main() {
    
    FIO;
    TEST {
        solve();
    }

    return 0;
}

P3603 雪辉

树上分块板子题。n个点的树，每个点有点权，每次操作指定k条路径，计算k条路径上所有点权的种类数和所有点权的mex。

基本思路是进行分块，每个块维护一个预处理好的位图，把路径拆成若干块，用每个整块的位图和散点去更新答案位图，最后结果就是答案位图的1的数量和第一个0的位置。

两种典型的做法：重链剖分后处理dfn序列，或者随机撒点。下面依次介绍。

重链剖分

这个做法和处理普通的序列没什么区别，大体思路是这样：按照重链去划分，一条路径最多被划分成$O(\log{n})$条重链，而每条重链的dfn序号又是连续的，基于这个想法，我们可以给原dfn序列分块，预处理每个块的位图，重剖的时候每条重链内部又可以划分成一些散块和若干整块，拼答案即可。

重剖分块和线段树处理类似，由于重链和子树的dfn序号连续，可以来做路径/子树相关修改和查询的问题。

#include <bits/stdc++.h>
#define FIO cin.tie(0); ios::sync_with_stdio(false)
#define all(x) (x).begin(), (x).end()
#define fi first
#define se second
#define TEST
#define TESTS int t = 1; cin >> t; while (t--)

#if 0
#define int i64
#define inf 0x3f3f3f3f3f3f3f3fLL
#else
#define inf 0x3f3f3f3f
#endif

using namespace std;
using i64 = long long;
using u32 = unsigned;
using u64 = unsigned long long;
using pii = std::pair<int, int>;

inline char nc() {
    static char buf[1 << 20], *p1, *p2;
    return p1 == p2 && (p2 = (p1 = buf) + fread(buf, 1, 1 << 20, stdin), p1 == p2) ? EOF : *p1++;
}
#ifndef ONLINE_JUDGE
#define nc getchar
#endif
void read() {}
template<typename T, typename... T2> 
inline void read(T &x, T2 &... oth) {
    x = 0; char c = nc(), up = c;
    while(!isdigit(c)) up = c, c = nc();
    while(isdigit(c)) x = x * 10 + c - '0', c = nc();
    up == '-' ? x = -x : 0;
    read(oth...);
}

constexpr int N = 1e5 + 10;
constexpr int B = 800;
constexpr int V = 3e4 + 10;
constexpr int MOD = 998244353;

int a[N], bi[N], bl[B], br[B];
int fa[N], dep[N], sz[N], son[N], top[N], dfn[N], val[N], idx;
vector<int> e[N];
bitset<V> st[B], ans;

void dfs1(int u, int f) {
    fa[u] = f;
    dep[u] = dep[f] + 1;
    sz[u] = 1;
    for (int v : e[u]) {
        if (v == f) continue;
        dfs1(v, u);
        sz[u] += sz[v];
        if (sz[son[u]] < sz[v]) son[u] = v;
    }
}

void dfs2(int u, int t) {
    top[u] = t;
    val[dfn[u] = ++idx] = a[u];
    if (!son[u]) return;
    dfs2(son[u], t);
    for (int v : e[u]) {
        if (top[v]) continue;
        dfs2(v, v);
    }
}

void query(int l, int r) {
    if (bi[l] == bi[r]) {
        for (int i = l; i <= r; ++i) {
            ans.set(val[i]);
        }
    } else {
        for (int i = l; i <= br[bi[l]]; ++i) {
            ans.set(val[i]);
        }
        for (int i = bl[bi[r]]; i <= r; ++i) {
            ans.set(val[i]);
        }
        for (int i = bi[l] + 1; i < bi[r]; ++i) {
            ans |= st[i];
        }
    }
}

void update(int u, int v) {
    while (top[u] != top[v]) {
        if (dep[top[u]] < dep[top[v]]) swap(u, v);
        query(dfn[top[u]], dfn[u]);
        u = fa[top[u]];
    }
    if (dep[u] < dep[v]) swap(u, v);
    query(dfn[v], dfn[u]);
}

pii calc() {
    int r1 = ans.count();
    ans.flip();
    int r2 = ans._Find_first();
    return {r1, r2};
}

void solve() {
    int n, m, f;
    cin >> n >> m >> f;
    int blen = sqrt(n * 20);
    int bnum = (n + blen - 1) / blen;
    for (int i = 1; i <= n; ++i) {
        cin >> a[i];
        bi[i] = (i - 1) / blen + 1;
    }
    for (int i = 0, u, v; i < n - 1; ++i) {
        cin >> u >> v;
        e[u].push_back(v);
        e[v].push_back(u);
    }
    dfs1(1, 0);
    dfs2(1, 1);
    for (int i = 1; i <= bnum; ++i) {
        bl[i] = (i - 1) * blen + 1;
        br[i] = min(n, i * blen);
        for (int j = bl[i]; j <= br[i]; ++j) {
            st[i].set(val[j]);
        }
    }
    for (int k, lastAns = 0; m; --m) {
        cin >> k;
        ans.reset();
        while (k--) {
            int x, y;
            cin >> x >> y;
            if (f) {
                x ^= lastAns;
                y ^= lastAns;
            }
            update(x, y);
        }       
        auto [r1, r2] = calc();
        lastAns = r1 + r2;
        cout << r1 << " " << r2 << "\n";
    }
}

signed main() {
    
    FIO;
    TEST {
        solve();
    }

    return 0;
}

随机撒点

这个感觉比较人类智慧。

我们随机选择$O(\sqrt{n})$个点作为“关键点”，那么相邻关键点之间、非关键点到关键点之间的距离的期望都是$O(\sqrt{n})$。类似分块的思想，我们预处理从每个关键点开始向祖先方向跳，一直到另一个关键点的这一段左闭右开的路径上的位图，那么我们找$x$到$y$的路径，就可以分成$x$到$lca$再从$lca$到$y$的这两段，每一段又可以分成若干散点和预处理好的关键点段，类似分块的方式拼答案即可。

可以发现随机撒点并没有用到什么特殊的性质，因此这种做法比较万能，能够处理多种树上问题。不过相对应的，常数方面要大一些。

#include <bits/stdc++.h>
#define FIO cin.tie(0); ios::sync_with_stdio(false)
#define all(x) (x).begin(), (x).end()
#define fi first
#define se second
#define TEST
#define TESTS int t = 1; cin >> t; while (t--)

#if 0
#define int i64
#define inf 0x3f3f3f3f3f3f3f3fLL
#else
#define inf 0x3f3f3f3f
#endif

using namespace std;
using i64 = long long;
using u32 = unsigned;
using u64 = unsigned long long;
using pii = std::pair<int, int>;

inline char nc() {
    static char buf[1 << 20], *p1, *p2;
    return p1 == p2 && (p2 = (p1 = buf) + fread(buf, 1, 1 << 20, stdin), p1 == p2) ? EOF : *p1++;
}
#ifndef ONLINE_JUDGE
#define nc getchar
#endif
void read() {}
template<typename T, typename... T2> 
inline void read(T &x, T2 &... oth) {
    x = 0; char c = nc(), up = c;
    while(!isdigit(c)) up = c, c = nc();
    while(isdigit(c)) x = x * 10 + c - '0', c = nc();
    up == '-' ? x = -x : 0;
    read(oth...);
}

constexpr int N = 1e5 + 10;
constexpr int B = 800 + 10;
constexpr int P = 20;
constexpr int V = 3e4 + 10;
constexpr int MOD = 998244353;

int a[N];
int fa[N][P], d[N];
int vis[N], markNode[N], nodeNum[N], up[N];
vector<int> e[N];
bitset<V> st[B], ans;

mt19937 rng(time(0));

void dfs(int u, int f) {
    d[u] = d[f] + 1;
    fa[u][0] = f;
    for (int i = 1; i < P; ++i) {
        fa[u][i] = fa[fa[u][i - 1]][i - 1];
    }
    for (int v : e[u]) {
        if (v == f) continue;
        dfs(v, u);
    }
}

int getLca(int u, int v) {
    if (d[u] < d[v]) swap(u, v);
    for (int i = P - 1; i >= 0; --i) {
        if (d[fa[u][i]] >= d[v]) u = fa[u][i]; 
    }
    if (u == v) return u;
    for (int i = P - 1; i >= 0; --i) {
        if (fa[u][i] != fa[v][i]) {
            u = fa[u][i];
            v = fa[v][i];
        }
    }
    return fa[u][0];
}

void query(int x, int lca) {
    while (nodeNum[x] == 0 && x != lca) {
        ans.set(a[x]);
        x = fa[x][0];
    }
    while (up[x] > 0 && d[up[x]] >= d[lca]) {
        ans |= st[nodeNum[x]];
        x = up[x];
    }
    while (x != lca) {
        ans.set(a[x]);
        x = fa[x][0];
    }
}

void updateAns(int x, int y) {
    int lca = getLca(x, y);
    query(x, lca);
    query(y, lca);
    ans.set(a[lca]);
}

pii calc() {
    int r1 = ans.count();
    int r2 = ((~ans)._Find_first());
    return {r1, r2};    
}

void solve() {
    int n, m, f;
    cin >> n >> m >> f;
    int blen = sqrt(n * 10);
    int bnum = (n + blen - 1) / blen;
    for (int i = 1; i <= n; ++i) {
        cin >> a[i];
    }
    for (int i = 0, u, v; i < n - 1; ++i) {
        cin >> u >> v;
        e[u].push_back(v);
        e[v].push_back(u);
    }
    dfs(1, 0);
    for (int i = 1, x; i <= bnum; ++i) {
        do {
            x = rng() % n + 1;
        } while (vis[x]);
        vis[x] = 1;
        markNode[i] = x;
        nodeNum[x] = i;
    }
    for (int i = 1; i <= bnum; ++i) {
        st[i].set(a[markNode[i]]);
        int cur = fa[markNode[i]][0];
        while (cur != 0) {
            if (nodeNum[cur] > 0) {
                up[markNode[i]] = cur;
                break;
            } else {
                st[i].set(a[cur]);
                cur = fa[cur][0];
            }
        }
    }
    for (int k, lastAns = 0; m; --m) {
        ans.reset();
        cin >> k;
        while (k--) {
            int x, y;
            cin >> x >> y;
            if (f) {
                x ^= lastAns;
                y ^= lastAns;
            }
            updateAns(x, y);
        }
        auto [r1, r2] = calc();
        lastAns = r1 + r2;
        cout << r1 << " " << r2 << "\n";
    }
}

signed main() {
    
    FIO;
    TEST {
        solve();
    }

    return 0;
}

P4119 [Ynoi2018] 未来日记

把区间中所有数x改成y，查询区间第k小。

同时对序列和值域分块。预处理信息：$sum1[i][j]$表示序列前i块中值域前j块的数出现的次数，$sum2[i][j]$表示序列前i块中小于等于j的数出现的次数。

考虑修改操作。根据区间中x和y的情况，大力分类讨论：若x=y或区间中无x，直接返回；若对散块修改，直接暴力；若对整块修改，考虑整块中x和y的出现情况：若同时有x有y，则暴力修改，若只有x没有y，那么打标记，类似集合合并的方式先懒处理，在暴力修改前统一做处理。为什么这样是对的？因为一个块内同时有x和有y的次数是有限的，经过$O(\sqrt{n})$次修改块内就会变得只有一个数，因此暴力修改的次数存在一个上界，我们可以放心处理。

现在详细讨论整块内有x无y时如何处理。我们维护三个信息：$idxset[i]$表示位置i的数属于哪个集合，$valset[i][j]$表示序列第i块中数j属于哪个集合，$setval[i][j]$表示序列第i块中集合编号j对应哪个数。那么把x改成y本质上就是$setval[i][valset[i][x]]=y,swap(valset[i][x],valset[i][y])$两个操作。统一处理的时候对整块做一遍$a[i]=setval[b][idxset[i]]$即可。

考虑查询操作。我们先统计散块信息，按照值域块和具体值来统计词频。先根据出现次数确定答案是在哪个值域块，再在值域块内部确定是哪个值。单次查询操作复杂度$O(\sqrt{n})$。

难点全在思维上，想清楚了代码挺好写。第一道DS黑题纪念。

#include <bits/stdc++.h>
#define FIO cin.tie(0); ios::sync_with_stdio(false)
#define all(x) (x).begin(), (x).end()
#define fi first
#define se second
#define TEST
#define TESTS int t = 1; cin >> t; while (t--)

#if 0
#define int i64
#define inf 0x3f3f3f3f3f3f3f3fLL
#else
#define inf 0x3f3f3f3f
#endif

using namespace std;
using i64 = long long;
using u32 = unsigned;
using u64 = unsigned long long;
using pii = std::pair<int, int>;

inline char nc() {
    static char buf[1 << 20], *p1, *p2;
    return p1 == p2 && (p2 = (p1 = buf) + fread(buf, 1, 1 << 20, stdin), p1 == p2) ? EOF : *p1++;
}
#ifndef ONLINE_JUDGE
#define nc getchar
#endif
void read() {}
template<typename T, typename... T2> 
inline void read(T &x, T2 &... oth) {
    x = 0; char c = nc(), up = c;
    while(!isdigit(c)) up = c, c = nc();
    while(isdigit(c)) x = x * 10 + c - '0', c = nc();
    up == '-' ? x = -x : 0;
    read(oth...);
}

constexpr int N = 1e5 + 10;
constexpr int B = 400;
constexpr int MOD = 998244353;

int a[N], bi[N], bl[B], br[B];
int sum1[B][B], sum2[B][N], cnt1[B], cnt2[N];
int idxset[N], valset[B][N], setval[B][N];
int blen, bnum;
int n, m;

void build(int b) {
    for (int i = 1; i <= blen; ++i) {
        valset[b][setval[b][i]] = 0;
    }
    for (int i = bl[b], s = 0; i <= br[b]; ++i) {
        if (valset[b][a[i]] == 0) {
            valset[b][a[i]] = ++s;
            setval[b][s] = a[i];
        }
        idxset[i] = valset[b][a[i]];
    }
}

void lazy(int b, int x, int y) {
    valset[b][y] = valset[b][x];
    setval[b][valset[b][x]] = y;
    valset[b][x] = 0;
}

void down(int b) {
    for (int i = bl[b]; i <= br[b]; ++i) {
        a[i] = setval[b][idxset[i]];
    }
}

void innerUpdate(int l, int r, int x, int y) {
    down(bi[l]);
    for (int i = l; i <= r; ++i) {
        if (a[i] != x) continue;
        sum1[bi[i]][bi[x]]--;
        sum1[bi[i]][bi[y]]++;
        sum2[bi[i]][x]--;
        sum2[bi[i]][y]++;
        a[i] = y;
    }
    build(bi[l]);
}

void update(int l, int r, int x, int y) {
    if (x == y || sum2[bi[r]][x] - sum2[bi[l] - 1][x] == 0) {
        return;
    }
    for (int b = bi[n]; b >= bi[l]; --b) {
        sum1[b][bi[x]] -= sum1[b - 1][bi[x]];
        sum1[b][bi[y]] -= sum1[b - 1][bi[y]];
        sum2[b][x] -= sum2[b - 1][x];
        sum2[b][y] -= sum2[b - 1][y];
    }
    if (bi[l] == bi[r]) {
        innerUpdate(l, r, x, y);
    } else {
        innerUpdate(l, br[bi[l]], x, y);
        innerUpdate(bl[bi[r]], r, x, y);
        for (int i = bi[l] + 1; i < bi[r]; ++i) {
            if (sum2[i][x] == 0) continue;
            if (sum2[i][y] != 0) {
                innerUpdate(bl[i], br[i], x, y);
            } else {
                sum1[i][bi[y]] += sum2[i][x];
                sum1[i][bi[x]] -= sum2[i][x];
                sum2[i][y] += sum2[i][x];
                sum2[i][x] = 0;
                lazy(i, x, y);
            }
        }
    }
    for (int b = bi[l]; b <= bi[n]; ++b) {
        sum1[b][bi[x]] += sum1[b - 1][bi[x]];
        sum1[b][bi[y]] += sum1[b - 1][bi[y]];
        sum2[b][x] += sum2[b - 1][x];
        sum2[b][y] += sum2[b - 1][y];
    }
}

void addCnt(int l, int r) {
    for (int i = l; i <= r; ++i) {
        cnt1[bi[a[i]]]++;
        cnt2[a[i]]++;
    }
}

void clearCnt(int l, int r) {
    for (int i = l; i <= r; ++i) {
        cnt1[bi[a[i]]] = cnt2[a[i]] = 0;
    }
}

int query(int l, int r, int k) {
    int ans = 0;
    bool inner = bi[l] == bi[r];
    if (inner) {
        down(bi[l]);
        addCnt(l, r);
    } else {
        down(bi[l]);
        down(bi[r]);
        addCnt(l, br[bi[l]]);
        addCnt(bl[bi[r]], r);
    }
    int sumCnt = 0;
    int vBlock = 0;
    for (int i = 1; i <= bi[N - 1]; ++i) {
        int cnt = cnt1[i] + (inner ? 0 : sum1[bi[r] - 1][i] - sum1[bi[l]][i]);
        if (sumCnt + cnt >= k) {
            vBlock = i;
            break;
        } else {
            sumCnt += cnt;
        }
    }
    for (int i = (vBlock - 1) * blen + 1; i <= vBlock * blen; ++i) {
        int cnt = cnt2[i] + (inner ? 0 : sum2[bi[r] - 1][i] - sum2[bi[l]][i]);
        if (sumCnt + cnt >= k) {
            ans = i;
            break;
        } else {
            sumCnt += cnt;
        }
    }
    if (inner) {
        clearCnt(l, r);
    } else {
        clearCnt(l, br[bi[l]]);
        clearCnt(bl[bi[r]], r);
    }
    return ans;
}       

void solve() {
    read(n, m);
    for (int i = 1; i <= n; ++i) {
        read(a[i]);
    }
    blen = 400;
    bnum = (n + blen - 1) / blen;
    for (int i = 1; i < N; ++i) {
        bi[i] = (i - 1) / blen + 1;
    }
    for (int i = 1; i <= bnum; ++i) {
        bl[i] = (i - 1) * blen + 1;
        br[i] = min(n, i * blen);
        build(i);
    }
    for (int i = 1; i <= bnum; ++i) {
        for (int j = 1; j < B; ++j) {
            // 改成+=就 TLE 
            // why?
            sum1[i][j] = sum1[i - 1][j];
        }
        for (int j = 1; j < N; ++j) {
            sum2[i][j] = sum2[i - 1][j];
        }
        for (int j = bl[i]; j <= br[i]; ++j) {
            sum1[i][bi[a[j]]]++;
            sum2[i][a[j]]++;
        }
    }
    for (int i = 0; i < m; ++i) {
        int op, l, r, x, y;
        read(op, l, r, x);
        if (op == 1) {
            read(y);
            update(l, r, x, y);
        } else {
            cout << query(l, r, x) << "\n";
        }
    }
}

signed main() {
    
    FIO;
    TEST {
        solve();
    }

    return 0;
}

P6578 [Ynoi2019] 魔法少女网站

单点赋值，区间查询满足最大值不大于v的连续子数组的个数。

对序列分块，考虑把所有操作离线下来，每个块内依次处理范围涉及到这个块的所有操作。由于这样需要拼接答案，考虑如何合并已获得的左右两个答案块。维护答案块最长满足条件的前缀$pre$，最长满足条件的后缀$suf$，答案块的长度$len$，答案块目前的答案数量$ans$。分类讨论合并这四个信息，更新答案。

对散块就暴力更新答案信息，对整块询问就把询问编号暂存下来，等待一起处理。等到这个整块单点修改前，把存下来的所有询问统一处理，更新这些询问的所有答案。最后再对这个块做一次统一处理即可。

考虑对整块统一处理的方式。每次统一处理，我们都有一批询问编号存在$qid$数组中，考虑对$qid$按照其询问值$v$升序排序，对整个块保存下标存在$pos$数组中，将下标按照其在序列中的值升序排序。这样我们维护两个指针，一个指向$qid$，一个指向$pos$，对于每个询问，都会有一个满足其询问值的下标集合，这个下标集合正好是$pos$的某个前缀。我们按照上面讨论的方式合并更新答案，这样通过不回退的双指针统一处理了所有询问，优化了复杂度。

这道题时限非常紧，普通的排序算法会被卡。我们考虑复杂度$O(n)$的基数排序。我们取进制$S=\sqrt{V}$，类似把每个数拆成高位和低位，做两次$O(n)$的排序即可，从某种角度来看这也是对值域分块。为了优化常数，进制直接取2的幂，这样可以把除法和取余变成二进制的右移和按位与，跑起来更快。

#include <bits/stdc++.h>
#define FIO cin.tie(0); ios::sync_with_stdio(false)
#define all(x) (x).begin(), (x).end()
#define fi first
#define se second
#define TEST
#define TESTS int t = 1; cin >> t; while (t--)

#if 0
#define int i64
#define inf 0x3f3f3f3f3f3f3f3fLL
#else
#define inf 0x3f3f3f3f
#endif

using namespace std;
using i64 = long long;
using u32 = unsigned;
using u64 = unsigned long long;
using pii = std::pair<int, int>;

inline char nc() {
    static char buf[1 << 20], *p1, *p2;
    return p1 == p2 && (p2 = (p1 = buf) + fread(buf, 1, 1 << 20, stdin), p1 == p2) ? EOF : *p1++;
}
#ifndef ONLINE_JUDGE
#define nc getchar
#endif
void read() {}
template<typename T, typename... T2> 
inline void read(T &x, T2 &... oth) {
    x = 0; char c = nc(), up = c;
    while(!isdigit(c)) up = c, c = nc();
    while(isdigit(c)) x = x * 10 + c - '0', c = nc();
    up == '-' ? x = -x : 0;
    read(oth...);
}

constexpr int N = 3e5 + 10;
constexpr int B = 600 + 10;
constexpr int P = 9;
constexpr int OFFSET = (1 << P) - 1;
constexpr int MOD = 998244353;

int a[N];
int op[N], x[N], y[N], v[N];
int pos[N], qid[N], cntp, cntq;
int cntv[N], help[N];
int lst[N], nxt[N];
int pre[N], suf[N], len[N];
i64 ans[N];
int n, m;

void radix(int idx[], int val[], int siz) {
    memset(cntv, 0, sizeof(int) * B);
    for (int i = 1; i <= siz; ++i) cntv[val[idx[i]] & OFFSET]++;
    for (int i = 1; i < B; ++i)    cntv[i] += cntv[i - 1];
    for (int i = siz; i >= 1; --i) help[cntv[val[idx[i]] & OFFSET]--] = idx[i];
    memcpy(idx + 1, help + 1, siz * sizeof(int));
    memset(cntv, 0, sizeof(int) * B);
    for (int i = 1; i <= siz; ++i) cntv[val[idx[i]] >> P]++;
    for (int i = 1; i < B; ++i)    cntv[i] += cntv[i - 1];
    for (int i = siz; i >= 1; --i) help[cntv[val[idx[i]] >> P]--] = idx[i];
    memcpy(idx + 1, help + 1, siz * sizeof(int));
}

void merge(int i, int curPre, int curSuf, int curLen, i64 curAns) {
    ans[i] += 1LL * suf[i] * curPre + curAns;
    pre[i] = pre[i] + (pre[i] == len[i] ? curPre : 0);
    suf[i] = curSuf + (curSuf == curLen ? suf[i] : 0);
    len[i] += curLen;
}

void calc(int l, int r) {
    for (int i = l; i <= r; ++i) {
        pos[++cntp] = i;
        lst[i] = i - 1;
        nxt[i] = i + 1;
    }
    radix(pos, a, cntp);
    radix(qid, v, cntq);
    int curPre = 0, curSuf = 0, curLen = r - l + 1;
    i64 curAns = 0;
    for (int i = 1, j = 1, idx; i <= cntq; ++i) {
        while (j <= cntp && a[pos[j]] <= v[qid[i]]) {
            idx = pos[j];
            if (lst[idx] == l - 1) {
                curPre += nxt[idx] - idx;
            }
            if (nxt[idx] == r + 1) {
                curSuf += idx - lst[idx];
            }
            curAns += 1LL * (nxt[idx] - idx) * (idx - lst[idx]);
            lst[nxt[idx]] = lst[idx];
            nxt[lst[idx]] = nxt[idx];
            j++;
        }
        ::merge(qid[i], curPre, curSuf, curLen, curAns);
    }
    cntp = cntq = 0;
}

void compute(int l, int r) {
    for (int i = 1; i <= m; ++i) {
        if (op[i] == 1) {
            if (l <= x[i] && x[i] <= r) {
                calc(l, r);
                a[x[i]] = v[i];
            }
        } else {
            if (x[i] <= l && r <= y[i]) {
                qid[++cntq] = i;
            } else {
                for (int j = max(x[i], l); j <= min(y[i], r); ++j) {
                    if (a[j] <= v[i]) {
                        ::merge(i, 1, 1, 1, 1);
                    } else {
                        ::merge(i, 0, 0, 1, 0);
                    }
                }
            }
        }
    }
    calc(l, r);
}

void solve() {
    read(n, m);
    for (int i = 1; i <= n; ++i) read(a[i]);
    for (int i = 1; i <= m; ++i) {
        read(op[i]);
        if (op[i] == 1) {
            read(x[i], v[i]);
        } else {
            read(x[i], y[i], v[i]);
        }
    }
    int blen = 1 << P;
    int bnum = (n + blen - 1) / blen;
    for (int i = 1; i <= bnum; ++i) {
        int l = (i - 1) * blen + 1;
        int r = min(i * blen, n);
        compute(l, r);
    }
    for (int i = 1; i <= m; ++i) {
        if (op[i] == 2) {
            cout << ans[i] << "\n";
        }
    }
}

signed main() {
    
    FIO;
    TEST {
        solve();
    }

    return 0;
}

结语

分块的中心思想就是把操作拆分成散块和整块，最后拼凑出需要的答案，同时利用各种复杂度均摊的妙妙操作来优化。这个数据结构不存在什么定式，基本只能见招拆招。多写点分块题能有效地练习分类讨论的结构化思维，收获还是很大的。