新手学做网站txt/百度指数三个功能模块

题目大意：

给出长度为$n$的序列$a$,$m$个询问，每次询问一段区间内仅出现了一次的数，多个则输出任意一个，否则输出0
$n,m,a_i<=5e5$

分析：

将询问离线，限制询问左指针
考虑将所有数字当前对应的合法右端点区间处理出来
每次左端点右移的时候将其对应数字的合法区间更新
过程用线段树维护
对于线段树上任一节点对应区间，记录其能被覆盖的时候，覆盖他的区间的左端点，并对这个左端点取$max$，因为如果这个区间不合法，肯定是过了左端点

代码：

原本的写的莫队被卡常了，放在最下面

#include <bits/stdc++.h>#define rep(i, st, ed) for (int i = st; i <= ed; i++)
#define rwp(i, ed, st) for (int i = ed; i >= st; i--)#define N 500005using namespace std;typedef long long ll;struct Node {int l, r, id;
}q[N];
int a[N], n, m;
int ans[N];
int f[N], ls[N];
int t[N*5], d[N*5];void read(int &x) {int f = 1; x = 0; char s = getchar();while (s < '0' || s > '9') { if (s == '-') f = - 1; s = getchar(); }while (s >= '0' && s <= '9') { x = x * 10 + (s - '0'); s = getchar(); }x = x * f;
}bool cmp(Node aa, Node bb) {return (aa.l == bb.l) ? aa.r < bb.r : aa.l < bb.l;
}void change(int x, int l, int r, int liml, int limr, int key) {if (liml > limr) return;if (l == liml && r == limr) {t[x] = max(t[x], key); return;}int mid = (l + r) >> 1;if (liml > mid) change(x*2+1, mid+1, r, liml, limr, key);else if (limr <= mid) change(x*2, l, mid, liml, limr, key);else change(x*2, l, mid, liml, mid, key), change(x*2+1, mid+1, r, mid+1, limr, key);
} void reserve(int x, int l, int r, int liml, int limr, int key) {if (liml > limr) return;if (l == liml && r == limr) {if (t[x] == key) t[x] = 0; return; } int mid = (l + r) >> 1;if (liml > mid) reserve(x*2+1, mid+1, r, liml, limr, key);else if (limr <= mid) reserve(x*2, l, mid, liml, limr, key);else reserve(x*2, l, mid, liml, mid, key), reserve(x*2+1, mid+1, r, mid+1, limr, key);
}int check(int x, int l, int r, int pos) {if (t[x]) return t[x];if (l == r) return 0;int mid = (l + r) >> 1;return (pos > mid)  ? check(x*2+1, mid+1, r, pos) : check(x*2, l, mid, pos);
}void dput(int x) {if (x > 9) dput(x/10);putchar(x%10+'0');
}int main() { //freopen("data.in", "r", stdin);read(n); rep(i, 1, n) read(a[i]);read(m); rep(i, 1, m) read(q[i].l), read(q[i].r), q[i].id = i;sort(q+1, q+m+1, cmp);for (int i = 1; i <= 5e5; i++) ls[i] = n+1;rwp(i, n, 1) f[i] = ls[a[i]], ls[a[i]] = i;rep(i, 1, 5e5) if (ls[i]) change(1, 1, n, ls[i], f[ls[i]]-1, ls[i]); for (int i = 1; i <= m; i++) {if (q[i-1].l != q[i].l) {for (int j = q[i-1].l; j < q[i].l; j++) reserve(1, 1, n, j, f[j]-1, j), change(1, 1, n, f[j], f[f[j]]-1, f[j]);}ans[q[i].id] = a[check(1, 1, n, q[i].r)];}for (int i = 1; i <= m; i++) dput(ans[i]), printf("\n");return 0;
}

这个就是莫队加指针大概是$O(m\sqrt{n})$

#include <bits/stdc++.h>#define rep(i, st, ed) for (int i = st; i <= ed; i++)
#define rwp(i, ed, st) for (int i = ed; i >= st; i--)#define N 500005using namespace std;typedef long long ll;struct Node {int l, r, id;
}q[N];
int beln[N], a[N], cnt[N], n, m, bis;
int ans[N];
int ls[N], rs[N], lst;void read(int &x) {int f = 1; x = 0; char s = getchar();while (s < '0' || s > '9') { if (s == '-') f = - 1; s = getchar(); }while (s >= '0' && s <= '9') { x = x * 10 + (s - '0'); s = getchar(); }x = x * f;
}bool cmp(Node aa, Node bb) {return (beln[aa.l] == beln[bb.l]) ? ((beln[aa.l] & 1) ? aa.r < bb.r : aa.r > bb.r): beln[aa.l] < beln[bb.l];
}void add(int x) {if (!x || x > n) return; if (cnt[a[x]] == 1) {rs[ls[a[x]]] = rs[a[x]];if (rs[a[x]]) ls[rs[a[x]]] = ls[a[x]];if (a[x] == lst) lst = ls[lst];ls[a[x]] = rs[a[x]] = 0;}++cnt[a[x]];	if (cnt[a[x]] == 1) rs[lst] = a[x], ls[a[x]] = lst, lst = a[x];
}void del(int x) {if (!x || x > n) return;if (cnt[a[x]] == 1) {rs[ls[a[x]]] = rs[a[x]];if (rs[a[x]]) ls[rs[a[x]]] = ls[a[x]];if (a[x] == lst) lst = ls[lst];ls[a[x]] = rs[a[x]] = 0;}--cnt[a[x]];if (cnt[a[x]] == 1) rs[lst] = a[x], ls[a[x]] = lst, lst = a[x];
}void write(int x) {if (x > 9) write(x/10);putchar(x%10+'0');
}int main() {read(n);rep(i, 1, n) read(a[i]);read(m); rep(i, 1, m) read(q[i].l), read(q[i].r), q[i].id = i;int siz = sqrt(n);rep(i, 1, n) beln[i] = (i-1)/siz+1;sort(q+1, q+m+1, cmp);int l = 1, r = 0; rep(i, 1, m) {while (l < q[i].l) del(l), l++;while (l > q[i].l) l--, add(l);while (r < q[i].r) r++, add(r);while (r > q[i].r) del(r), r--;if (rs[0]) ans[q[i].id] = rs[0]; else ans[q[i].id] = 0; }rep(i, 1, m) write(ans[i]), printf("\n");return 0;
}