有任何问题欢迎留言或私聊 欢迎交流讨论哦

 原题目描述及样例在最下面

 题目意思很裸 就是询问区间内出现了多少种数字。

 既然这么裸 方法自然很多。可以莫队直接搞 主席树也行。离线下来的树状数组也行 树状数组可以搞的话 线段树肯定也行咯。

 我这里提供莫队 主席树 树状数组三种方法。
 三种方法的时间效率差不多 但是主席树特别耗内存

 (这里假设大家都会主席树 不会点这里)

 主席树的处理和树状数组有一点点像吧。

 比如建立第i个数字的线段树的时候 如果这个数字没出现过 就从这个位置开始的一条链都加1。如果这个数字之前出现过了 就把上次出现的那个位置开始的一条链都减1。保证同一数字在此区间内只计算一次。

 就这样维持区间内区间内出现了多少种数字。

#include bits/stdc .h using namespace std;typedef long long LL;const int N 1e6 5;int n,m;struct lp{ int l,r,sum;}cw[N*20];int rak[N],ar[N],br[N],vis[N],tot;void update(int l,int r,int last,int cur,int x,int v){ cw[ tot] cw[last]; cw[tot].sum cw[last].sum v; cur tot; if(l r)return; int mid (l r) 1; if(x mid)update(l,mid,cw[last].l,cw[cur].l,x,v); else update(mid 1,r,cw[last].r,cw[cur].r,x,v);int query(int l,int r,int p,int cur){ if(l r)return cw[cur].sum; int mid (l r) 1; if(p mid)return query(mid 1,r,p,cw[cur].r); else { int ans query(l,mid,p,cw[cur].l); ans cw[cw[cur].r].sum; return ans;int main(){ while(~scanf( %d , n)){ for(int i 1;i n; i){ scanf( %d , ar[i]); tot 0;cw[0].l cw[0].r cw[0].sum 0; memset(rak,0,sizeof(rak)); memset(vis,0,sizeof(vis)); for(int i 1;i n; i){ if(vis[ar[i]] 0){ update(1,n,rak[i-1],rak[i],i,1); vis[ar[i]] i; }else{ update(1,n,rak[i-1],rak[i],vis[ar[i]],-1); vis[ar[i]] i; update(1,n,rak[i],rak[i],i,1); scanf( %d , m); for(int i 0,u,v;i m; i){ scanf( %d%d , u, v); printf( %d\\n ,query(1,n,u,rak[v]) ); return 0;

 如果用莫队就很暴力咯 直接搞就行了。

 直接莫队维护一个vis数组 记录每个数出现的次数。然后随时更新答案Ans。

#include bits/stdc .h using namespace std;typedef long long LL;const int N 200005;const int M 30007;const int INF 0x3f3f3f3f;const int mod 1e9 7;int n,m;int ar[M],l[M],r[M],belong[M],cnt[1000006],ans[N];int block,num;struct lp{ int l,r,id;}cw[N];int tt;bool cmp(const lp a,const lp b){ if(belong[a.l] belong[b.l]){ return a.r b.r; return belong[a.l] belong[b.l];inline void build(){ block sqrt((double)n/log(n*1.0)*log(2.0)); num n/block;if(n%block)num ; for(int i 1;i num; i){ l[i] (i-1)*block 1;r[i] i*block; r[num] n; for(int i 1;i n; i){ belong[i] (i-1)/block 1;inline void update(int x,int d){ cnt[ar[x]] d; if(d 1){ if(cnt[ar[x]] 1)tt ; }else{ if(cnt[ar[x]] 0)tt--;int main(){ while(~scanf( %d , n)){ for(int i 1;i n; i){ scanf( %d , ar[i]); build(); tt 0; scanf( %d , m); for(int i 0;i m; i){ scanf( %d%d , cw[i].l, cw[i].r); cw[i].id i; memset(cnt,0,sizeof(cnt)); sort(cw,cw m,cmp); int L 1,R 0; for(int i 0;i m; i){ while(L cw[i].l)update(L ,-1); while(L cw[i].l)update(--L,1); while(R cw[i].r)update(R--,-1); while(R cw[i].r)update( R,1); ans[cw[i].id] tt; for(int i 0;i m; i){ printf( %d\\n ,ans[i] ); return 0;

 把询问离线处理一下就可以使用树状数组了。

 用树状数组记录区间内出现过的数。如果这个数之前没出现过 就从这里update(x,1) 如果这个数之前出现过了 update(last,-1)。保证同一数字在此区间内只计算一次。

 用一个vis数组顺便记录上一次出现的位置就行了。

 离线的树状数组还是很强大的很好玩的。大家一定要搞懂这个离线是什么意思。

#include bits/stdc .h using namespace std;typedef long long LL;const int N 30007;const int M 200005;const int INF 0x3f3f3f3f;const int mod 1e9 7;int n,m;int ar[N],sum[N];struct lp{ int l,r,id;}cw[M];int ans[M],vis[1000006];int tt;bool cmp(const lp a,const lp b){ return a.r b.r;inline int lowbit(int x){ return x (-x);inline void add(int x,int d){ while(x n){ sum[x] d; x lowbit(x);inline int query(int x){ int Ans 0; while(x){ Ans sum[x]; x- lowbit(x); return Ans;int main(){ while(~scanf( %d , n)){ for(int i 1;i n; i){ scanf( %d , ar[i]); tt 0; scanf( %d , m); for(int i 0;i m; i){ scanf( %d%d , cw[i].l, cw[i].r); cw[i].id i; sort(cw,cw m,cmp); memset(sum,0,sizeof(sum)); memset(vis,0,sizeof(vis)); for(int i 1,j 0;i n j m; i){ if(vis[ar[i]]){ add(vis[ar[i]],-1); vis[ar[i]] i; add(vis[ar[i]],1); while(j m cw[j].r i){ ans[cw[j].id] query(cw[j].r)-query(cw[j].l-1); for(int i 0;i m; i){ printf( %d\\n ,ans[i] ); return 0;

English Vietnamese
Given a sequence of n numbers a1, a2, …, an and a number of d-queries. A d-query is a pair (i, j) (1 ≤ i ≤ j ≤ n). For each d-query (i, j), you have to return the number of distinct elements in the subsequence ai, ai 1, …, aj.

Input
Line 1: n (1 ≤ n ≤ 30000).
Line 2: n numbers a1, a2, …, an (1 ≤ ai ≤ 106).
Line 3: q (1 ≤ q ≤ 200000), the number of d-queries.
In the next q lines, each line contains 2 numbers i, j representing a d-query (1 ≤ i ≤ j ≤ n).
Output
For each d-query (i, j), print the number of distinct elements in the subsequence ai, ai 1, …, aj in a single line.
Example
Input
5
1 1 2 1 3
3
1 5
2 4
3 5

Output
3
2
3