首页 > 代码库 > SPOJ 3267. D-query (主席树or树状数组离线)
SPOJ 3267. D-query (主席树or树状数组离线)
A - D-query
Time Limit:1500MS Memory Limit:0KB 64bit IO Format:%lld & %lluAppoint description:
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
主席树版:
/************************************************************************* > File Name: cf.cpp > Author: acvcla > QQ: > Mail: acvcla@gmail.com > Created Time: 1949Äê10ÔÂ1ÈÕ ÐÇÆÚÒ» 0ʱ0·Ö0Ãë ************************************************************************/ #include<iostream> #include<algorithm> #include<cstdio> #include<vector> #include<cstring> #include<map> #include<queue> #include<stack> #include<string> #include<cstdlib> #include<ctime> #include<set> #include<math.h> using namespace std; typedef long long LL; const int maxn = 3e4 + 10; #define rep(i,a,b) for(int i=(a);i<=(b);i++) #define pb push_back int tot,n,m,date[maxn],root[maxn]; struct chairTnode { int s,rc,lc; chairTnode(int s=0,int lc=0,int rc=0):s(s),lc(lc),rc(rc){} }; chairTnode chairT[maxn*20]; int newnode(int sum,int lson,int rson) { int rt=++tot; chairT[rt]=chairTnode(sum,lson,rson); return rt; } void Insert(int &rt,int pre_rt,int pos,int L,int R,int val) { chairTnode &t=chairT[pre_rt]; rt=newnode(t.s+val,t.lc,t.rc); if(L==R)return; int mid=(L+R)>>1; if(pos<=mid)Insert(chairT[rt].lc,t.lc,pos,L,mid,val); else Insert(chairT[rt].rc,t.rc,pos,mid+1,R,val); } int Query(int rt,int L,int R,int pos)//Query sum of [pos,R] { if(L==pos)return chairT[rt].s; int mid=(L+R)>>1; if(pos<=mid)return Query(chairT[rt].lc,L,mid,pos)+chairT[chairT[rt].rc].s; return Query(chairT[rt].rc,mid+1,R,pos); } int main() { while(~scanf("%d",&n)) { rep(i,1,n){ scanf("%d",date+i); } tot=root[0]=0; map<int,int>q; int t; for(int i=1;i<=n;i++){ if(!q[date[i]]){ Insert(root[i],root[i-1],i,1,n,1);//在位置i的数目加1 }else{ Insert(t,root[i-1],q[date[i]],1,n,-1);//之前已经出现过,减去前面加的那次 Insert(root[i],t,i,1,n,1);//加到现在这次来 } q[date[i]]=i; } int ql,qr; scanf("%d",&m); while(m--) { scanf("%d%d",&ql,&qr); printf("%d\n",Query(root[qr],1,n,ql)); } } return 0; }
树状数组版:
#include<iostream> #include<cstdio> #include<cstring> #include<cstdlib> #include<algorithm> #include<map> const int maxn1=3e4+5; const int maxn2=2e5+5; typedef long long LL; using namespace std; int l[maxn2],r[maxn2],loc[maxn1],A[maxn1],id[maxn2],n; int C[maxn1],ans[maxn2]; inline int lowbit(int x){return x&-x;} void update(int x,int d) { while(x<=n) { C[x]+=d; x+=lowbit(x); } } int Query(int x) { int sum=0; while(x>0) { sum+=C[x]; x-=lowbit(x); } return sum; } bool cmp(int i,int j) { return r[i]<r[j]; } int main() { while(~scanf("%d",&n)) { memset(loc,0,sizeof(loc)); memset(C,0,sizeof(C)); map<int,int>q; q.clear(); for(int i=1;i<=n;i++) { scanf("%d",A+i); update(i,1); if(!q[A[i]]) { q[A[i]]=i; } } int m; scanf("%d",&m); for(int i=1;i<=m;i++) { scanf("%d%d",l+i,r+i); id[i]=i; } sort(id+1,id+1+m,cmp); /*主要思想是将计数尽可能拖到后面来*/ int Right=1; for (int i = 1; i <= m; ++i) { int x=id[i]; while(Right<=r[x]) { if(q[A[Right]]!=Right){ update(q[A[Right]],-1);/*在后面出现了,让前面的计数抵消,在后面计数,保证查询区间里的数不遗漏*/ q[A[Right]]=Right; } ++Right; } Right=r[x]; ans[x]=Query(r[x])-Query(l[x]-1); } for(int i=1;i<=m;i++)printf("%d\n",ans[i]); } return 0; }
SPOJ 3267. D-query (主席树or树状数组离线)
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。