[文章目录]
Description
给你一个N*N的矩阵，不用算矩阵乘法，但是每次询问一个子矩形的第K小数。n<=500 q<=60000
重新看遍题，好像可以线段树套权值主席树做：对于行维护外层线段树，外层线段树上对应的行再对于列维护权值线段树，不同的列间通过主席树的方式递推下去。每次查询矩形区域，我们找到行对应的log段线段，之后在每个主席树上差分列，二分权值即可。时间复杂度，空间
然而这道题是整体二分的模板题。。。
离线询问对于询问和权值范围同时分治，每次查询左区间的权值在所有询问矩形中出现的个数，和K比较递归将询问分治。
n很小，二维树状数组差分维护矩形内出现点的个数即可(懒得扫描线)。
时间复杂度空间
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
#define N 510
int n,m;
struct node
{
int x,y,w;
}a[N*N];
bool cmp(node x,node y){return x.w<y.w;}
struct ques
{
int x1,x2,y1,y2,k;
}q[61000];
int cg[61000],t[61000],ans[61000];
int f[N][N];
void fix(int x,int y,int w)
{
int i;
while(x<=n)
{
for(i=y;i<=n;i+=-i&i) f[x][i]+=w;
x+=-x&x;
}
}
int query(int x,int y)
{
int re=0,i;
while(x>0)
{
for(i=y;i>0;i-=-i&i) re+=f[x][i];
x-=-x&x;
}
return re;
}
void solve(int l,int r,int L,int R)
{
if(l==r)
{
for(int i=L;i<=R;++i) ans[cg[i]]=a[l].w;
return ;
}
int mid=(l+r)>>1,tmp,i1=L,i2=R;
for(int i=l;i<=mid;++i) fix(a[i].x,a[i].y,1);
for(int i=L;i<=R;++i)
{
tmp=query(q[cg[i]].x2,q[cg[i]].y2)-query(q[cg[i]].x1-1,q[cg[i]].y2)
-query(q[cg[i]].x2,q[cg[i]].y1-1)+query(q[cg[i]].x1-1,q[cg[i]].y1-1);
if(q[cg[i]].k<=tmp) t[i1++]=cg[i];
else t[i2--]=cg[i],q[cg[i]].k-=tmp;
}
for(int i=L;i<=R;++i) cg[i]=t[i];
for(int i=l;i<=mid;++i) fix(a[i].x,a[i].y,-1);
if(i2>=L) solve(l,mid,L,i2);
if(i1<=R) solve(mid+1,r,i1,R);
}
int main()
{
scanf("%d%d",&n,&m);
int t=0;
for(int i=1;i<=n;++i)
for(int j=1;j<=n;++j)
{
++t;
scanf("%d",&a[t].w);
a[t].x=i; a[t].y=j;
}
sort(a+1,a+t+1,cmp);
for(int i=1;i<=m;++i) scanf("%d%d%d%d%d",&q[i].x1,&q[i].y1,&q[i].x2,&q[i].y2,&q[i].k),cg[i]=i;
solve(1,t,1,m);
for(int i=1;i<=m;++i) printf("%d\n",ans[i]);
return 0;
}