[国家集训队]矩阵乘法

洛咕

题意:给定一个\(N*N\)的矩阵，每次询问一个子矩形内的第\(K\)小数.\(n<=500,Q<=500000.\)

分析:看到询问第\(K\)小就想到了整体二分.然后在二维平面上,用二维树状数组即可.所以就还是熟悉的模板题了.

本题有点小卡常,我连\(register\)都用上了,然后把\(else\)全都换成了\(if\),然后能不写函数就不写函数.(\(PS:\)其实这题不卡常的,是我刚开始写法丑陋,树状数组写了个\(lowbit\)函数,每个大的点将近慢了\(0.4s\).)

#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cstring>
#include<cmath>
#include<queue>
#include<map>
#include<set>
#define ll long long
#define rg register
using namespace std;
inline int read(){
    rg int x=0,o=1;char ch=getchar();
    while(ch!='-'&&(ch<'0'||ch>'9'))ch=getchar();
    if(ch=='-')o=-1,ch=getchar();
    while(ch>='0'&&ch<='9')x=x*10+ch-'0',ch=getchar();
    return x*o;
}
const int N=400005;
int n,Q,tot,ans[N],c[505][505];
struct query{int opt,x1,y1,x2,y2,z;}q[N],ql[N],qr[N];
inline void add(int x,int y,int z){
    for(rg int i=x;i<=n;i+=i&-i)
        for(rg int j=y;j<=n;j+=j&-j)c[i][j]+=z;
}
inline int ask(int x,int y){
    rg int cnt=0;
    for(rg int i=x;i;i-=i&-i)
        for(rg int j=y;j;j-=j&-j)cnt+=c[i][j];
    return cnt;
}
inline void solve(int l,int r,int st,int ed){
    if(st>ed)return;
    if(l==r){
        for(rg int i=st;i<=ed;++i)if(q[i].opt)ans[q[i].opt]=l;
        return;
    }
    rg int mid=(l+r)>>1,lt=0,rt=0;
    for(rg int i=st;i<=ed;++i){
        if(!q[i].opt){
            if(q[i].z<=mid)add(q[i].x1,q[i].y1,1),ql[++lt]=q[i];
            if(q[i].z>mid)qr[++rt]=q[i];
        }
        if(q[i].opt){
            rg int sum=ask(q[i].x2,q[i].y2)-ask(q[i].x1-1,q[i].y2)-ask(q[i].x2,q[i].y1-1)+ask(q[i].x1-1,q[i].y1-1);
//这里本来担心树状数组下标为0会卡死,写了好多个if特判,然后发现不特判也没事???
            if(sum>=q[i].z)ql[++lt]=q[i];
            if(sum<q[i].z)q[i].z-=sum,qr[++rt]=q[i];
        }
    }
    for(rg int i=ed;i>=st;--i)
        if(!q[i].opt&&q[i].z<=mid)add(q[i].x1,q[i].y1,-1);      
    for(rg int i=1;i<=lt;++i)q[st+i-1]=ql[i];
    for(rg int i=1;i<=rt;++i)q[lt+st+i-1]=qr[i];
    solve(l,mid,st,st+lt-1);solve(mid+1,r,st+lt,ed);
}
int main(){
    n=read();Q=read();
    for(rg int i=1;i<=n;++i)
        for(rg int j=1;j<=n;++j)//老套路:把矩阵的赋值也当做操作
            q[++tot].opt=0,q[tot].x1=i,q[tot].y1=j,q[tot].z=read();
    for(rg int i=1;i<=Q;++i){
        q[++tot].x1=read();q[tot].y1=read();q[tot].x2=read();q[tot].y2=read();q[tot].z=read();
        q[tot].opt=i;
    }
    solve(0,1e9,1,tot);for(rg int i=1;i<=Q;++i)printf("%d\n",ans[i]);
    return 0;
}