由于EC-Final不会做G的离线线段树，于是打算在这方面做几道题学习一下。

题意：给定一个数列和许多询问，每次询问数列的某一段中所有不重复数字的和。比如1,2,1,2,3这个数列，1-3区间答案是3，2-5区间答案6。

解：首先发现在线不好做，尝试反着做。可以发现，若从后往前一个个将数字加入，则仅会影响加入位置到最近的相同数字之间的位置的答案。于是就预处理一下nxt并排序询问，从后往前加数，用线段树维护一下答案即可。

当然这里线段树也可以用区间树状数组代替

同时，假设强制在线，把上述的线段树可持久化一下即可

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
const int maxn=33333,maxb=111111;
int n,T,a[maxn],nxt[maxn],q;
map<int,int> ma;
pii b[maxb];
int p[maxb];
LL ans[maxb];
bool cmp(const int &x,const int &y)
{
    if (b[x].first==b[y].first) return b[x].second>b[y].second;
    return b[x].first>b[y].first;
}
struct SEG
{
    LL T[maxn<<2];//,lazy[maxn<<2];
    void clear()
	{
        memset(T,0,sizeof(T));
    }
    void change(int n,int L,int R,int l,int r,const int &x)
	{
        if (l==L&&r==R) {T[n]+=x;return;}
        int mid=(L+R)>>1;
        if (l>mid) change(n<<1|1,mid+1,R,l,r,x);
        else if (r<=mid) change(n<<1,L,mid,l,r,x);
        else {change(n<<1,L,mid,l,mid,x);change(n<<1|1,mid+1,R,mid+1,r,x);}
    }
    void change(int l,int r,int x)
	{
        change(1,1,n,l,r,x);
    }
    LL query(int n,int L,int R,const int &pos)
	{
        if (L==R) return T[n];
        int mid=(L+R)>>1;
        if (pos>mid) return T[n]+query(n<<1|1,mid+1,R,pos);
        else return T[n]+query(n<<1,L,mid,pos);
    }
    LL query(const int &pos){return query(1,1,n,pos);}
}seg;
int main()
{
    read(T);
    while (T--)
    {
        seg.clear();
        ma.clear();
        read(n);
        rep(i,1,n) read(a[i]);
        per(i,n,1) 
        {
            int temp=ma[a[i]];
            if (temp) nxt[i]=temp-1;
            else nxt[i]=n;
            ma[a[i]]=i;
        }
        read(q);
        rep(i,1,q) read(b[i].first,b[i].second);
        rep(i,1,q) p[i]=i;
        sort(p+1,p+q+1,cmp);
        int now=1;
        per(i,n,1)
        {
            seg.change(i,nxt[i],a[i]);
            while (b[p[now]].first==i)
            {
                ans[p[now]]=seg.query(b[p[now]].second);
                now++;
            }
        }
        rep(i,1,q) printf("%lld\n",ans[i]);
    }
    return 0;
}