莫队算法（离线查询）

莫队算法(离线查询)

SP3267 DQUERY - D-query

题意

有 n个数 m次查询

每次查询给出 范围 l 和 r

求 l ~r之间有多少不同的数

思路

(其实线段树,树状数组都可以)莫队算法

AC代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
#include<bits/stdc++.h>
#define endl "\n"
#define INF 0x3f3f3f3f3f3f3f
typedef long long ll;
const ll mod = 998244353;
const double PI = acos(-1.0);
const double EI = exp(1.0);
const int N = 1e6 + 50;
const int maxn = 1e6+50;
const double eps = 1e-8;
using namespace std;
struct query
{
	query() {}
	query(int l, int r, int id) :l(l), r(r), id(id) {}
	int l, r, id;

}q[maxn];
int read() {
	int res = 0;
	char c = getchar();
	while (!isdigit(c)) c = getchar();
	while (isdigit(c)) res = (res << 1) + (res << 3) + c - 48, c = getchar();
	return res;
}//快读
void printi(int x) {
	if (x / 10) printi(x / 10);
	putchar(x % 10 + '0');
}
int a[maxn], cnt[N], ans[maxn], belong[maxn];
bool cmp(query a, query b)//分块排序
{
	if (belong[a.l] ^ belong[b.l])
	{
		return a.l < b.l;
	}
	else
	{
		if (belong[a.l] & 1) //如果左端点在奇数块则按照右端点升序 反之相反
		{
			return a.r < b.r;
		}
		else
			return a.r > b.r;
	}
}
int add(int x)
{
	cnt[x]++;
	if (cnt[x] == 1)
		return 1;
	return 0;
}
int del(int x)
{
	cnt[x]--;
	if (cnt[x] == 0)
		return -1;
	return 0;
}
void init(int n)//分区
{
	int size = sqrt(n);
	int bnum = ceil(double(n) / size);
	for (int i = 1; i <= bnum; i++)//
	{
		for (int j = (i - 1) * size + 1; j <= i * size; j++)
		{
			belong[j] = i;
		}
	}
}
void solve()
{
	int n, m;
	cin >> n;
	init(n);
	for (int i = 1; i <= n; i++)
		cin >> a[i];
	cin >> m;
	for (int i = 1; i <= m; i++)
	{
		int l, r;
		cin >> l >> r;
		q[i] = query(l, r, i);
	}
	sort(q + 1, q + 1 + m, cmp);
	int l = 1, r = 0;
	int now = 0;
	for (int i = 1; i <= m; i++)
	{
		int ql = q[i].l, qr = q[i].r;
		while (l < ql) now += del(a[l++]);
		while (l > ql) now += add(a[--l]);
		while (r < qr) now += add(a[++r]);
		while (r > qr) now += del(a[r--]);
		ans[q[i].id] = now;
	}
	for (int i = 1; i <= m; i++)
		cout << ans[i] << endl;
}

int main()
{
	ios_base::sync_with_stdio(false);
	cin.tie(); cout.tie(0);
	//int t; cin >> t; while (t--)
	solve();
	return 0;
}
#ACM
莫队算法（离线查询）
http://example.com/2022/02/20/mo-dui-suan-fa-chi-xian-cha-xun/
作者
CynicCat
发布于
2022年2月20日
许可协议