网页游戏网站排名前10名长沙做网站的公司有哪些
强烈推荐推荐不懂主席树的看一下这篇文章：
http://www.cnblogs.com/zyf0163/p/4749042.html
题目链接：
http://acm.hdu.edu.cn/showproblem.php?pid=5919
题目大意：给你一个区间，假设这个区间中有k个数，每个数的位置升序排列为 p1 p2 p3 ->pk，问p[k/2]是多少
解题思路：
（解题思路如果看不懂可以先看一下HDU 3333）
没注意题目范围 应该是不用离散化的 然后这里离散化了一下
从后向前建n颗树，树的结点维护区间内有多少个不同的值，建树时，每遇到一个新点，判断之前是否出现过，若出现过，在之前的位置减1，给新位置加1。
对于每个询问，先查询出每个区间有多少个不同的值，假设有k个，直接查询区间k/2小就可以了，2/k向上取整。
AC代码：
#include <iostream>
#include <cstring>
#include <cstdio>
#include <cstdlib>
#include <cmath>
#include <string>
#include <vector>
#include <list>
#include <map>
#include <queue>
#include <stack>
#include <algorithm>
#include <set>
#include <functional>
#define RI(N) scanf("%d",&(N))
#define RII(N,M) scanf("%d %d",&(N),&(M))
#define RIII(N,M,K) scanf("%d %d %d",&(N),&(M),&(K))
#define mem(a) memset((a),0,sizeof(a))
using namespace std;
const int inf=1e9;
const int inf1=-1*1e9;
double EPS=1e-10;
typedef long long LL;
const int N =200000+5;
int a[N],b[N],tot,rt[N*40],sum[N*40],ls[N*40],rs[N*40],sz,cas=1,exi[N],n;
int preans;void build(int &o,int l,int r)
{o=++tot;sum[o]=0;if(l==r) return ;int m=(l+r)>>1;build(ls[o],l,m);build(rs[o],m+1,r);
}void update(int &o,int l,int r,int last,int p,int add)
{o=++tot;sum[o]=sum[last]+add;ls[o]=ls[last];rs[o]=rs[last];if(l==r) return ;int m=(l+r)>>1;if(p<=m) update(ls[o],l,m,ls[last],p,add);else update(rs[o],m+1,r,rs[last],p,add);
}int query1(int l,int r,int rtt,int L,int R)
{if(L<=l&&r<=R){// cout<<"l = "<<l<<" r ="<<r<<"sum = "<<sum[rtt]<<endl;return sum[rtt];}int m=(l+r)>>1;int ans=0;if(m>=L) ans+=query1(l,m,ls[rtt],L,R);if(m<R) ans+=query1(m+1,r,rs[rtt],L,R);return ans;}int query(int now,int l,int r,int k)
{int ans=0;if(l==r) return l;int m=(l+r)>>1;int cnt=sum[ls[now]];if(k<=cnt) return query(ls[now],l,m,k);return query(rs[now],m+1,r,k-cnt);
}void solve()
{int l,r;RII(l,r);int ll=min((l+preans)%n+1,(r+preans)%n+1);int rr=max((l+preans)%n+1,(r+preans)%n+1);// cout<<"主节点 = "<<sum[rt[rr]]<<endl;// cout<<"ll = "<<ll<<"rr = "<<rr<<endl;int ans=query1(1,n,rt[ll],ll,rr);// cout<<"ans = "<<ans<<endl;int ans1=ans/2;if(ans%2) ans1++;int x=query(rt[ll],1,n,ans1);printf(" %d",x);preans=x;
}int main()
{int T;scanf("%d",&T);while(T--){int q;RII(n,q);for(int i=1; i<=n; i++) RI(a[i]),b[i]=a[i];sort(b+1,b+n+1);sz=unique(b+1,b+n+1)-(b+1);tot=0;build(rt[n+1],1,n);for(int i=1; i<=n; i++) a[i]=lower_bound(b+1,b+sz+1,a[i])-b;memset(exi,0,sizeof(exi));for(int i=n; i>=1; i--){if(exi[a[i]]){update(rt[i],1,n,rt[i+1],exi[a[i]],-1);update(rt[i],1,n,rt[i],i,1);}else{update(rt[i],1,n,rt[i+1],i,1);}exi[a[i]]=i;}printf("Case #%d:",cas++);preans=0;while(q--) solve();printf("\n");}return 0;
}