自动搬运

查看原文

来自洛谷，原作者为

	皎月半洒花 在那之前，你要多想。

搬运于2025-08-24 21:59:44，当前版本为作者最后更新于2020-04-12 00:47:48，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

写一个感觉比较详细(萌新友好向)的莫队做法…复杂度 $O(n\sqrt m+m\sqrt n)$ 。

考虑直接莫队的话，需要支持查询某个值域区间中的数，需要上树状数组，但这样带 $\log$ 。

于是考虑一下莫队的本质，即莫队的复杂度分析，本质上分析的是 $l,r$ 移动的复杂度，也就是修改的复杂度。所以莫队可以本质上看成一个 $O(n\sqrt m)$ 修改，$O(m)$ 询问的数据结构。观察到询问数较少，于是可以用一个可以快速修改，低速查询的 ds 来维护值域，那这自然就是值域分块，最终复杂度 $O(n\sqrt m+m\sqrt n)$ 。

以下是补充内容：

1、莫队的复杂度分析

令 $m$ 为操作数，$B$ 为块大小。考虑对于一个块内的 $l$，其 $r$ 是单增的，于是考虑如下：

• 左端点，在块内可能会一前一后这样设置，这样复杂度被卡到最满，为 $O(m\cdot B)$ ；
• 右端点，考虑各块内的询问显然都可以做到单块 $O(n)$，所以不需要考虑 $m$ 的贡献，即右端点移动的复杂度就是 $\frac{n}{B}\cdot n=\frac{n^2}{B}$。

均值一下发现 $m\cdot B+\frac{n^2}{B}\geq 2\sqrt{n^2m}=O(n\sqrt m)$ ，此时有 $m\cdot B=\frac{n^2}{B}$，解得 $B=\frac{n}{\sqrt m}$ .

所以取块大小为 $\frac{n}{\sqrt m}$ 时达到理论最优，复杂度为 $O(n\sqrt m)$ 。

2、值域分块的正确打开方式

观察到我们本质上需要一个值域上 $O(1)$ 单点加/减，$O(\sqrt n)$ 区间询问的结构，那就是普通的分块了。考虑分块维护块内和和单点值，修改的时候 $O(1)$ 修改点值和块值，询问就是朴素询问(for 过去)即可。

然后本题需要分别维护出现次数和是否出现，分别维护即可。

#include <bits/stdc++.h>

using namespace std ;

const int N = 200010 ;

void debug(int *tp, int minn, int maxn, char c){
    for (int i = minn ; i <= maxn ; ++ i)
        cout << tp[i] << " " ;  cout << c ;
}

int B ; 
int V ; 
int n, m ;
int bl[N] ;
int blv[N] ;
int res[N] ;
int ans[N] ;
int sum[N] ;
int sumr[N] ;
int sump[N] ;
int base[N] ;

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

bool comp(query a, query b){
	return (bl[a.l] ^ bl[b.l]) ? bl[a.l] < bl[b.l] : 
		   ((bl[a.l] & 1) ? a.r < b.r : a.r > b.r) ;
}
void del(int p){
	sump[base[p]] -- ; 
	sumr[blv[base[p]]] -- ;
	if (sump[base[p]] <= 0) -- sum[blv[base[p]]]  ; 
}
void add(int p){
	sump[base[p]] ++ ; 
	sumr[blv[base[p]]] ++ ; 
	if (sump[base[p]] <= 1) ++ sum[blv[base[p]]]  ; 
}
int get_ans(int l, int r){
	int ret = 0 ; 
	r = min(r, V) ; 
	if (l > V) return 0 ; 
	int nl = blv[l] + 1 ; 
	int nr = blv[r] - 1 ;
	if (blv[l] == blv[r]){
		for (int i = l ; i <= r ; ++ i)
			ret += (bool)sump[i] ; return ret ; 
	}
	for (int i = nl ; i <= nr ; ++ i) ret += sum[i] ;
	for (int i = l ; blv[i] == blv[l] && l <= V ; ++ i) ret += (bool)sump[i] ;
	for (int i = r ; blv[i] == blv[r] && r >= 0 ; -- i) ret += (bool)sump[i] ;
	return ret ;
}
int get_res(int l, int r){
	int ret = 0 ; 
	r = min(r, V) ; 
	if (l > V) return 0 ; 
	int nl = blv[l] + 1 ; 
	int nr = blv[r] - 1 ;
	if (blv[l] == blv[r]){
		for (int i = l ; i <= r ; ++ i)
			ret += sump[i] ; return ret ; 
	}
	for (int i = nl ; i <= nr ; ++ i) ret += sumr[i] ;
	for (int i = l ; blv[i] == blv[l] && l <= V ; ++ i) ret += sump[i] ;
	for (int i = r ; blv[i] == blv[r] && r >= 0 ; -- i) ret += sump[i] ;
	return ret ;
}
int main(){
	cin >> n >> m ; 
	B = 1.0 * n / sqrt(m) + 1 ; 
	for (int i = 1 ; i <= n ; ++ i)
		scanf("%d", &base[i]), V = max(V, base[i]), bl[i] = i / B ; 
	for (int i = 1 ; i <= m ; ++ i)
		scanf("%d%d%d%d", &q[i].l, &q[i].r, &q[i].a, &q[i].b), q[i].id = i ; 
	sort(q + 1, q + m + 1, comp) ; 
	int l = 1, r = 0 ; B = sqrt(V) + 1 ; 
	for (int i = 0 ; i <= V ; ++ i) blv[i] = i / B ; 
	for (int i = 1 ; i <= m ; ++ i){
		int a = q[i].a, b = q[i].b ; 
		while (l < q[i].l) del(l ++) ; 
		while (l > q[i].l) add(-- l) ; 
		while (r < q[i].r) add(++ r) ;
		while (r > q[i].r) del(r --) ;
		res[q[i].id] = get_res(a, b) ;
		ans[q[i].id] = get_ans(a, b) ; 
	}
	for (int i = 1 ; i <= m ; ++ i) 
		printf("%d %d\n", res[i], ans[i]) ; return 0 ; 
}

快来夸我码风! (超自豪

我是一个刚开始学 lxl 深刻理论的萌新，不要 d 我