水题技巧之：如果你做莫队题时不会标准根号复杂度……

lyms_Hz17 · 2025-11-20 07:32:22 · 算法·理论

前情提要：教练墙了 luogu，但是 cnblogs 没封……

然后现在又把这个文章搬到了 luogu 上。

肯定有你不会的莫队题对吧，一定的有对么？然后呢，这篇文章可以让你把一些你不会做 O(n\sqrt m) 的题目做成 O(n\sqrt m h)（h 定义下面有说）或者 O(nm^\frac 23)，没准能水过去呢！！！

所以以下均使用数列分块入门 9 作为例题。

正文

Part I：\log 的将就，O(n\sqrt m h)

一般我们看到一个用上了莫队但是又不太会 O(1) 移动指针的东西，我们怎么办。如果只是单纯好删不好加或好加不好删的话，那可以考虑回滚莫队，可是如果既不好删也不好加呢？也许会想到二次离线或看题解一个十分唐氏的东西：用 \log 数据结构辅助维护，然后复杂度变成难看的 n\sqrt m \log n，写了这个复杂度你能过什么题？连典题区间众数都过不了好吗。

正如有人说过的：

所以复杂度注定不会非常好看（事实是难看到解不出来）。

至于思路，应该显然吧。

思考为什么分块经常和莫队搭档，因为人家可以 O(1) 修改，O(\sqrt n) 查询，和莫队的 O(n\sqrt m) 次修改，O(m) 次查询很搭。

拿线段树类比，它的单次修改复杂度是 O(\log n)，查询也是 O(\log n)，就很不搭，所以下面考虑强行平衡。

思考：为啥是 \log n？因为这是人家的层数，所以我们把层数拿出来，称其为 h，然后你就可以……砍掉一些层数。

发现线段树维护信息的方式是“合并”+“上传”，只要你把一棵线段树上面砍掉，成为线段树森林，你的层数就会变小，至于查询？整棵线段树的查询显然是 O(1) 的，散的线段树最多两棵，带 \log 查就行，合并信息？手动合并呗，这样一来，你的查询复杂度就变成了 2h + \frac {n}{2^h}。

然后你就可以微调 h 来平衡，大概就自己人工退火退一个一个跑得快的块长就行，一般考虑把 h 补成整数好些，因为这样线段树很整，实测速度也会块，而且非常方便 ZKW 线段树。然后就可以得到一个神秘的 O(n\sqrt m h) 复杂度。至于 h……反正是个位数，除非题很卡常，不然一般都能过。

注意：如果你不会 ZKW 线段树的话最好别用这个办法，毕竟递归线段树的常数摆着呢，用了也难卡过，看看下一节吧。

code

zxkqwq 写的特别快，我就算了，懒得卡常。

// code by 樓影沫瞬_Hz17
#include <bits/stdc++.h>
#define en_ putchar_unlocked('\n')
#define e_ putchar_unlocked(' ')
// #define int long long
using namespace std;
inline int in() { 
    int n = 0; char p = getchar_unlocked();
    while (p < '-') p = getchar_unlocked();
    bool f = p == '-' ? p = getchar_unlocked() : 0;
    do n = n * 10 + (p ^ 48), p = getchar_unlocked();
    while (p >= '0');
    return f ? -n : n;
}
inline int in(int &a) { return a = in(); }
inline void out(int n) {
    if(n < 0) putchar_unlocked('-'), n = -n;
    if(n > 9) out(n / 10);
    putchar_unlocked(n % 10 + '0');
}
constexpr int N = 3e5 + 10, B = 580, K = 256;
using pii = pair<int, int>;

struct query {
    int l, r, id;
} q[N];

int a[N], hs[N], pos[N], bel[N];

int L[N], R[N], cnt, n;

