//主席树 权值线段树+可持久化 //权值线段树：在此处指各个数字在某个区间内出现的次数 //那么第一棵权值线段树会记录[1,1]的数字出现次数 //第n棵权值线段树会记录[1,n]的数字出现次数 //例：数列为110001//第一棵权值线段树记录为tree1[0]=0 tree1[1]=1//第二棵权值线段树记录为tree2[0]=0 tree2[1]=2//第六棵权值线段树记录为tree6[0]=3 tree6[1]=3//那么要求区间为[3,5]的数字出现次数可拿第五棵权值线段树减去第(三减一)棵权值线段树 //此处运用前缀和思想 //将多棵权值线段树的公共点合为一个点可减少空间复杂度 //求区间第k小即可求出区间数字出现次数后递归操作 #include#include #include #include #include #include using namespace std;int n,m,cnt,b[200001],root[200001];//b[]离散化后的值 root[]根的编号 struct uio{ int num,id;}a[200001];//离散化辅助结构体 struct rty{ int ls,rs,siz;//左儿子，右儿子，区间元素个数 }tree[5000001];//权值线段树 递增使得左儿子表示的值小于右儿子表示的值 bool cmp(uio x,uio y){ return x.num