给n个数， m个询问， 每次询问输出区间内的数的和， 相同的数只计算一次。
数组里的数是>-1e9 <1e9， 可以把它离散以后用莫队搞...
1 #include <iostream> 2 #include <vector> 3 #include <cstdio> 4 #include <cstring> 5 #include <algorithm> 6 #include <cmath> 7 #include <map> 8 #include <set> 9 #include <string> 10 #include <queue> 11 #include <stack> 12 #include <bitset> 13 using namespace std; 14 #define pb(x) push_back(x) 15 #define ll long long 16 #define mk(x, y) make_pair(x, y) 17 #define lson l, m, rt<<1 18 #define mem(a) memset(a, 0, sizeof(a)) 19 #define rson m+1, r, rt<<1|1 20 #define mem1(a) memset(a, -1, sizeof(a)) 21 #define mem2(a) memset(a, 0x3f, sizeof(a)) 22 #define rep(i, n, a) for(int i = a; i<n; i++) 23 #define fi first 24 #define se second 25 typedef pair<int, int> pll; 26 const double PI = acos(-1.0); 27 const double eps = 1e-8; 28 const int mod = 1e9+7; 29 const int inf = 1061109567; 30 const int dir[][2] = { {-1, 0}, {1, 0}, {0, -1}, {0, 1} }; 31 const int maxn = 3e5+5; 32 int a[maxn], b[maxn], c[maxn]; 33 ll ans[100005]; 34 struct node 35 { 36 int l, r, id, block; 37 bool operator < (node a)const 38 { 39 if(block == a.block) 40 return r<a.r; 41 return block<a.block; 42 } 43 }q[100005]; 44 int main() 45 { 46 int t, n, m; 47 cin>>t; 48 while(t--) { 49 scanf("%d", &n); 50 mem(c); 51 for(int i = 1; i<=n; i++) { 52 scanf("%d", &a[i]); 53 b[i-1] = a[i]; 54 } 55 sort(b, b+n); 56 int cnt = unique(b, b+n)-b; 57 for(int i = 1; i<=n; i++) { 58 a[i] = lower_bound(b, b+cnt, a[i])-b+1; 59 } 60 int BLOCK = max(1.0, sqrt(cnt*1.0)); 61 cin>>m; 62 for(int i = 0; i<m; i++) { 63 scanf("%d%d", &q[i].l, &q[i].r); 64 q[i].block = q[i].l/BLOCK; 65 q[i].id = i; 66 } 67 sort(q, q+m); 68 ll sum = 0; 69 for(int i = q[0].l; i<=q[0].r; i++) { 70 if(!c[a[i]]) { 71 sum += b[a[i]-1]; 72 } 73 c[a[i]]++; 74 } 75 ans[q[0].id] = sum; 76 for(int i = 1; i<m; i++) { 77 if(q[i].l<q[i-1].l) { 78 for(int j = q[i-1].l-1; j>=q[i].l; j--) { 79 if(!c[a[j]]) { 80 sum += b[a[j]-1]; 81 } 82 c[a[j]]++; 83 } 84 } else { 85 for(int j = q[i-1].l; j<q[i].l; j++) { 86 if(c[a[j]]==1) { 87 sum -= b[a[j]-1]; 88 } 89 c[a[j]]--; 90 } 91 } 92 if(q[i].r>q[i-1].r) { 93 for(int j = q[i-1].r+1; j<=q[i].r; j++) { 94 if(!c[a[j]]) { 95 sum += b[a[j]-1]; 96 } 97 c[a[j]]++; 98 } 99 } else { 100 for(int j = q[i-1].r; j>q[i].r; j--) { 101 if(c[a[j]] == 1) { 102 sum -= b[a[j]-1]; 103 } 104 c[a[j]]--; 105 } 106 } 107 ans[q[i].id] = sum; 108 } 109 for(int i = 0; i<m; i++) 110 printf("%I64d ", ans[i]); 111 } 112 return 0; 113 }