luogu P1527 矩阵乘法

题目链接

给你一个矩阵询问子矩阵的第k小

整体二分练习题,就是多了一个二维前缀和,直接二维树状数组就行了

#include<bits/stdc++.h>

#define fi first
#define se second
#define mp make_pair
#define pb push_back
#define LL long long
#define pii pair<int,int>
#define SZ(x) (int)x.size()
#define all(x) x.begin(),x.end()

using namespace std;

LL gcd(LL a, LL b) {return b ? gcd(b, a % b) : a;}
LL lcm(LL a, LL b) {return a / gcd(a, b) * b;}
LL powmod(LL a, LL b, LL MOD) {LL ans = 1; while (b) {if (b % 2)ans = ans * a % MOD; a = a * a % MOD; b /= 2;} return ans;}
const int N = 5e5 + 3;
const LL mod = 1e9 + 7;
int n,q;
int a[555][555];
struct uzi{
    LL o,x,y,a,b,d,pos;
}p[N],q1[N],q2[N];
int cnt;
LL ans[N];
LL t[555][555];
void add(int k,int p,LL d){
    for(int i=k;i<=n;i+=i&-i){
        for(int j=p;j<=n;j+=j&-j)t[i][j]+=d;
    }
}
LL get(int a,int b){
    LL A=0;
    if(!a||!b)return 0;
    for(int i=a;i;i-=i&-i){
        for(int j=b;j;j-=j&-j)A+=t[i][j];
    }
    return A;
}
void solve(LL l,LL r,int x,int y){
    if(l>r||x>y)return ;
    if(l==r){
        for(int i=x;i<=y;i++)if(p[i].o==2)ans[p[i].pos]=l;
        return ;
    }
    int c=0,d=0;
    LL mid=l+r>>1;
    for(int i=x;i<=y;i++){
        if(p[i].o==1){
            if(p[i].a<=mid)add(p[i].x,p[i].y,1),q1[++c]=p[i];
            else q2[++d]=p[i];
        }else{
            LL res=get(p[i].a,p[i].b)-get(p[i].a,p[i].y-1)-get(p[i].x-1,p[i].b)+get(p[i].x-1,p[i].y-1);
            if(res>=p[i].d)q1[++c]=p[i];
            else p[i].d-=res,q2[++d]=p[i];
        }
    }
    for(int i=1;i<=c;i++)if(q1[i].o==1)add(q1[i].x,q1[i].y,-1);
    for(int i=x;i<=x+c-1;i++)p[i]=q1[i-x+1];
    for(int i=x+c;i<=y;i++)p[i]=q2[i-x-c+1];
    solve(l,mid,x,x+c-1);
    solve(mid+1,r,x+c,y);
}
int main() {
	ios::sync_with_stdio(false);
    cin>>n>>q;
    for(int i=1;i<=n;i++)for(int j=1;j<=n;j++)cin>>a[i][j],p[++cnt]={1,i,j,a[i][j],0,0,0};
    for(int i=1;i<=q;i++){
        int x1,x2,y1,y2,k;
        cin>>x1>>y1>>x2>>y2>>k;
        p[++cnt]={2,x1,y1,x2,y2,k,i};
    }
    solve(-1e10,1e10,1,cnt);
    for(int i=1;i<=q;i++)cout<<ans[i]<<endl;
	return 0;
}