題目連結
題目資料：
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;
}