首页 > 代码库 > SPOJ 3267. D-query (主席树）

SPOJ 3267. D-query (主席树）

2024-09-03 01:44:20   220人阅读

A - D-query
Time Limit:1500MS     Memory Limit:0KB     64bit IO Format:%lld & %llu

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 51 1 2 1 331 52 43 5 Output 323

 （其实我觉得这道题作为主席树入门比第k大数要好很多）

大概就是从前往后，插入一个数则新建一棵树，如果之前没有出现，直接插入，如果之前出现了 ，再建一棵树删除，大概是这样。

（我说新建一棵树不是真的新建诶，学了主席树应该大概知道我的意思）

 1 #include <bits/stdc++.h> 2  3 using namespace std; 4 const int N = 30000 + 11 ; 5  6 int n,a[N],li[N],q,tot,cnt,root[N],pos[N]; 7 struct id 8 { 9     int l,r,sum;10 }tree[N*40];11 12 13 void Init()14 {15     scanf("%d",&n);16     for(int i = 1; i <= n; ++i) 17     {18         scanf("%d",a + i);19         li[i] = a[i];20     }21     sort(li+1,li+1+n);22     tot = 1 ;23     for(int i = 2 ; i <= n; ++i) if( li[i] != li[tot] ) li[++tot] = li[i];        24 }25 26 int binary_search( int num )27 {28     int l = 1 , r = tot;29     while( l <= r )30     {31         int mid = l + ((r-l)>>1);32         if(li[mid] == num) return mid;33         if(li[mid] < num) l = mid + 1;34         else r = mid - 1;35     } 36     return -1;37 }38 39 void updata(int l,int r,int &x,int y,int posi,int add)40 {41     tree[++cnt] = tree[y] ; x = cnt; tree[cnt].sum += add;42     if(l == r) return ;43     int mid = l + ((r-l)>>1);44     if(posi <= mid) updata(l,mid,tree[x].l,tree[y].l,posi,add);45     else updata(mid+1,r,tree[x].r,tree[y].r,posi,add);46 }47 48 int query( int num,int L,int R,int l,int r )49 {50     if(L ==l && R == r) return tree[num].sum; 51     int mid = L + ((R-L)>>1);52     if(r <= mid) return query(tree[num].l,L,mid,l,r);53     else if(l > mid) return query(tree[num].r,mid+1,R,l,r);54     else return query(tree[num].l,L,mid,l,mid) + query(tree[num].r,mid+1,R,mid+1,r);55 }56 57 void Solve( )58 {59     for(int i = 1 ; i <= n; ++i)60     {61         int num = binary_search(a[i]);62         updata(1,n,root[i],root[i-1],i,1);63         if( pos[num] ) updata(1,n,root[i],root[i],pos[num],-1);64         pos[num] = i;65     }66     scanf("%d",&q);67     for(int i = 1 ; i <= q; ++i)68     {69         int l, r;70         scanf("%d%d",&l,&r);71         printf("%d\n",query(root[r],1,n,l,r));72     }73 }74 75 int main( )76 {77 //    freopen("spoj3267.in","r",stdin);78 //    freopen("spoj3267.out","w",stdout);79     Init();80     Solve();81     fclose(stdin);82     fclose(stdout);83     return 0;84 }

 

SPOJ 3267. D-query (主席树）


联系
我们