題意

給出n個數，m個詢問，每個詢問給出一個區間，需要回答這個區間中不同的數的個數

題目

{assign var=“code” value=“DQUERY”} {if KaTeX parse error: Expected 'EOF', got '}' at position 8: par==""}? {assign var=pa…locale} {/if}

English Vietnamese
{if $par==“vn”} {literal}

Truy v?n-d

Cho m?t d?y s? n ph?n t? a1, a2, …, an và m?t s? các truy v?n-d. M?t truy v?n-d là m?t c?p (i, j) (1 ≤ i ≤ j ≤ n). V?i m?i truy v?n-d (i, j), b?n c?n tr? v? s? ph?n t? phan bi?t n?m trong d?y con ai, ai+1, …, aj.

D? li?u

Dòng 1: n (1 ≤ n ≤ 30000).
Dòng 2: n s? a1, a2, …, an (1 ≤ ai ≤ 106).
Dòng 3: q (1 ≤ q ≤ 200000), s? l??ng truy v?n- d.
Trong q dòng sau, m?i dòng ch?a 2 s? i, j bi?u th? m?t truy v?n-d (1 ≤ i ≤ j ≤ n).

K?t qu?

V?i m?i truy v?n-d (i, j), in ra s? ph?n t? phan bi?t thu?c d?y con ai, ai+1, …, aj trên m?t dòng.

Ví d?

D? li?u

5
1 1 2 1 3
3
1 5
2 4
3 5

K?t qu?

3
2
3
{/literal}{elseif ($par==“en” || $par=="")}{literal}

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
{/literal} {/if}

分析

分析:主席樹的經典運用（注意不是權值線段樹而是位置線段樹），將主席樹看作擁有n個歷史版本的線段樹, 每個線段樹表示[1,n]的區間，
節點權值為建造該線段樹為止該區間的貢獻。
當拿到一個新的元素時，如果這個元素沒被插入過，我們就直接插入。反之則刪除這個數再插入
一次這個數。也就是說，我們既能保證序列中有相同元素時，先插入位置靠后的（前面的刪掉再
插入相當于把插入位置向后挪），又能保證每一個元素在線段樹中只有一個。

AC代碼

#include<stdio.h> #include<string.h> #include<algorithm> using namespace std; typedef long long ll; const int M=3e4+10; const int N=1e6+10; int book[N],root[M];///每個數列的每個位置作為葉子節點 struct node {int l,r,sum; } s[M*40]; int tot,n,m,t,tmp,l,r; void build(int l,int r,int &x) {int now=++tot;s[now].sum=0;s[now].l=s[now].r=0;if(l==r)return ;int mid=(l+r)>>1;build(l,mid,s[now].l);build(mid+1,r,s[now].r); } void update(int l,int r,int &x,int y,int pos,int v) {s[++tot]=s[y];s[tot].sum+=v;//這樣對于查詢區間[l,r]首先需要找到第r個線段樹，該樹記錄的是[1,r]中各區間的貢獻x=tot;if(l==r)return ;int mid=(l+r)>>1;if(pos<=mid)///對于相同的數，先更新最左邊的位置update(l,mid,s[x].l,s[y].l,pos,v);elseupdate(mid+1,r,s[x].r,s[y].r,pos,v); } int query(int pos,int x,int l,int r) {if(l==r)return s[x].sum;int mid=(l+r)>>1;if(pos<=mid)return s[s[x].r].sum+query(pos,s[x].l,l,mid);elsereturn query(pos,s[x].r,mid+1,r); } int main() {tot=-1;scanf("%d",&n);build(1,n,root[0]);for(int i=1; i<=n; i++)///對于構造第i個線段樹{scanf("%d",&m);if(!book[m])update(1,n,root[i],root[i-1],i,1);///如果book[m]的值沒有出現，則只將這次出現的位置權值+1， elseelse{update(1,n,tmp,root[i-1],book[m],-1);///對于構造第i個線段樹，如果a[i]的值已經出現過了,就將上一個出現的位置權值-1update(1,n,root[i],tmp,i,1);///再將這次出現的位置權值+1}book[m]=i;///相同的數產生的貢獻，只記錄在最末尾的為止上，這樣就不會重復。}scanf("%d",&t);while(t--){scanf("%d%d",&l,&r);printf("%d\n",query(l,root[r],1,n));///這樣我們在查詢區間[l,r]時，只需要查詢一下第r棵線段樹中[l,r]的區間和即可。}return 0; } 創作挑戰賽新人創作獎勵來咯，堅持創作打卡瓜分現金大獎

總結

以上是生活随笔為你收集整理的D-query SPOJ - DQUERY(主席树求区间中不同的数的个数)的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。