struct Tree {
    uint mx[K * 2], id[K * 2];
    #define ls (u << 1)
    #define rs (u << 1 | 1)
    inline void update(const int p) {
        uint u = p - L[bel[p]] + K;
        ++ mx[u], id[u] = p;
        for(u >>= 1; u; u >>= 1) {
            if(mx[ls] >= mx[rs]) mx[u] = mx[ls], id[u] = id[ls];
            else mx[u] = mx[rs], id[u] = id[rs];
        }
    }
    inline void reduce(const int p) {
        uint u = p - L[bel[p]] + K;
        -- mx[u], id[u] = p;
        for(u >>= 1; u; u >>= 1) {
            if(mx[ls] >= mx[rs]) mx[u] = mx[ls], id[u] = id[ls];
            else mx[u] = mx[rs], id[u] = id[rs];
        }
    }
} rt[N / K + 10];

int ans[N];

signed main() {
    #ifndef ONLINE_JUDGE 
        freopen("in.ru", "r", stdin);
        freopen("out.ru", "w", stdout);
    #endif
    in(n);
    for(int i = 1; i <= n; i ++) hs[i] = in(a[i]);
    for(int i = 1; i <= n; i ++) in(q[i].l), in(q[i].r), q[i].id = i, pos[i] = (i - 1) / B +1;

    for(int i = 1; R[i - 1] != n; i ++) {
        L[i] = (i - 1) * K + 1, R[i] = min(i * K, n);
        for(int j = L[i]; j <= R[i]; j ++) bel[j] = i;
    }
    sort(q + 1, q + 1 + n, [](const query &a, const query &b) 
        { return pos[a.r] == pos[b.r] ? pos[a.r] & 1 ? a.l < b.l : a.l > b.l : pos[a.r] < pos[b.r];});

    sort(hs + 1, hs + 1 + n);
    int len = unique(hs + 1, hs + 1+ n) - hs - 1;
    for(int i = 1; i <= n; i ++) 
        a[i] = lower_bound(hs + 1, hs + len + 1, a[i]) - hs;

    for(int i = 1, l = 1, r = 0, MX, ID; i <= n; i ++) {
        while(l > q[i].l) -- l, rt[bel[a[l]]].update(a[l]);
        while(r < q[i].r) ++ r, rt[bel[a[r]]].update(a[r]);
        while(l < q[i].l) rt[bel[a[l]]].reduce(a[l]), ++ l;
        while(r > q[i].r) rt[bel[a[r]]].reduce(a[r]), -- r;
        MX = 0;
        for(int i = 1; i <= bel[n]; i ++) {
            if(rt[i].mx[1] > MX) {
                MX = rt[i].mx[1];
                ID = rt[i].id[1];
            }
        }   
        ans[q[i].id] = hs[ID];
    }

    for(int i = 1; i <= n; i ++) out(ans[i]), en_;
} 
// 星間~ 干渉~ 融解~ 輪迴~ 邂逅~ 再生~ ララバイ~

Part II：个位数的块长，O(n m^{\frac {2}{3}})

这个倒是听说过呢。

如上所言，一般分块和莫队搭档都是十分好的，但是有时候，你发现：

就是如果你的修改、查询都只会做 \sqrt n，难道要做 O(n\sqrt n\sqrt m) 吗……

同样的，令块长为 B，发现你只会的是 O(B) 修改（暴力重构），O(\frac nB) 查询。

一个显然的思路是把块长改成 m^\frac 14，复杂度变成 O(nm^\frac 34)，但是这个还是很烂。

你可以考虑分两层块，也就是什么块套块，第一层块长 m^\frac 13，第二层 m^\frac 16，这样你的修改复杂度就变成了二倍常数的 O(m^\frac 16)，查询就是 O(\frac {n}{m^\frac 13} )，总的复杂度就是 O(nm^{\frac {2}{3}})，发现这个比上面的那个 O(n\sqrt m h) 劣一点，实际表现（数列分块 9 为例）和 ZKW 线段树相近，远优于普通线段树。

然后就是标题，你发现一般 m^\frac 16 不会大于个位数……

然后这个码有 Solwek 的帮助（详见），特在此感谢一下。

code

Solwek 写的特别快，我就算了，懒得卡常。

