Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include <iostream>
- #include <cassert>
- #include <vector>
- #include <map>
- using namespace std;
- int n;
- int m;
- const int MAX = 20 * 500000;
- int pos;
- int sum[MAX], le[MAX], ri[MAX];
- typedef int tree;
- void init(tree nt, tree t) {
- sum[nt] = sum[t];
- le[nt] = le[t];
- ri[nt] = ri[t];
- }
- void update(tree t) {
- sum[t] = sum[le[t]] + sum[ri[t]];
- }
- tree add(tree t, int tl, int tr, int p, int d) {
- assert(0 <= tl && tl <= p && p < tr && tr <= n + 1);
- tree nt = pos++;
- init(nt, t);
- if (tr - tl == 1) {
- sum[nt] += d;
- return nt;
- }
- int tc = (tl + tr) / 2;
- if (p < tc)
- le[nt] = add(le[t], tl, tc, p, d);
- else
- ri[nt] = add(ri[t], tc, tr, p, d);
- update(nt);
- return nt;
- }
- int getsum(tree t, int tl, int tr, int l, int r) {
- assert(0 <= tl && tl <= l && l < r && r <= tr && tr <= n + 1);
- if (t == 0)
- return 0;
- if (tl == l && tr == r)
- return sum[t];
- int ans = 0;
- int tc = (tl + tr) / 2;
- if (l < tc)
- ans += getsum(le[t], tl, tc, l, min(r, tc));
- if (r > tc)
- ans += getsum(ri[t], tc, tr, max(l, tc), r);
- return ans;
- }
- int main() {
- ios::sync_with_stdio(false);
- cin.tie(nullptr);
- cout.tie(nullptr);
- int q;
- cin >> n >> q;
- vector<int> a(n), ne(n);
- for (int i = 0; i < n; i++)
- cin >> a[i];
- map<int, int> m;
- for (int i = n - 1; i >= 0; i--) {
- if (m.count(a[i]))
- ne[i] = m[a[i]];
- else
- ne[i] = n;
- m[a[i]] = i;
- }
- pos = 1;
- vector<tree> vt(n + 1, 0);
- vt[n] = pos++;
- for (int i = n - 1; i >= 0; i--)
- vt[i] = add(vt[i + 1], 0, n + 1, ne[i], 1);
- for (int i = 0; i < q; i++) {
- int l, r;
- cin >> l >> r;
- l--;
- cout << r - l - getsum(vt[l], 0, n + 1, l, r) << ' ';
- }
- }
Add Comment
Please, Sign In to add comment