Palindrome(莫队)

简介

题目来源:SHUOJ214

给定长度为$n$的序列 $a_1, a_2, a_3, … , a_n$ ,现有$m$个查询,每个查询给定下标 $l, r$ ,问能否通过对 $l$ 到 $r$ 之间的数字进行重新排列,使得 $l$ 到 $r$ 之间的序列成为回文串。

Input

多组数据,第一行有一个整数$T$,接下来有$T$组数据。
每组数据第一行有两个整数$n$,$m$。$(1 ≤ n ≤ 100000, 1 ≤ m ≤ 100000)$
第二行有n个数,依次为$a_1, a_2, a_3, … , a_n$。$(1 ≤ a_i ≤ 100000)$
随后有$m$行,每行有两个整数 $l, r$,代表每个查询。

Output

对于每组数据。
第一行输出 "Case x:" , $x$为第几组数据。
接下来输出$m$行,对于每个询问,如果能够构成回文串,输出"YES",否则输出"NO"

Sample Input

1
2
3
4
5
6
7
8
1
10 5
1 1 1 1 2 2 2 3 3 4
1 2
1 5
1 7
1 8
7 10

Sample Output

1
2
3
4
5
6
Case 1:
YES
YES
YES
NO
NO

HINT

第一个询问,可构成 1 1 。第二个询问,可构成 1 1 2 1 1 。第三个询问,可构成 2 1 1 2 1 1 2 。
第四、五个询问,无法构成回文串。

思路

  • 题目的意思可以理解为对于每个查询,要判断在这个区间内出现次数为奇数的数的个数。如果大于1个就不能构成回文串。
  • 直接暴力去做肯定是会TLE的0.0.
  • 由于本题的操作不带有修改,只有查询,所以可以使用莫队算法。(简单说就是在知道$[l,r]$的答案后,可以快速回答$[l-1,r],[l+1,r],[l,r-1],[l,r+1]$)具体不展开了。
  • 于是只要记录每个数在区间内的出现次数即可,并在状态转移时更新出现次数为奇数的数的个数。

代码

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
#include <bits/stdc++.h>
using namespace std;

const int maxn = 100010;
int n, m, unit, tmp;

struct query
{
int L, R, id;
} node[maxn];

int ans[maxn];
int num[maxn];
int a[maxn];

bool cmp(query a, query b)
{
if (a.L / unit != b.L / unit)
return a.L / unit < b.L / unit;
else
return a.R < b.R;
}

void add(int i)
{
num[i]++;
if (num[i] % 2)
tmp++;
else
tmp--;
}

void del(int i)
{
num[i]--;
if (num[i] % 2)
tmp++;
else
tmp--;
}

void solve()
{
tmp = 0;
memset(num, 0, sizeof(num));
memset(ans, 0, sizeof(ans));
int L = 1;
int R = 0;
for (int i = 0; i < m; i++)
{
while (node[i].L < L) add(a[--L]);
while (node[i].L > L) del(a[L++]);
while (node[i].R < R) del(a[R--]);
while (node[i].R > R) add(a[++R]);
ans[node[i].id] = tmp;
}

}

int main()
{
int T;
int kase = 0;
scanf("%d", &T);
while (T--)
{
scanf("%d%d", &n, &m);
for (int i = 1; i <= n; i++)
scanf("%d", &a[i]);
for (int i = 0; i < m; i++)
{
node[i].id = i;
scanf("%d%d", &node[i].L, &node[i].R);
}
unit = (int)sqrt(n);
sort(node, node + m, cmp);
solve();
printf("Case %d:\n", ++kase);
for (int i = 0; i < m; i++)
printf("%s\n", ans[i] > 1 ? "NO" : "YES");
}
return 0;
}
捐助作者