HDU 5919 Sequence II（可持久化线段树）
【题目链接】 http://acm.hdu.edu.cn/showproblem.php?pid=5919
【题目大意】
给出一个数列，每次查询数列中，区间非重元素的下标的中位数。查询操作强制在线。
【题解】
因为查询的是下标，因此，我们直接在下标操作表示这里有没有数字，然后查询k大数即可，非重元素即需要在区间每个数第一次出现的地方+1，然后对处理完的区间进行查询即可，考虑到查询强制在线，不能扫描线，因此只能建立可持久化线段树，线段树的第i个版本表示第i个位置往后的每个元素第一次出现的位置，那么查询区间【L，R】，就是查询第L个版本的线段树第k大数，然后对于k的计算，我们只要在第L个版本的线段树上查询区间【L，R】中的非重元素个数，即线段树求和，之后除2上取整即可。
【代码】
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 | #include <cstdio>#include <cstring>#include <algorithm>using namespace std;const int N=200010;int n,m,i,x,y,z,ans;int l[N*40],r[N*40],v[N*40],tot,root[N],a[N],pre[N];void read(int&a){ char ch;while(!((ch=getchar())>='0')&&(ch<='9')); a=ch-'0';while(((ch=getchar())>='0')&&(ch<='9'))a*=10,a+=ch-'0';}int build(int a,int b){ int x=++tot; v[x]=0; if(a==b)return x; int mid=(a+b)>>1; return l[x]=build(a,mid),r[x]=build(mid+1,b),x;}int change(int x,int a,int b,int c,int p){ int y=++tot;v[y]=v[x]+p; if(a==b)return y; int mid=(a+b)>>1; if(c<=mid)l[y]=change(l[x],a,mid,c,p),r[y]=r[x]; else l[y]=l[x],r[y]=change(r[x],mid+1,b,c,p); return y;}int query(int x,int a,int b,int L,int R){ if(L<=a&&b<=R)return v[x]; int mid=(a+b)/2,res=0; if(L<=mid)res+=query(l[x],a,mid,L,R); if(R>mid)res+=query(r[x],mid+1,b,L,R); return res; }int getans(int x,int a,int b,int k){ if(a==b)return a; int mid=(a+b)>>1; if(v[l[x]]>=k)return getans(l[x],a,mid,k); else return getans(r[x],mid+1,b,k-v[l[x]]);}int T,Cas=0;int main(){ scanf("%d",&T); while(T--){ scanf("%d%d",&n,&m);tot=0; memset(pre,-1,sizeof(pre)); for(int i=1;i<=n;i++)read(a[i]); root[n+1]=build(1,n); for(int i=n;i;i--){ if(pre[a[i]]==-1)root[i]=change(root[i+1],1,n,i,1); else{ int tmp=change(root[i+1],1,n,pre[a[i]],-1); root[i]=change(tmp,1,n,i,1); }pre[a[i]]=i; }printf("Case #%d:",++Cas); int ans=0; while(m--){ read(x);read(y); int xx=(x+ans)%n+1,yy=(y+ans)%n+1; x=min(xx,yy);y=max(xx,yy); int u=query(root[x],1,n,x,y); u=(u+1)/2; ans=getans(root[x],1,n,u); printf(" %d",ans); }puts(""); }return 0;} |
评论 (0)
