题目链接：
分析和思路：
可能最先想到的就是把l,r区间的数拿出来排序后得到答案，但多次频繁操作时间复杂度太高，这时候强大的数据结构主席树就发挥出它强大的作用，这就是主席树模板题目，套模板。
主席树本质就是线段树（又称可持久化线段树），可以将历史版本保留下来。对于区间[l, r]的第K大询问，如果我们能够得到一个插入原序列中[1, l - 1]元素的线段树，和一颗插入了[1, r]元素的线段树，由于线段树是开在值域上，区间长度是一定的，所以结构也必然是完全相同的，我们可以直接对这两颗线段树进行相减，得到的是相当于插入了区间[l ,r]元素的线段树。注意这里利用到的区间相减性质，实际上是用两颗不同历史版本的线段树进行相减：一颗是插入到第l-1个元素的旧树，一颗是插入到第r元素的新树。这样相减之后得到的是相当于只插入了原序列中[l, r]元素的一颗记录了区间数字个数的线段树。
插入时，我们显然不能每次插入一个元素，就从头建立一颗全新的线段树，否则内存开销无法承受。事实上，每次插入一个新的元素时，我们不需要新建所有的节点，而是只新建增加的节点。也就是从根节点出发，先新建节点并复制原节点的值，然后进行修改即可。
我的天呐，看了这么长时间总算懂得一点点主席树了，拿小本本记下来。。
1 #include2 #include 3 #include 4 #include 5 using namespace std; 6 const int maxn=1e5+5; 7 int a[maxn],sorted[maxn],root[maxn];//root每棵树根存结点 8 int cnt; 9 struct node10 {11 int sum,lson,rson;//重要:ls,rs代表左右儿子结点编号!(泪奔线段树l,r代表本结点管辖范围!!)12 }Tree[maxn<<5];13 14 int createnode(int su,int ls,int rs)//创建新树(先等于原树)15 {16 int idx=++cnt;17 Tree[idx].sum=su;18 Tree[idx].lson=ls;19 Tree[idx].rson=rs;20 return idx;21 }22 void update(int l,int r,int &root,int pre_rt,int pos)//&编号,void&x(原空间)代替了return x返回型更方便更新修改 23 {24 root=createnode(Tree[pre_rt].sum+1,Tree[pre_rt].lson,Tree[pre_rt].rson);//从根节点往下更新到叶子,新建立出一路更新的节点,这样就是一颗新树了25 if (l==r) return;26 27 int mid=(l+r)>>1;28 if (pos<=mid) update(l,mid,Tree[root].lson,Tree[pre_rt].lson,pos);29 else update(mid+1,r,Tree[root].rson,Tree[pre_rt].rson, pos);30 }31 32 int query(int l,int r,int S,int E,int k)33 {34 if (l==r) return l;//说明最终返回的是答案离散后的结果即编号(排第几) 35 36 int mid=(l+r)>>1;37 int sum=Tree[Tree[E].lson].sum-Tree[Tree[S].lson].sum;//两左二子数目相减得到该节点真正个数判断 38 if (k<=sum) return query(l,mid,Tree[S].lson,Tree[E].lson,k);39 else return query(mid+1,r,Tree[S].rson,Tree[E].rson,k-sum);40 }41 int main()42 {43 int n,m,num,pos,T;44 scanf("%d %d",&n,&m);45 cnt=0; root[0]=0;46 for(int i=1;i<=n;i++)47 {48 scanf("%d",&a[i]);49 sorted[i]=a[i];50 }51 52 sort(sorted+1,sorted+1+n);53 num=unique(sorted+1,sorted+n+1)-(sorted+1);//num去杂之后的最终范围54 for(int i=1;i<=n;i++)55 { //实际上是对每个元素建立了一颗线段树,保存其根节点56 pos=lower_bound(sorted+1,sorted+num+1,a[i])-sorted;//得到编号即离散化后的映射57 update(1,num,root[i],root[i-1],pos);58 }59 60 while(m--)61 {62 int x,y,k;63 scanf("%d%d%d",&x,&y,&k);64 x++; y++; 65 int kk=y-x+1;//数学转换小变大(或者查询时直接右递归)66 kk=kk-(k-1); 67 //if(Tree[root[y]].sum-Tree[root[x-1]].sum
牛客小白月赛9E：https://ac.nowcoder.com/acm/contest/275/E
查询区间内<=x的数量
思路：本质还是查询第k小(大),用了lower_bound转换而已
1 #include2 #include 3 #include 4 #include 5 using namespace std; 6 const int maxn=1e5+5; 7 int a[maxn],sorted[maxn],root[maxn];//root每棵树根存结点 8 int cnt; 9 struct node10 {11 int sum,lson,rson;//重要:ls,rs代表左右儿子结点编号!(泪奔线段树l,r代表本结点管辖范围!!)12 }Tree[maxn<<5];13 14 int createnode(int su,int ls,int rs)//创建新树(先等于原树)15 {16 int idx=++cnt;17 Tree[idx].sum=su;18 Tree[idx].lson=ls;19 Tree[idx].rson=rs;20 return idx;21 }22 void update(int l,int r,int &root,int pre_rt,int pos)//&编号,void&x(原空间)代替了return x返回型更方便更新修改23 {24 root=createnode(Tree[pre_rt].sum+1,Tree[pre_rt].lson,Tree[pre_rt].rson);//从根节点往下更新到叶子,新建立出一路更新的节点,这样就是一颗新树了25 if (l==r) return;26 27 int mid=(l+r)>>1;28 if (pos<=mid) update(l,mid,Tree[root].lson,Tree[pre_rt].lson,pos);29 else update(mid+1,r,Tree[root].rson,Tree[pre_rt].rson, pos);30 }31 32 int query(int l,int r,int S,int E,int k)33 {34 if (1<=l && r<=k) return Tree[E].sum-Tree[S].sum;//说明最终返回的是答案离散后的结果即编号(排第几)35 36 int mid=(l+r)>>1;37 //int sum=Tree[Tree[E].lson].sum-Tree[Tree[S].lson].sum;//两左二子数目相减得到该节点真正个数判断38 int ans=0;39 ans+=query(l,mid,Tree[S].lson,Tree[E].lson,k);40 if(k>=mid+1) ans+=query(mid+1,r,Tree[S].rson,Tree[E].rson,k);41 42 return ans;43 }44 45 int main()46 {47 int n,m,num,pos,T;48 scanf("%d %d",&n,&m);49 cnt=0; root[0]=0;50 for(int i=1;i<=n;i++)51 {52 scanf("%d",&a[i]);53 sorted[i]=a[i];54 }55 56 sort(sorted+1,sorted+1+n);57 num=unique(sorted+1,sorted+n+1)-(sorted+1);//num去杂之后的最终范围58 for(int i=1;i<=n;i++)59 { //实际上是对每个元素建立了一颗线段树,保存其根节点60 pos=lower_bound(sorted+1,sorted+num+1,a[i])-sorted;//得到编号即离散化后的映射61 update(1,num,root[i],root[i-1],pos);62 }63 64 while(m--)65 {66 int x,y,k;67 scanf("%d%d%d",&x,&y,&k);68 69 int t=lower_bound(sorted+1,sorted+1+num,k)-(sorted+1)+1;//lower_bound查询排第几常用优化技巧操作70 //if(Tree[root[y]].sum-Tree[root[x-1]].sum
查询区间不同数的个数(做法很多，可树状数组，莫队，主席树)
sum存的不是第几大了，而是区间每个不同数的最右边的位置
1 #include2 #include 3 #include 4 #include 5 using namespace std; 6 const int maxn=1e5+5; 7 int a[maxn],sorted[maxn],root[maxn]; 8 int vis[maxn*10]; 9 int cnt;10 struct node11 {12 int sum,lson,rson;13 }Tree[maxn<<5];14 15 int createnode(int su,int ls,int rs)16 {17 int idx=++cnt;18 Tree[idx].sum=su;19 Tree[idx].lson=ls;20 Tree[idx].rson=rs;21 return idx;22 }23 void update(int l,int r,int &root,int pre_rt,int pos,int val)24 {25 root=createnode(Tree[pre_rt].sum+val,Tree[pre_rt].lson,Tree[pre_rt].rson);26 if (l==r) return;27 28 int mid=(l+r)>>1;29 if (pos<=mid) update(l,mid,Tree[root].lson,Tree[pre_rt].lson,pos,val);30 else update(mid+1,r,Tree[root].rson,Tree[pre_rt].rson,pos,val);31 }32 33 int query(int l,int r,int posl,int posr,int E)34 {35 if (posl<=l && r<=posr) return Tree[E].sum;36 37 int mid=(l+r)>>1;38 39 int ans=0;40 if(mid>=posl) ans+=query(l,mid,posl,posr,Tree[E].lson);41 if(mid
完