// code by 樓影沫瞬_Hz17 & Solwek
#include <bits/stdc++.h>
#define en_ putchar_unlocked('\n')
#define e_ putchar_unlocked(' ')
using namespace std;
template<typename T> inline T in() { 
    T n = 0; char p = getchar_unlocked();
    while (p < '-') p = getchar_unlocked();
    bool f = p == '-' ? p = getchar_unlocked() : 0;
    do n = n * 10 + (p ^ 48), p = getchar_unlocked();
    while (isdigit(p));
    return f ? -n : n;
}
template<typename T> inline T in(T &a) { return a = in<T>(); }
template<typename T> inline void out(T n) {
    if(n < 0) putchar_unlocked('-'), n = -n;
    if(n > 9) out(n / 10);
    putchar_unlocked(n % 10 + '0');
}
const int N = 3e5 + 10, B = 577, B2 = 64, B3 = 8;
using pii = pair<int, int>;

int a[N], n, L1[N], R1[N], bel1[N], L2[N], R2[N], bel2[N];
int hs[N];

struct query {
    int l, r, id;
} q[N];
int pos[N];

int ans[N];
uint mx1[N], mx2[N], id1[N], id2[N], cnt[N];

inline void upd(int x,int v){
    cnt[x] += v;
    int id = bel2[x], idp = bel1[x];
    mx2[id] = 0;
    for(int i = L2[id]; i <= R2[id]; i ++) {
        if(cnt[i] > mx2[id]) {
            mx2[id] = cnt[i];
            id2[id] = i;
        }
    }   
    int idl = (idp - 1) * B3 + 1;
    int idr = min(bel2[n], idl + B3 - 1);
    mx1[idp] = 0;
    for(int i = idl; i <= idr; i ++) {  
        if(mx2[i] > mx1[idp]){
            mx1[idp] = mx2[i];
            id1[idp] = id2[i];
        }
    }   
}
signed main() {
    #ifndef ONLINE_JUDGE 
        freopen("in.ru", "r", stdin);
        freopen("out.ru", "w", stdout);
    #endif
    in(n);
    for(int i = 1; i <= n; i ++) hs[i] = in(a[i]);
    for(int i = 1; i <= n; i ++) in(q[i].l), in(q[i].r), q[i].id = i;
    for(int i = 1; i <= n; i ++) pos[i] = (i - 1) / B + 1;

    for(int i = 1; R1[i - 1] != n; i ++) {
        L1[i] = (i - 1) * B2 + 1, R1[i] = min(i * B2, n);
        for(int j = L1[i]; j <= R1[i]; j ++) bel1[j] = i;
    }
    for(int i = 1; R2[i - 1] != n; i ++) {
        L2[i] = (i - 1) * B3 + 1, R2[i] = min(i * B3, n);
        for(int j = L2[i]; j <= R2[i]; j ++) bel2[j] = i;
    }

    sort(q + 1, q + 1 + n, [](query a, query b) 
        { return pos[a.l] == pos[b.l] ? pos[a.l] & 1 ? a.r < b.r : a.r > b.r : pos[a.l] < pos[b.l];});

    sort(hs + 1, hs + 1 + n);
    int len = unique(hs + 1, hs + 1+ n) - hs - 1;
    for(int i = 1; i <= n; i ++) 
        a[i] = lower_bound(hs + 1, hs + len + 1, a[i]) - hs;

    for(int i = 1, l = 1, r = 0, mx, id; i <= n; i ++) {
        while(l < q[i].l) upd(a[l], -1), l ++;
        while(l > q[i].l) l --, upd(a[l], 1);
        while(r < q[i].r) r ++, upd(a[r], 1);
        while(r > q[i].r) upd(a[r], -1), r --;
        mx = 0;
        for(int j = 1; j <= bel1[n]; j ++) {
            if(mx1[j] > mx) {
                mx = mx1[j];
                id = id1[j];
            }
        }
        ans[q[i].id] = hs[id];
    }

    for(int i = 1; i <= n; i ++) out(ans[i]), en_;
} 
// 星間~ 干渉~ 融解~ 輪迴~ 邂逅~ 再生~ ララバイ~