题目链接：bzoj2738
题目大意：给你一个N*N的矩阵，不用算矩阵乘法，但是每次询问一个子矩形的第K小数。
【= =题目在逗我吧
题解：
整体二分
不过是不带修改的区间第k小的升级版。
改用二维树状数组维护就好了。
可能是我常数太大代码太丑?狂TLE，最后加了个读优卡过了。。。
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<iostream>
#include<algorithm>
using namespace std;
#define maxn 351000
#define N 600
#define inf 1e9
struct node
{
int x1,x2,y1,y2,c,tg,ans;
}q[maxn];
int n,m,id[maxn],c[N][N];
int tol[maxn],tor[maxn];
inline int read()
{
int x=0,f=1;char ch=getchar();
while(ch<'0'||ch>'9') {if(ch=='-')f=-1;ch=getchar();}
while(ch>='0'&&ch<='9') {x=x*10+ch-'0';ch=getchar();}
return x*f;
}
int lowbit(int x){return x&(-x);}
void change(int x,int y,int k)
{
for (int i=x;i<=n;i+=lowbit(i))
for (int j=y;j<=n;j+=lowbit(j))
c[i][j]+=k;
}
int query(int x,int y)
{
int ret=0;
for (int i=x;i>0;i-=lowbit(i))
for (int j=y;j>0;j-=lowbit(j))
ret+=c[i][j];
return ret;
}
void solve(int head,int tail,int l,int r)
{
if (head>tail) return;
int lnum=0,rnum=0,i,mid=(l+r)>>1;
if (l==r)
{
for (i=head;i<=tail;i++)
if (q[id[i]].tg==2) q[id[i]].ans=l;
return;
}
for (i=head;i<=tail;i++)
if (q[id[i]].tg==1)
{
if (q[id[i]].c<=mid) tol[++lnum]=id[i],change(q[id[i]].x1,q[id[i]].y1,1);
else tor[++rnum]=id[i];
}else
{
int now=query(q[id[i]].x2,q[id[i]].y2)-query(q[id[i]].x2,q[id[i]].y1-1)-query(q[id[i]].x1-1,q[id[i]].y2)+query(q[id[i]].x1-1,q[id[i]].y1-1);
if (now>=q[id[i]].c) tol[++lnum]=id[i];
else q[id[i]].c-=now,tor[++rnum]=id[i];
}
for (i=head;i<=tail;i++)
if (q[id[i]].tg==1 && q[id[i]].c<=mid) change(q[id[i]].x1,q[id[i]].y1,-1);
for (i=0;i<lnum;i++) id[head+i]=tol[i+1];
for (i=0;i<rnum;i++) id[head+i+lnum]=tor[i+1];
solve(head,head+lnum-1,l,mid);
solve(head+lnum,tail,mid+1,r);
}
int main()
{
//freopen("a.in","r",stdin);
//freopen("a.out","w",stdout);
int i,j,x,t=0;
// scanf("%d%d",&n,&m);
n=read();m=read();
for (i=1;i<=n;i++)
for (j=1;j<=n;j++)
{
id[++t]=t;x=read();
// scanf("%d",&x);
q[t].x1=i;q[t].y1=j;
q[t].c=x;q[t].tg=1;
}
for (i=1;i<=m;i++)
{
id[++t]=t;
q[t].x1=read();q[t].y1=read();
q[t].x2=read();q[t].y2=read();
// scanf("%d%d%d%d",&q[t].x1,&q[t].y1,&q[t].x2,&q[t].y2);
q[t].c=read();// scanf("%d",&q[t].c);
q[t].tg=2;q[t].ans=-1;
}
solve(1,t,0,inf);
for (i=1;i<=t;i++) if (q[i].tg==2) printf("%d
",q[i].ans);
return 0;
}