1 /* 2 主席树:对于序列的每一个前缀建一棵以序列里的值为下标的线段树(所以要先离散化), 3 记录该前缀序列里出现的值的次数; 4 记离散后的标记为1~n; (下面值直接用1~n代替;) 5 对于区间[x,y]的第k大的值,那么从root[x-1],root[y]开始, 6 t=root[y].[1,mid]-root[x-1].[1,mid] ,t表示区间[x,y]内值在[1,mid]的个数 7 先判断t是否大于K,如果t大于k,那么说明在区间[x,y]内存在[1,mid]的数的个数大于k, 8 也就是第k大的值在[1,mid]中,否则在[mid+1,r]中; 9 10 这样我们依次同时从root[x-1],root[y]往下走11 当l==r时 第k大的值就是离散后标记为l的值;12 13 如果每棵线段都建完整的化,n*(n<<2)肯定会mle,14 我们发现对于前缀[1,i]和前缀[1,i+1]的线段树,如果b[i+1]<=mid (b[i+1]表示a[i+1]离散后的标记)15 那么线段树i和线段树i+1的左边是完全相同的,根本不需要在建,只需要用指针指一下就好;16 那么对于一棵新的线段树其实我们最多要建的节点数为log(n);nlog(n)的节点数还是可以忍受的;17 18 19 20 */21 #include22 #include 23 #include 24 #include 25 #include 26 #include 27 #define w(i) T[(i)].w28 #define ls(i) T[(i)].ls29 #define rs(i) T[(i)].rs30 using namespace std;31 const int N=100000+10;32 struct node{33 int ls,rs,w;34 node(){ls=rs=w=0;}35 }T[N*20];36 int a[N],b[N],p[N],root[N],sz;37 int cmp(int i,int j){38 return a[i] >1;46 if (x<=m) ins(ls(i),l,m,x);47 else ins(rs(i),m+1,r,x);48 }49 int query(int i,int j,int l,int r,int k){50 if (l==r) return l;51 int t=w(ls(j))-w(ls(i));52 int m=(l+r)>>1;53 if (t>=k) return query(ls(i),ls(j),l,m,k);54 else return query(rs(i),rs(j),m+1,r,k-t);55 }56 int main(){57 int Cas;scanf("%d",&Cas);58 while (Cas--){59 root[0]=0;60 scanf("%d%d",&n,&m);61 for (int i=1;i<=n;i++){62 scanf("%d",&a[i]);p[i]=i;63 }64 sort(p+1,p+1+n,cmp);//间接排序,p[i]表示第i小的值在a[]中的下标; 65 for (int i=1;i<=n;i++) b[p[i]]=i;//离散化 66 /*67 for (int i=1;i<=n;i++) cout< <<" ";cout<