给定一个长度为n序列,m个询问,每次询问给定一个区间[l,r],如果这个区间里存在只出现一次的数,输出这个数(如果有多个就输出任意一个),没有就输出0,n,m<=5*10^5
输入格式:
第一行一个整数n
接下来1行n个小于5*10^5
的正整数,即序列
下面一行一个整数m
在下面m行,每行两个整数l,r
6
1 1 2 3 2 4
2
2 6
1 2
莫队板子题,分块优化查询(记录只出现一次的数在哪个块中出现)暴力分块查找
时间复杂度:msqrt(n) + nsqrt(n)
#include <iostream>
#include <math.h>
#include <bits/stdc++.h>
using namespace std;
const int maxn = 5e5 + 5;
struct node {
int l, r, id;
}q[maxn];
int col[maxn], cnt[maxn], pos[maxn + 5];
int L[maxn + 5], R[maxn + 5];
int res[maxn];
inline bool cmp(node a, node b) {
if(pos[a.l] != pos[b.l]) {
return pos[a.l] < pos[b.l];
}
if(pos[a.l] & 1) {
return a.r < b.r;
}
return a.r > b.r;
}
void add(int x) {
cnt[col[x]]++;
if (cnt[col[x]] == 1) { //如果只出现一次
res[pos[col[x]]]++; //这个数所在的块+1
} else if (cnt[col[x]] == 2){ //如果出现不止一次
res[pos[col[x]]]--; //这个数所在的块-1
}
}
void del(int x) {
cnt[col[x]]--;
if (cnt[col[x]] == 1) {//如果只出现一次
res[pos[col[x]]]++;//这个数所在的块+1
} else if (cnt[col[x]] == 0) { //如果不在这个范围内
res[pos[col[x]]]--; //这个数所在的块-1
}
}
int read() {
int ans = 0;
char ch = getchar();
while (ch < '0' || ch > '9') ch = getchar();
while (ch >= '0' && ch <= '9') {
ans = ans * 10 + ch - '0';
ch = getchar();
}
return ans;
}
int ans[maxn];
int main() {
int n, m;
int block = sqrt(maxn);
int num = maxn / block + (maxn % block != 0);
for (int i = 1; i <= maxn; i++) {
pos[i] = (i - 1) / block + 1;
}
for (int i = 1; i <= num; i++) {
L[i] = (i - 1) * block + 1;
R[i] = i * block;
}
R[num] = maxn;
n = read();
for (int i = 1; i <= n; i++) {
col[i] = read();
}
m = read();
for (int i = 1; i <= m; i++) {
q[i].l = read(); q[i].r = read();
q[i].id = i;
}
sort (q + 1, q + m + 1, cmp);
int l = 1, r = 0;
for (int i = 1; i <= m; i++) { //莫队板子
while(l < q[i].l) {
del(l++);
}
while(r < q[i].r) {
add(++r);
}
while(l > q[i].l) {
add(--l);
}
while(r > q[i].r) {
del(r--);
}
for (int j = 1; j <= num; j++) { //暴力查询只出现一次的数在哪个块中出现
if (res[j]) {
for (int k = L[j]; k <= R[j]; k++) { //查询出现的数字
if (cnt[k] == 1) {
ans[q[i].id] = k; break;
}
}
break;
}
}
}
for (int i = 1; i <= m; i++) {
printf("%d\n", ans[i]);
}
return 0;
}