题目链接
题目数据：
T (1 ≤ T ≤ 10),(1 ≤ N ≤ 30,000),(0 ≤ Ai ≤ 1,000,000,000)
Q (1 ≤ Q ≤ 100,000)
题目限制：
Time limit： 3000 ms
Memory limit： 32768 kB
题目大意：
统计一个区间内不重复的数据和。
例如 ：
1 1 2 1 3
3
1 5 (1+2+3)
2 4 (1+2)
3 5 (2+1+3)
*解决方法：离线处理。（不了解的可以去百度，我也不是和了解，这算是离线处理的第一道题）
（我尽量把我理解的离散处理说一下）
*解决思路：
数据这么大，当然离散化，若不离散化，1e9咋建树；
序列如此多，当然离线化，若不离线化，1e5怎查询；
如何离散化，请看我代码，如何离线化，右点小在前。
（言归正传了哈哈哈哈哈哈哈）
第一步:离散化。离散化还不会的，看下面代码。下面说离线化的思路：
第二步：离线化：
#1，排序：
对：
1 5
2 4
3 5
按照右端点进行排序，右端点小的在前，对左端点不要求；
排序后：
2 4 （1）
1 5 （2）
3 5 （3）
#2，建树：树的叶子节点表示数据最新一次出现的位置，记录的是当前位置数据的大小。（1 1 2 1 3）
树的叶子节点: 1 2 3 4 5
记录的信息: 0 0 0 0 0 (建树时还没加入任何节点)
1&插入 1：更新树的信息：
树的叶子节点: 1 2 3 4 5
记录的信息: 1 0 0 0 0 （插入1,1最新的一次位置为1）
2&插入 1：更新树的信息：
树的叶子节点: 1 2 3 4 5
记录的信息: 0 1 0 0 0 （插入1,1最新的一次位置为2，并抹除上一次出现的位置）
3&插入 2：更新树的信息：
树的叶子节点: 1 2 3 4 5
记录的信息: 0 1 2 0 0 （插入2,2最新的一次位置为3，第一次出现）
4&插入 1：更新树的信息：
树的叶子节点: 1 2 3 4 5
记录的信息: 0 0 2 1 0 （插入1,1最新的一次位置为4，并抹除上一次出现的位置）
（这时刚好遇到排序后的第一个序列，[2，4]，统计2到4的和）
5&插入 3：更新树的信息：
树的叶子节点: 1 2 3 4 5
记录的信息: 0 0 2 1 3
(统计[1,5],[3,5]的区间和)
（看到这里你可能会想，为啥要这样处理呢？）
第一点：所有的点直插入了一次，如果对每个序列都单独建一次树的话，you can try。
第二点: 为什木要对序列按右端点小的排序呢？给一个组数据:
1 3 1 2 5
1 3
1 2
按照上面建树的过程模拟一下，看不排序直接建树，会有什么结果。
《树状数组建树》《代码是我的，不能拿走，上面解题思路是大家的》
《QQ：3237676809，一起在ACM的小路上高歌啊~~~~》
// T (1 ≤ T ≤ 10),(1 ≤ N ≤ 30,000),(0 ≤ Ai ≤ 1,000,000,000)
//Q (1 ≤ Q ≤ 100,000)
#include<map>
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
typedef long long LL;
const int N=30010;
const int M=100010;
LL a[30010],a2[30010];
struct point
{
int L,R,id;
}b[M];
LL ans[M];
LL c[N];
int vis[N];
int n,len;
// 1
void int_i(void)
{
len=0;
for(int i=1;i<=n;i++)
{
c[i]=0;
vis[i]=0;
}
return ;
}
// 2
int cmp_b(point s1,point s2)
{
return s1.R < s2.R;
}
// 3
int lowbit(int x)
{
return x&(-x);
}
// 4
void update_tree(int pos,LL x)
{
while(pos<=n)
{
c[pos]+=x;
pos+=lowbit(pos);
}
return ;
}
// 5
LL getsum(int pos)
{
LL ans=0;
while(pos>0)
{
ans+=c[pos];
pos-=lowbit(pos);
}
return ans;
}
// 6
void simplify(void)
{
sort(a2+1,a2+1+n);
len=unique(a2+1,a2+n+1) - (a2+1);
for(int i=1;i<=n;i++)
{
int pos=lower_bound(a2+1,a2+n+1,a[i]) - a2;
a[i]=pos;
}
return ;
}
int main()
{
int t,m;
scanf("%d",&t);
while(t--)
{
scanf("%d",&n);
int_i();
for(int i=1;i<=n;i++)
{
scanf("%lld",&a[i]);
a2[i]=a[i];
}
scanf("%d",&m);
for(int i=1;i<=m;i++)
{
scanf("%d%d",&b[i].L,&b[i].R);
b[i].id=i;
}
sort(b+1,b+m+1,cmp_b);
simplify();
int j=1;
for(int i=1;i<=m;i++)
{
while(j<=b[i].R)
{
if(vis[a[j]]!=0)
{
update_tree(vis[a[j]],-a2[a[j]]);
}
vis[a[j]]=j;
update_tree(j,a2[a[j]]);
j++;
}
ans[b[i].id]=getsum(b[i].R)-getsum(b[i].L-1);
}
for(int i=1;i<=m;i++)
{
printf("%lld\n",ans[i]);
}
}
return 0;
}