|
|
題目鏈接：http://acm.hdu.edu.cn/showproblem.php?pid=3333
  /**//*
 題意：
給出一個長度為N(N <= 30000)的數列，然后是一連串詢問，詢問數
<= 100000，問給定區間內不同數字的和。
解法：
離線算法+離散化+線段樹
思路：
乍看之下還是區間求和，但是要求不同數字的和，這題我的做法和一
般的區間詢問略有不同，采用離線算法。因為數字的范圍較大，所以首先
是對數列進行離散化，一般可以用二分或者hash，將大范圍的數字映射到
連續的區間。然后一次性讀入所有的區間（整數對），并且對整數對的右
端點進行遞增排序。這里注意，要記錄下整數對讀入的位置下標。接下來
按順序枚舉每個數字val[i]，如果val[i]之前出現過，就將val[i]之前位
置的值刪除，然后在當前位置插入，當枚舉的位置和區間對中某個位置相
等時執行詢問操作。枚舉完畢后一次性把答案按區間輸入的下標輸出即可
。總的復雜度是O(nlog(n))。
 */
#include <iostream>
#include <algorithm>
#include <vector>
using namespace std;
#define maxn 200010
#define ll __int64
int n, m;
int val[maxn];
int tmp[maxn], tmpsize;
int bin[maxn], size;
int hash[maxn];
ll ans[maxn];
struct Pair  {
int l, r;
int idx;
};
vector < Pair > Pa;
bool cmp(Pair a, Pair b) {
return a.r < b.r;
}
void Process() {
sort(tmp, tmp + tmpsize);
bin[ size = 1 ] = tmp[0];
  for(int i = 1; i < tmpsize; i++) {
if(tmp[i] != tmp[i-1])
bin[ ++size ] = tmp[i];
 }
}
int Binary(int v) {
int l = 1;
int r = size;
while(l <= r) {
int m = (l + r) >> 1;
if(bin[m] == v)
return m;
if(v > bin[m])
l = m + 1;
else
r = m - 1;
}
}
struct Tree {
ll Sum;
}T[4*maxn];
void Build(int p, int l, int r) {
T[p].Sum = 0;
if(l == r) {
return ;
}
int mid = (l + r) >> 1;
Build(p<<1, l, mid);
Build(p<<1|1, mid+1, r);
}
void Insert(int p, int l, int r, int inPos, int val) {
if(l == inPos && inPos == r) {
T[p].Sum += val;
return ;
}
int mid = (l + r) >> 1;
if(inPos <= mid) {
Insert(p<<1, l, mid, inPos, val);
}else {
Insert(p<<1|1, mid+1, r, inPos, val);
}
T[p].Sum = T[p<<1].Sum + T[p<<1|1].Sum;
}
ll Query(int p, int l, int r, int a, int b) {
if(l == a && b == r) {
return T[p].Sum;
}
int mid = (l + r) >> 1;
ll v = 0;
if(b <= mid) {
v += Query(p<<1, l, mid, a, b);
}else if(a >= mid + 1) {
v += Query(p<<1|1, mid+1, r, a, b);
}else {
v += Query(p<<1, l, mid, a, mid);
v += Query(p<<1|1, mid+1, r, mid+1, b);
}
return v;
}
int main() {
int t;
int i, j;
scanf("%d", &t);
while(t--) {
tmpsize = 0;
scanf("%d", &n);
for(i = 1; i <= n; i++) {
scanf("%d", &val[i]);
tmp[ tmpsize++ ] = val[i];
}
Process();
Pa.clear();
scanf("%d", &m);
for(i = 0; i < m; i++) {
Pair pt;
scanf("%d %d", &pt.l, &pt.r);
pt.idx = i;
Pa.push_back(pt);
}
sort(Pa.begin(), Pa.end(), cmp);
for(i = 1; i <= size; i++)
hash[i] = 0;
Build(1, 1, n);
j = 0;
for(i = 1; i <= n; i++) {
int idx = Binary(val[i]);
int prePos = hash[idx];
if( prePos ) {
Insert(1, 1, n, prePos, -val[i]);
}
Insert(1, 1, n, i, val[i]);
hash[idx] = i;
for(; j < m; j++) {
if(Pa[j].r == i) {
ans[ Pa[j].idx ] = Query(1, 1, n, Pa[j].l, Pa[j].r);
}else
break;
}
}
for(i = 0; i < m; i++) {
printf("%I64d\n", ans[i]);
}
}
return 0;
}
|