首先，不会主席树的同学请http://blog.csdn.net/metalseed/article/details/8045038 顺便再做做BZOJ3110
网传的整体二分算法本蒟蒻表示真看不懂，于是乱××了一个可怕的二维主席树，其中的一维是继承上一层处理的，另一维用树状数组，内存达到了可怕的O(N^2log^2N)，时间是O((N^2+Q)*log^2N)，都是贴着线过的，估计重新交一遍就TLE了吧
#include <cstdio>
#include <algorithm>
#define numnod 22030000
int root[501][501],ls[numnod],rs[numnod],cnt[numnod],a[501][501],A[250001],H=0,N,Q,n,ir[6666],dr[6666],Ni,Nd;
void add(int x,int y,int w)
{
int lp=root[x][y],p=++n,l=1,r=H,new_root=p;
cnt[p]=cnt[lp]+1;
while (l<r)
{
int m=l+r>>1;
if (w<=m)
ls[p]=++n,rs[p]=rs[lp],p=ls[p],lp=ls[lp],r=m;
else
rs[p]=++n,ls[p]=ls[lp],p=rs[p],lp=rs[lp],l=m+1;
cnt[p]=cnt[lp]+1;
}
root[x][y]=new_root;
}
void init()
{
scanf("%d%d",&N,&Q);
for (int i=1;i<=N;i++)
for (int j=1;j<=N;j++)
scanf("%d",&a[i][j]),A[++H]=a[i][j];
std::sort(A+1,A+H+1);
H=std::unique(A+1,A+H+1)-A-1;
for (int i=1;i<=N;i++)
for (int j=1;j<=N;j++)
a[i][j]=std::lower_bound(A+1,A+H+1,a[i][j])-A;
for (int j=1;j<=N;j++)
for (int i=1;i<=N;i++)
{
root[i][j]=root[i-1][j];
for (int k=(j&(j-1))+1;k<=j;k++)
add(i,j,a[i][k]);
}
}
int main()
{
init();
while (Q--)
{
int x1,y1,x2,y2,k,l=1,r=H;
scanf("%d%d%d%d%d",&x1,&y1,&x2,&y2,&k);
Ni=Nd=0;
for (int i=y2;i;i&=i-1)
ir[++Ni]=root[x2][i],dr[++Nd]=root[x1-1][i];
for (int i=y1-1;i;i&=i-1)
dr[++Nd]=root[x2][i],ir[++Ni]=root[x1-1][i];
while (l<r)
{
int cL=0,m=l+r>>1;
for (int i=Ni;i;i--)
cL+=cnt[ls[ir[i]]];
for (int i=Nd;i;i--)
cL-=cnt[ls[dr[i]]];
if (k<=cL)
{
for (int i=Ni;i;i--)
ir[i]=ls[ir[i]];
for (int i=Nd;i;i--)
dr[i]=ls[dr[i]];
r=m;
}
else
{
for (int i=Ni;i;i--)
ir[i]=rs[ir[i]];
for (int i=Nd;i;i--)
dr[i]=rs[dr[i]];
k-=cL,l=m+1;
}
}
printf("%d\n",A[l]);
}
return 0;
}
具体就看代码吧 没什么好讲的 注意一(ju)点(duo)细节就行了
