如何卡满莫队

· · 算法·理论

如何卡满莫队

应该是全网最先闲。

本文教会你如何卡满莫队，并不是莫队复杂度错了。

以下她它祂牠不分。

起因

起因是这样的，我的好同学 @emmoy 学习了莫队拼上分块 plus（和最重要的循环展开）艹掉古明地枣的袜子，由于她本人常数巨大，拿下了最劣解，8700+ms 险过。

突然我就很想欺负可爱的 emmoy，于是我决定 hack 她把她 T 飞。

过程

首先，她没有打快读，我们很自然的想到拉满 n,m=5\times10^5。

但那不重要，我们发现她打了分块 plus，拼上循环展开根本卡不掉，考虑对莫队下手。

我们观察她的排序比较函数：

bool cmp(const node &x,const node &y){
    if(pos[x.l]^pos[y.l]) return x.l<y.l;
    if(pos[x.l]&1) return x.r<y.r;
    return x.r>y.r;
}

如此邪恶，竟然还加了奇偶化排序优化，根本无法下手，因此考虑对排序下手。

这个排序函数在 x,y 同块时按 r 排序，所以 l 是无序的。

注意 sort 是不稳定排序，所以说 l 就是乱序的，所以我们希望每次移动莫队左指针，都要跑满整个块。

所以考虑如下数据（以她的块长 700 为例）：

500000 12
1 490000
1 495000
1 490001
1 495001
1 490002
1 495002
700 490000
700 495000
700 490001
700 495001
700 490002
700 495002

我们排完序后发现是：

1 490000
700 490000
1 490001
700 490001
1 490002
700 490002
1 495000
700 495000
1 495001
700 495001
1 495002
700 495002

非常好，这样的话左指针就会移动 O(n\sqrt n) 次，轻松卡满。

如你所见，傲娇的 emmoy 被我黑客了。

:::info[给出这道题的（针对 emmoy）的数据生成器]

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
#define int ll

const int N = 1e6 + 10;
const int INF = 1e18;
const int MOD = 998244353;

#define T0 1e6
#define Te 1e-5
#define DELTA 0.999
mt19937_64 rnd(chrono::steady_clock::now().time_since_epoch().count());
#define rand(l, r) uniform_int_distribution<int>(l, r)(rnd)
#define uniform() (double(rnd()) / rnd.max())

template <typename T>
void out(const T &t)
{
    cout << t << '\n';
}

template <typename T, typename... Args>
void out(const T &t, const Args &...rest)
{
    cout << t << ' ';
    out(rest...);
}
signed main()
{
    cin.tie(0)->sync_with_stdio(false), cout.setf(ios::fixed), cout.precision(10);

    const int n = 5e5, m = 5e5;
    out(n, m);
    for (int i = 1; i <= n; ++i)
    {
        out(rand(1, n - 1), rand(-n, n));
    }
    const int cnt = 700;
    int used = 0;
    for (int i = 1; i <= cnt; ++i)
    {
        int l = (i - 1) * 700 + 1, r = i * 700;
        for (int j = 1; j <= 175; ++j)
        {
            out(l, 490000 + j);
            out(l, 495000 + j);
            out(r, 490000 + j);
            out(r, 495000 + j);
            used += 4;
        }
    }
    for (int i = used + 1; i <= m; ++i)
    {
        int l = rand(1, n), r = rand(1, n);
        if (l > r)
        {
            swap(l, r);
        }
        out(l, r);
    }

    return 0;
}

:::

结果

这样多随几次数据就可以轻松把指针移动次数卡到 4.9\times10^8，相比随机数据的 3\times10^8，足足慢了 60\%。

可惜的是 QOJ 的机子跑得飞快，每次指针移动跑 16 次单点更新竟然可以 10s 内艹过去，不愧是循环展开。

所以只卡掉了 emmoy。

如果你有更厉害的 hack 欢迎交流！！