原题
Given a sequence of n numbers a1, a2, ..., an and a number of d-queries. A d-query is a pair (i, j) (1 ≤ i ≤ j ≤ n). For each d-query (i, j), you have to return the number of distinct elements in the subsequence ai, ai+1, ..., aj.
Input
- Line 1: n (1 ≤ n ≤ 30000).
- Line 2: n numbers a1, a2, ..., an (1 ≤ ai ≤ 106).
- Line 3: q (1 ≤ q ≤ 200000), the number of d-queries.
- In the next q lines, each line contains 2 numbers i, j representing a d-query (1 ≤ i ≤ j ≤ n).
Output
- For each d-query (i, j), print the number of distinct elements in the subsequence ai, ai+1, ..., aj in a single line.
Example
Input
5
1 1 2 1 3
3
1 5
2 4
3 5
Output
3
2
3
思路
因为这道题去学了主席树，学了点皮毛之后再看题发现普通的线段树就能做。离线处理一下，每处理到一个位置就将这个位置的贡献+1，如果这个位置的数已经出现过，将上个出现的位置贡献-1，区间查询即可。
#include <algorithm>
#include <cmath>
#include <cstdio>
#include <cstring>
#include <list>
#include <map>
#include <iostream>
#include <iomanip>
#include <queue>
#include <set>
#include <stack>
#include <string>
#include <unordered_map>
#include <vector>
#define LL long long
#define inf 0x3f3f3f3f
#define INF 0x3f3f3f3f3f3f
#define PI 3.1415926535898
#define F first
#define S second
#define endl '
'
#define lson rt << 1
#define rson rt << 1 | 1
#define lowbit(x) (x &(-x))
#define f(x, y, z) for (int x = (y), __ = (z); x < __; ++x)
#define _rep(i, a, b) for (int i = (a); i <= (b); ++i)
#define _per(i, a, b) for (int i = (a); i >= (b); --i)
using namespace std;
const int maxn = 1e6 + 7;
int n, m, a[maxn];
int tree[maxn * 4];
int lz[maxn * 4];
map<int, int> mp;
struct node {
int l, r, id, ans;
};
bool cmp1(node x, node y) {
return x.r < y.r;
}
bool cmp2(node x, node y) {
return x.id < y.id;
}
vector<node> q;
void add(int n, int index, int L, int R, int rt)
{
if (L == R)
{
tree[rt] += n;
return;
}
int mid = (L + R) / 2;
if (index <= mid) add(n, index, L, mid, lson);
else add(n, index, mid + 1, R, rson);
tree[rt] = tree[lson] + tree[rson];
}
void push_down(int rt, int l, int r) {
if (lz[rt]) {
int mid = (l + r) / 2;
lz[lson] += lz[rt];
lz[rson] += lz[rt];
tree[lson] += 1LL * (mid - l + 1) * lz[rt];
tree[rson] += 1LL * (r - mid) * lz[rt];
lz[rt] = 0;
}
}
LL query_range(int rt, int l, int r, int L, int R) {
if (l <= L && r >= R) return tree[rt];
push_down(rt, L, R);
int mid = (L + R) / 2;
LL sum = 0;
if (mid >= l) sum += query_range(lson, l, r, L, mid);
if (mid < r) sum += query_range(rson, l, r, mid + 1, R);
return sum;
}
int main() {
ios::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);
cin >> n;
_rep(i, 1, n) cin >> a[i];
cin >> m;
int x, y;
_rep(i, 1, m) {
cin >> x >> y;
q.push_back({ x, y, i, 0 });
}
sort(q.begin(), q.end(), cmp1);
int sz = q.size(), p = 0;
_rep(i, 1, n) {
if (p >= sz) break;
if (mp[a[i]]) add(-1, mp[a[i]], 1, n, 1);
add(1, i, 1, n, 1);
while (q[p].r == i) {
int l = q[p].l, r = q[p].r;
q[p].ans = query_range(1, l, r, 1, n);
p++;
if (p >= sz) break;
}
mp[a[i]] = i;
}
sort(q.begin(), q.end(), cmp2);
f(i, 0, q.size()) cout << q[i].ans << endl;
}