题解

Difficulty：6.1 / Easy+

Tag：莫队

？！原来莫队还能这么用么这能还队莫来原！？

---

假设 $n,q,V$ 同阶。

显然第二个查询就是不算重复元素，考虑莫队。显然可以 $O(\log n)$ 单点增删 $O(\log n)$ 查询。这样是 $O(n\sqrt n\log n)$ 的。

但是注意到莫队这个神奇算法增删元素与查询的次数是不一样的，增删元素的次数是查询次数的 $O(\sqrt n)$ 倍！所以搭配莫队的最佳数据结构其实是 $O(1)$ 增删 $O(\sqrt n)$ 查询，这样整体还是 $O(n\sqrt n)$！

分块即可做到这一点。

旧码风常数就是小（

#include <bits/stdc++.h>
typedef std::pair <int, int> pii;
const int N = 100000, B = 316;
int B2;
struct node{
	int l, r, x, y, id;
	bool operator < (const node &b) const{
		if(l / B2 == b.l / B2){
			if((l / B2) & 1) return r < b.r;
			else return r > b.r;
		}
		return l / B2 < b.l / B2;
	}
}q[N + 5];
namespace DS{
	int bucket[N + 5];
	int belong[N + 5], left[N + 5], right[N + 5];
	int block1[N / B + 5], block2[N / B + 5];
	void init(int n){
		for(int i = 1; i <= n; i++){
			belong[i] = i / B;
			if(!left[belong[i]]) left[belong[i]] = i;
			right[belong[i]] = i;
		}
	}
	void add(int val){
		if(!(bucket[val]++)) block2[belong[val]]++;
		block1[belong[val]]++;
	}
	void del(int val){
		if(!(--bucket[val])) block2[belong[val]]--;
		block1[belong[val]]--;
	}
	pii query(int l, int r){
		int ans = 0, ans2 = 0;
		if(belong[l] == belong[r]){
			for(int i = l; i <= r; i++){
				ans += bucket[i];
				ans2 += bool(bucket[i]);
			}
			return {ans, ans2};
		}
		int curl = belong[l], curr = belong[r];
		for(int i = l; i <= right[curl]; i++){
			ans += bucket[i];
			ans2 += bool(bucket[i]);
		}
		for(int i = curl + 1; i < curr; i++){
			ans += block1[i];
			ans2 += block2[i];
		}
		for(int i = left[curr]; i <= r; i++){
			ans += bucket[i];
			ans2 += bool(bucket[i]);
		}
		return {ans, ans2};
	}
}
int a[N + 5];
pii ans[N + 5];
int n, m;
int main(){
	std::ios::sync_with_stdio(0);
	std::cin.tie(0);
	std::cout.tie(0);
	std::cin >> n >> m;
	B2 = 1.41421356 * n / sqrtl(m) + 1;
	DS::init(N);
	for(int i = 1; i <= n; i++){
		std::cin >> a[i];
	}
	for(int i = 1; i <= m; i++){
		std::cin >> q[i].l >> q[i].r >> q[i].x >> q[i].y;
		q[i].id = i;
	}
	std::sort(q + 1, q + m + 1);
	int l = 1, r = 0;
	for(int i = 1; i <= m; i++){
		while(r < q[i].r) DS::add(a[++r]);
		while(l > q[i].l) DS::add(a[--l]);
		while(l < q[i].l) DS::del(a[l++]);
		while(r > q[i].r) DS::del(a[r--]);
		ans[q[i].id] = DS::query(q[i].x, q[i].y);
	}
	for(int i = 1; i <= m; i++){
		std::cout << ans[i].first << ' ' << ans[i].second << '\n';
	}
	
	return 0;
}