给定一个长度为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; }
