专栏文章

如何卡满莫队

aaaron0919
算法·理论参与者 13已保存评论 15

文章操作

快速查看文章及其快照的属性，并进行相关操作。

当前评论
15 条
当前快照
1 份
快照标识符
@mi4025l3
此快照首次捕获于
2025/11/18 11:14
3 个月前
此快照最后确认于
2026/02/11 02:31
上周
查看原文

如何卡满莫队

应该是全网最先闲。
本文教会你如何卡满莫队，并不是莫队复杂度错了。
以下她它祂牠不分。

起因

起因是这样的，我的好同学 @emmoy 学习了莫队拼上分块 plus（和最重要的循环展开）艹掉古明地枣的袜子，由于她本人常数巨大，拿下了最劣解，8700+ms 险过。
突然我就很想欺负可爱的 emmoy，于是我决定 hack 她把她 T 飞。

过程

首先，她没有打快读，我们很自然的想到拉满 n,m=5×105n,m=5\times10^5。
但那不重要，我们发现她打了分块 plus，拼上循环展开根本卡不掉，考虑对莫队下手。
我们观察她的排序比较函数：
CPP
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,yx,y 同块时按 rr 排序，所以 ll 是无序的。
注意 sort 是不稳定排序，所以说 ll 就是乱序的，所以我们希望每次移动莫队左指针，都要跑满整个块。
所以考虑如下数据（以她的块长 700700 为例）：
CPP
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
我们排完序后发现是：
CPP
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(nn)O(n\sqrt n) 次，轻松卡满。
如你所见，傲娇的 emmoy 被我黑客了。
给出这道题的（针对 emmoy）的数据生成器CPP
#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×1084.9\times10^8，相比随机数据的 3×1083\times10^8，足足慢了 60%60\%。
可惜的是 QOJ 的机子跑得飞快，每次指针移动跑 1616 次单点更新竟然可以 10s10s 内艹过去，不愧是循环展开。
所以只卡掉了 emmoy。
如果你有更厉害的 hack 欢迎交流！！

评论

共 15 条评论，欢迎与作者交流。

正在加载评论...