SPOJ DQUERY:D-query

时间：2023-03-09 09:32:51
SPOJ DQUERY:D-query

主席树/树状数组。给一个区间，多次询问[l,r]内有多少个不重复的元素。每个前缀都建线段树，询问直接r的[l,r]就可以了。（似乎对主席树有一点了解了？。。。话说spoj好高级的样子。。。

#include<cstdio>

#include<cstring>

#include<iostream>

#include<algorithm>

using namespace std;

#define REP(i,s,t) for(int i=s;i<=t;i++)

#define dwn(i,s,t) for(int i=s;i>=t;i--)

#define clr(x,c) memset(x,c,sizeof(x))

int read(){

	int x=0;char c=getchar();

	while(!isdigit(c)) c=getchar();

	while(isdigit(c)) x=x*10+c-'0',c=getchar();

	return x;

}

const int nmax=30005;

const int inf=0x7f7f7f7f;

struct node{

	node *l,*r;int sum;

};

node nodes[nmax*25],*pt=nodes,*root[nmax];

int a[nmax],b[nmax],vis[nmax*40];

node* build(int l,int r){

	node* op=pt++;op->sum=0;

	if(l==r) return op;

	int mid=(l+r)>>1;

	op->l=build(l,mid);op->r=build(mid+1,r);

	return op;

}

node* update(int p,int add,node* t,int l,int r){

	node* op=pt++;op->sum=t->sum+add;

	if(l==r) return op;

	int mid=(l+r)>>1;

	if(p<=mid) op->r=t->r,op->l=update(p,add,t->l,l,mid);

	else op->l=t->l,op->r=update(p,add,t->r,mid+1,r);

	return op;

}

int query(int tl,int tr,int l,int r,node* t){

	if(tl<=l&&tr>=r) return t->sum;

	int ans=0,mid=(l+r)>>1;

	if(tl<=mid) ans+=query(tl,tr,l,mid,t->l);

	if(tr>mid) ans+=query(tl,tr,mid+1,r,t->r);

	return ans;

}

int main(){

	int n,m;

	while(scanf("%d",&n)!=EOF){

		pt=nodes;clr(vis,0);

		REP(i,1,n) a[i]=read();

		root[0]=build(1,n);

		REP(i,1,n){

			node* t=update(i,1,root[i-1],1,n);

			if(vis[a[i]]) root[i]=update(vis[a[i]],-1,t,1,n);

			else root[i]=t;

			vis[a[i]]=i;

		}

		m=read();

		REP(i,1,m){

			int s=read(),t=read();

			printf("%d\n",query(s,t,1,n,root[t]));

		}

	}

	return 0;

}

　　

Time Limit: 227MS   Memory Limit: 1572864KB   64bit IO Format: %lld & %llu

Submit Status

Description

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

Hint

Added by: Duc
Date: 2008-10-26
Time limit: 0.227s
Source limit: 50000B
Memory limit: 1536MB
Cluster: Cube (Intel G860)
Languages: All except: ERL JS NODEJS PERL 6 VB.net
Resource: © VNOI

相关文章