专栏文章

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

llyms_Hz17
算法·理论参与者 13已保存评论 16

文章操作

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

当前评论
16 条
当前快照
1 份
快照标识符
@mi8bfotg
此快照首次捕获于
2025/11/21 11:43
3 个月前
此快照最后确认于
2025/12/01 20:25
3 个月前
查看原文
前情提要：教练墙了 luogu，但是 cnblogs 没封……
然后现在又把这个文章搬到了 luogu 上。
肯定有你不会的莫队题对吧，一定的有对么？然后呢，这篇文章可以让你把一些你不会做 O(nm)O(n\sqrt m) 的题目做成 O(nmh)O(n\sqrt m h)（hh 定义下面有说）或者 O(nm23)O(nm^\frac 23)，没准能水过去呢！！！
所以以下均使用数列分块入门 9 作为例题。

正文

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

一般我们看到一个用上了莫队但是又不太会 O(1)O(1) 移动指针的东西，我们怎么办。如果只是单纯好删不好加或好加不好删的话，那可以考虑回滚莫队，可是如果既不好删也不好加呢？也许会想到二次离线或看题解一个十分唐氏的东西：用 log⁡\log 数据结构辅助维护，然后复杂度变成难看的 nmlog⁡nn\sqrt m \log n，写了这个复杂度你能过什么题？连典题区间众数都过不了好吗。
正如有人说过的：
log⁡\log 算法和根号八字不合。
所以复杂度注定不会非常好看（事实是难看到解不出来）。
至于思路，应该显然吧。
思考为什么分块经常和莫队搭档，因为人家可以 O(1)O(1) 修改，O(n)O(\sqrt n) 查询，和莫队的 O(nm)O(n\sqrt m) 次修改，O(m)O(m) 次查询很搭。
拿线段树类比，它的单次修改复杂度是 O(log⁡n)O(\log n)，查询也是 O(log⁡n)O(\log n)，就很不搭，所以下面考虑强行平衡。
思考：为啥是 log⁡n\log n？因为这是人家的层数，所以我们把层数拿出来，称其为 hh，然后你就可以……砍掉一些层数。
发现线段树维护信息的方式是“合并”+“上传”，只要你把一棵线段树上面砍掉，成为线段树森林，你的层数就会变小，至于查询？整棵线段树的查询显然是 O(1)O(1) 的，散的线段树最多两棵，带 log⁡\log 查就行，合并信息？手动合并呗，这样一来，你的查询复杂度就变成了 2h+n2h2h + \frac {n}{2^h}。
然后你就可以微调 hh 来平衡，大概就自己人工退火退一个一个跑得快的块长就行，一般考虑把 hh 补成整数好些，因为这样线段树很整，实测速度也会块，而且非常方便 ZKW 线段树。然后就可以得到一个神秘的 O(nmh)O(n\sqrt m h) 复杂度。至于 hh……反正是个位数，除非题很卡常，不然一般都能过。
注意：如果你不会 ZKW 线段树的话最好别用这个办法，毕竟递归线段树的常数摆着呢，用了也难卡过，看看下一节吧。

code

zxkqwq 写的特别快，我就算了，懒得卡常。
CPP
// 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(nm23)O(n m^{\frac {2}{3}})

这个倒是听说过呢。
如上所言，一般分块和莫队搭档都是十分好的，但是有时候，你发现：
就是如果你的修改、查询都只会做 n\sqrt n，难道要做 O(nnm)O(n\sqrt n\sqrt m) 吗……
同样的，令块长为 BB，发现你只会的是 O(B)O(B) 修改（暴力重构），O(nB)O(\frac nB) 查询。
一个显然的思路是把块长改成 m14m^\frac 14，复杂度变成 O(nm34)O(nm^\frac 34)，但是这个还是很烂。
你可以考虑分两层块，也就是什么块套块，第一层块长 m13m^\frac 13，第二层 m16m^\frac 16，这样你的修改复杂度就变成了二倍常数的 O(m16)O(m^\frac 16)，查询就是 O(nm13)O(\frac {n}{m^\frac 13} )，总的复杂度就是 O(nm23)O(nm^{\frac {2}{3}})，发现这个比上面的那个 O(nmh)O(n\sqrt m h) 劣一点，实际表现（数列分块 99 为例）和 ZKW 线段树相近，远优于普通线段树。
然后就是标题，你发现一般 m16m^\frac 16 不会大于个位数……
然后这个码有 Solwek 的帮助（详见），特在此感谢一下。

code

Solwek 写的特别快，我就算了，懒得卡常。
CPP
// 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_;
} 
// 星間~ 干渉~ 融解~ 輪迴~ 邂逅~ 再生~ ララバイ~

评论

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

正在加载评论...