题目传送门
几乎完全一样的题目（区间内不同数的个数）： 传送门
题意: 给你n个数，q次查询，问这个区间内，区间内数的和的个数有多少种，每个不同的数只能取一次。
做法：
莫队也可做，但是了解到树状数组也可以进行离线操作。思路就是，记录相同数字中上一个数字出现的位置。 按照查询区间的右端点排序，从小到大访问右端点，更新当前位置时，如果之前有出现过相同的数字，相同数字所在的位置处更新为-a[i]，否则更新为a[i]。存储答案的方式类似莫队AC代码：
#include<bits/stdc++.h> using namespace std; #define IO ios_base::sync_with_stdio(0),cin.tie(0),cout.tie(0) #define pb(x) push_back(x) #define sz(x) (int)(x).size() #define sc(x) scanf("%d",&x) #define abs(x) ((x)<0 ? -(x) : x) #define all(x) x.begin(),x.end() #define mk(x,y) make_pair(x,y) #define fin freopen("in.txt","r",stdin) #define fout freopen("out.txt","w",stdout) typedef long long ll; const int mod = 1e9+7; const double PI = 4*atan(1.0); const int maxm = 1e8+5; const int maxn = 1e6+5; const int INF = 0x3f3f3f3f; const ll LINF = 1ll<<62; struct node { int l,r; int id; }q[maxn]; int n,m; int a[maxn],pre[maxn],tmp[maxn]; ll ans[maxn],c[maxn]; inline int read() { char x; int u,flag = 0; while(x = getchar(),x<'0' || x>'9') if(x == '-') flag = 1; u = x-'0'; while(x = getchar(),x>='0' && x<='9') u = (u<<3)+(u<<1)+x-'0'; if(flag) u = -u; return u; } inline int lowbit(int x){return x&(-x);} inline void update(int x,int val) { for(int i=x;i<=n;i+=lowbit(i)) c[i]+=val; } inline ll query(int x) { ll res = 0; for(int i=x;i;i-=lowbit(i)) res+=c[i]; return res; } inline ll range_query(int l,int r) { return query(r)-query(l-1); } bool cmp(node a,node b){ if(a.r == b.r) return a.l<b.l; else return a.r<b.r; } int main() { // fin; // IO; int t = read(); while(t--) { memset(tmp,0,sizeof(tmp)); memset(c,0,sizeof(c)); n = read(); for(int i=1;i<=n;i++){ a[i] = read(); pre[i] = tmp[a[i]]; tmp[a[i]] = i; } m = read(); for(int i=1;i<=m;i++){ q[i].l = read();q[i].r = read(); q[i].id = i; } sort(q+1,q+1+m,cmp); int cnt = 1; for(int i=1;i<=m;i++) { for(;cnt<=q[i].r;cnt++) { if(pre[cnt]) update(pre[cnt],-a[cnt]); update(cnt,a[cnt]); } ans[q[i].id] = range_query(q[i].l,q[i].r); } for(int i=1;i<=m;i++) printf("%lld\n",ans[i]); } return 0; }