|
|
|
|
|
#include <iostream>
|
|
|
|
|
|
#include <algorithm>
|
|
|
|
|
|
#include <cstring>
|
|
|
|
|
|
#include <cstdio>
|
|
|
|
|
|
#include <unordered_map>
|
|
|
|
|
|
#include <vector>
|
|
|
|
|
|
using namespace std;
|
|
|
|
|
|
typedef long long LL;
|
|
|
|
|
|
const int N = 30010, M = 100010;
|
|
|
|
|
|
typedef pair<int, int> PII;
|
|
|
|
|
|
|
|
|
|
|
|
// 线段树结构体
|
|
|
|
|
|
struct Node {
|
|
|
|
|
|
int l, r;
|
|
|
|
|
|
LL sum; // 区间和
|
|
|
|
|
|
} tr[N << 2];
|
|
|
|
|
|
|
|
|
|
|
|
int n, m; // n个数字的原始数列，m次询问
|
|
|
|
|
|
int a[N]; // 原始数组
|
|
|
|
|
|
LL ans[M]; // 问题答案
|
|
|
|
|
|
|
|
|
|
|
|
void pushup(int u) {
|
|
|
|
|
|
tr[u].sum = tr[u << 1].sum + tr[u << 1 | 1].sum;
|
|
|
|
|
|
}
|
|
|
|
|
|
|
|
|
|
|
|
void build(int u, int l, int r) {
|
|
|
|
|
|
tr[u] = {l, r};
|
|
|
|
|
|
int mid = (l + r) >> 1;
|
|
|
|
|
|
if (l == r) return;
|
|
|
|
|
|
build(u << 1, l, mid), build(u << 1 | 1, mid + 1, r);
|
|
|
|
|
|
pushup(u); // 套路，其实本题不需要pushup
|
|
|
|
|
|
}
|
|
|
|
|
|
|
|
|
|
|
|
void modify(int u, int x, int v) {
|
|
|
|
|
|
if (tr[u].l == tr[u].r) {
|
|
|
|
|
|
tr[u].sum += v;
|
|
|
|
|
|
return;
|
|
|
|
|
|
}
|
|
|
|
|
|
int mid = (tr[u].l + tr[u].r) >> 1;
|
|
|
|
|
|
if (x <= mid) modify(u << 1, x, v);
|
|
|
|
|
|
if (x > mid) modify(u << 1 | 1, x, v);
|
|
|
|
|
|
pushup(u);
|
|
|
|
|
|
}
|
|
|
|
|
|
|
|
|
|
|
|
LL query(int u, int l, int r) {
|
|
|
|
|
|
if (l <= tr[u].l && tr[u].r <= r) return tr[u].sum;
|
|
|
|
|
|
LL ans = 0;
|
|
|
|
|
|
int mid = tr[u].l + tr[u].r >> 1;
|
|
|
|
|
|
if (l <= mid) ans += query(u << 1, l, r);
|
|
|
|
|
|
if (r >= mid + 1) ans += query(u << 1 | 1, l, r);
|
|
|
|
|
|
return ans;
|
|
|
|
|
|
}
|
|
|
|
|
|
|
|
|
|
|
|
int main() {
|
|
|
|
|
|
// 加快读入
|
|
|
|
|
|
ios::sync_with_stdio(false), cin.tie(0);
|
|
|
|
|
|
int T;
|
|
|
|
|
|
cin >> T;
|
|
|
|
|
|
while (T--) {
|
|
|
|
|
|
unordered_map<int, int> b;
|
|
|
|
|
|
vector<PII> q[N]; // 这是一个二维数组,单元格中是PII
|
|
|
|
|
|
memset(ans, 0, sizeof ans);
|
|
|
|
|
|
memset(tr, 0, sizeof tr);
|
|
|
|
|
|
|
|
|
|
|
|
cin >> n;
|
|
|
|
|
|
// 构建线段树
|
|
|
|
|
|
build(1, 1, n);
|
|
|
|
|
|
|
|
|
|
|
|
for (int i = 1; i <= n; i++) cin >> a[i];
|
|
|
|
|
|
|
|
|
|
|
|
cin >> m;
|
|
|
|
|
|
for (int i = 1; i <= m; i++) {
|
|
|
|
|
|
int l, r;
|
|
|
|
|
|
cin >> l >> r;
|
|
|
|
|
|
q[r].push_back({l, i}); // 以r结尾的有一个查询:{l,id=i}
|
|
|
|
|
|
}
|
|
|
|
|
|
|
|
|
|
|
|
// 图灵树
|
|
|
|
|
|
// ① 核心：一边构建，一边查询
|
|
|
|
|
|
// ② 理解：为配合动态构建，需要以当前的进度节点为右边界进行查询，这导致了前面以右边界为索引保存PII信息
|
|
|
|
|
|
for (int i = 1; i <= n; i++) {
|
|
|
|
|
|
// 根据值，利用HASH表，找出此值原来的位置
|
|
|
|
|
|
// 如果有相同值出现，则旧位置上减去a[i],然后更新HASH，在新位置上+a[i]
|
|
|
|
|
|
if (b.count(a[i])) modify(1, b[a[i]], -a[i]);
|
|
|
|
|
|
b[a[i]] = i; // 值->号
|
|
|
|
|
|
modify(1, i, a[i]);
|
|
|
|
|
|
|
|
|
|
|
|
// 枚举以i为右端点的查询
|
|
|
|
|
|
for (auto c : q[i]) ans[c.second] = query(1, c.first, i);
|
|
|
|
|
|
}
|
|
|
|
|
|
// 输出
|
|
|
|
|
|
for (int i = 1; i <= m; i++) printf("%lld\n", ans[i]);
|
|
|
|
|
|
}
|
|
|
|
|
|
return 0;
|
|
|
|
|
|
}
|
