文章目录

题目题解代码

---

题目

题目描述 Mirko是一个非常简单的人。Mirko的朋友Darko给了他由N个自然数组成的一个数组，并问了他Q个问题。每个问题由两个整数L和R组成，要求Mirko回答在数组的第L位到第R位中恰好出现两次的不同值有多少种。

输入 第一行输入包含整数N和Q（1≤N，Q≤5*1e5）。表示数组中自然数的个数和问题的个数。 第二行输入包含N个自然数ai（ai≤1e9）。表示数组。 接下来Q行每行包含两个整数Li和Ri（1≤Li≤Ri≤N），表示一个问题询问的区间。

输出 输出Q行，每行一个整数。第i行的整数表示第i个问题的答案。

样例输入 5 1 1 2 1 1 1 1 3

样例输出 1

题解

莫队模板题，不懂莫队的戳 有人说莫队是提莫队长，emmm…

打了莫队要再离散化一下就过了

代码

#include <cstdio> #include <cstring> #include <cmath> #include <iostream> #include <algorithm> using namespace std; template <typename T> T Fabs(T x) {return x < 0 ? -x : x;} template <typename T> T Max(T x, T y) {return x > y ? x : y;} const int N = 500005; const int Q = 500005; int n, q, m, unit, curl = 1, curr = 0, answer; int cnt[N], ans[Q]; struct node { int num, id, ls; }; node a[N]; struct data { int l, r, id; bool operator < (const data &rhs) const { if(l / unit == rhs.l / unit) return r < rhs.r; return l < rhs.l; } }; data p[Q]; bool cmp1(node lhs, node rhs) { return lhs.num < rhs.num; } bool cmp2(node lhs, node rhs) { return lhs.id < rhs.id; } void add(int x) { if(cnt[a[x].ls] == 2) answer --; cnt[a[x].ls] ++; if(cnt[a[x].ls] == 2) answer ++; } void remove(int x) { if(cnt[a[x].ls] == 2) answer --; cnt[a[x].ls] --; if(cnt[a[x].ls] == 2) answer ++; } int main() { freopen("poklon.in", "r", stdin); freopen("poklon.out", "w", stdout); scanf("%d%d", &n, &q); for(int i = 1; i <= n; i ++) { scanf("%d", &a[i].num); a[i].id = i; } for(int i = 1; i <= q; i ++) { scanf("%d%d", &p[i].l, &p[i].r); p[i].id = i; } sort(a + 1, a + 1 + n, cmp1); for(int i = 1; i <= n; i ++) { if(a[i].num != a[i - 1].num) a[i].ls = ++ m; else a[i].ls = a[i - 1].ls; } sort(a + 1, a + 1 + n, cmp2); unit = sqrt(n); sort(p + 1, p + 1 + q); for(int i = 1; i <= q; i ++) { while(p[i].l < curl) add(-- curl); while(p[i].l > curl) remove(curl ++); while(p[i].r > curr) add(++ curr); while(p[i].r < curr) remove(curr --); ans[p[i].id] = answer; } for(int i = 1; i <= q; i ++) printf("%d\n", ans[i]); return 0; }