关于一个很强的操作，整体二分
最基本的运用就是洛谷的主席树模板——静态区间的k大
下面说一说思路
所谓整体，就是所有的询问全部一起处理，这是因为如果单个单个二分的话无疑会超时。那么如何可以做到这点呢？首先对于数组中原来的数和询问，把它们封装在同样的结构体里。这个结构体包括x,y,k,id,type
对于数组中原来的数，通过观察程序可以发现y,k是没有任何作用的。x代表的是这个位置的数的大小，id表示数的位置，type是它的类型（不是询问）
对于询问，x，y，k表示在区间x~y中查询第k小的数，id表示的是询问的编号，type是它的类型（询问）
那么接下来我们要对这些封装好的什么什么东西一起二分，这些东西我们存在一个数组里，在接下来的描述中我们管它叫队列
在solve函数中，ql,ql分别表示当前处理的队列的子列的左端点和右端点。l，r就是我们二分的权值。首先判断，若是ql>qr就直接return。之后判断l是不是与r相等，若是相等说明找到了，此时对于目前处理的队列中所有询问而言结果都是l（或r）。
如果以上都没有满足，那么我们还需要继续二分下去。mid=(l+r)>>1，那么考虑算出当前维护的队列中所有type==1的类型的x值小于等于mid的划分到左边，同时统计个数。而如果大于mid就划分到右边。怎么统计个数呢？我们每次递归是使用树状数组，而每次结束时又把它给清空，（如果这里可以离散化的话好像会很完美，但可不可以我没有去想。。。因为这道题确实只是入门题。当然主要是因为我是蒟蒻的缘故）。对于type==2的元素而言，直接树状数组统计x，y之间的比mid小的数的个数，然后和k比个大小，同样把它划分成左右两边
相信没学过的人有疑问了，为什么我们要划分成左右两边呢？首先我们每次递归处理的是一个子问题，划分是处理子问题的一个大前提。其次，我们得知划分到右边的无论如何不会影响左边的处理，可以理解为对左边不存在贡献。
递归的最后我们只需要修改队列分出左右就好了
值得再次提醒的是，l，r，mid是我们二分的数值，请不要和ql，qr的含义弄混
下面附上代码
#include<bits/stdc++.h> using namespace std; const int oo=1e9+7; const int maxn=2e5+15; int n,m,cnt; int ans[maxn],tree[maxn]; struct NODE { int x;int y;int k; int id;int type; }q[maxn<<1],q1[maxn<<1],q2[maxn<<1]; void add(int x,int y) { while (x<=n) { tree[x]+=y; x+=x&(-x); } } int sum(int x) { int ans=0; while (x) { ans+=tree[x]; x-=x&(-x); } return ans; } void solve(int ql,int qr,int l,int r) { if (ql>qr) return; if (l==r){ for (int i=ql;i<=qr;i++) if (q[i].type==2) ans[q[i].id]=l; return; } int mid=(l+r)>>1; int p1=0,p2=0; for (int i=ql;i<=qr;i++) if (q[i].type==1){ if (q[i].x<=mid){ add(q[i].id,1); q1[++p1]=q[i]; } else q2[++p2]=q[i]; } else { int res=sum(q[i].y)-sum(q[i].x-1); if (res>=q[i].k) q1[++p1]=q[i]; else { q[i].k-=res; q2[++p2]=q[i]; } } for (int i=1;i<=p1;i++) if (q1[i].type==1) add(q1[i].id,-1); for (int i=1;i<=p1;i++) q[i+ql-1]=q1[i]; for (int i=1;i<=p2;i++) q[i+ql+p1-1]=q2[i]; solve(ql,ql+p1-1,l,mid); solve(ql+p1,qr,mid+1,r); } int main() { scanf("%d%d",&n,&m); for (int i=1;i<=n;i++) { int x; scanf("%d",&x); q[++cnt]=(NODE){x,1,oo,i,1}; } for (int i=1;i<=m;i++) { int x,y,k; scanf("%d%d%d",&x,&y,&k); q[++cnt]=(NODE){x,y,k,i,2}; } solve(1,cnt,-oo,oo); for (int i=1;i<=m;i++) printf("%d ",ans[i]); return 0; }
#include<bits/stdc++.h> using namespace std; const int oo=1e9+7; const int maxn=2e5+15; int n,m,cnt; int ans[maxn],tree[maxn]; struct NODE { int x;int y;int k; int id;int type; }q[maxn<<1],q1[maxn<<1],q2[maxn<<1]; void add(int x,int y) { while (x<=n) { tree[x]+=y; x+=x&(-x); } } int sum(int x) { int ans=0; while (x) { ans+=tree[x]; x-=x&(-x); } return ans; } void solve(int ql,int qr,int l,int r) { if (ql>qr) return; if (l==r){ for (int i=ql;i<=qr;i++) if (q[i].type==2) ans[q[i].id]=l; return; } int mid=(l+r)>>1; int p1=0,p2=0; for (int i=ql;i<=qr;i++) if (q[i].type==1){ if (q[i].x<=mid){ add(q[i].id,1); q1[++p1]=q[i]; } else q2[++p2]=q[i]; } for (int i=ql;i<=qr;i++) if (q[i].type==2){ int res=sum(q[i].y)-sum(q[i].x-1); if (res>=q[i].k) q1[++p1]=q[i]; else { q[i].k-=res; q2[++p2]=q[i]; } } for (int i=1;i<=p1;i++) if (q1[i].type==1) add(q1[i].id,-1); for (int i=1;i<=p1;i++) q[i+ql-1]=q1[i]; for (int i=1;i<=p2;i++) q[i+ql+p1-1]=q2[i]; solve(ql,ql+p1-1,l,mid); solve(ql+p1,qr,mid+1,r); } int main() { scanf("%d%d",&n,&m); for (int i=1;i<=n;i++) { int x; scanf("%d",&x); q[++cnt]=(NODE){x,1,oo,i,1}; } for (int i=1;i<=m;i++) { int x,y,k; scanf("%d%d%d",&x,&y,&k); q[++cnt]=(NODE){x,y,k,i,2}; } solve(1,cnt,-oo,oo); for (int i=1;i<=m;i++) printf("%d ",ans[i]); return 0; }
我自己是代码2，一直不理解代码1为什么也可以，求大佬教我（当然两份都能A题）