BZOJ 2738: 矩阵乘法 [整体二分]

时间：2023-03-08 20:11:15
给你一个N*N的矩阵，不用算矩阵乘法，但是每次询问一个子矩形的第K小数。
愚蠢的名字......
整体二分，影响因子就是矩阵里的数
把$\le mid$的矩阵元素加到二维树状数组里然后询问分成两组就行了
可以把矩阵元素权值排序后直接二分矩阵元素而不是值
复杂度$O(nlog^3n)$
用排序代替一维树状数组理论上更快，但需要把矩阵里的元素和查询放到一个数组里再排序貌似常数太大
然后发现黄学长的做法是错误的复杂度不对....但竟然比我快....
二维树状数组一定不要写错！！！
#include<iostream>

#include<cstdio>

#include<cstring>

#include<algorithm>

#include<cmath>

using namespace std;

const int N=,M=6e4+,INF=1e9;

typedef long long ll;

inline int read(){

    char c=getchar();int x=,f=;

    while(c<''||c>''){if(c=='-')f=-; c=getchar();}

    while(c>=''&&c<=''){x=x*+c-''; c=getchar();}

    return x*f;

}

int n,Q;

struct Factor{

    int x,y,v;

    Factor(){}

    Factor(int a,int b,int c):x(a),y(b),v(c){}

    bool operator <(const Factor &r)const{return v<r.v;}

}a[N*N];

int m,now=;

struct Query{

    int x1,y1,x2,y2,k;

}q[M];

int id[M],t1[M],t2[M],cur[M];

int c[N][N];

inline int lowbit(int x){return x&-x;}

inline void add(int x,int y,int v){

    for(int i=x;i<=n;i+=lowbit(i))

        for(int j=y;j<=n;j+=lowbit(j)) c[i][j]+=v;

}

inline int sum(int x,int y){

    int re=;

    for(int i=x;i;i-=lowbit(i))

        for(int j=y;j;j-=lowbit(j)) re+=c[i][j];

    return re;

}

inline int que(int i){

    int x1=q[i].x1-,y1=q[i].y1-,x2=q[i].x2,y2=q[i].y2;

    return sum(x2,y2)-sum(x1,y2)-sum(x2,y1)+sum(x1,y1);

}

int ans[M];

void Sol(int l,int r,int ql,int qr){

    if(ql>qr) return;

    if(l==r){

        for(int i=ql;i<=qr;i++) ans[id[i]]=a[l].v;

        return;

    }

    int mid=(l+r)>>;

    for(int i=l;i<=mid;i++) add(a[i].x,a[i].y,);

    int p1=,p2=;

    for(int i=ql;i<=qr;i++){

        int u=id[i],s=cur[u]+que(u);

        if(s>=q[u].k) t1[++p1]=u;

        else t2[++p2]=u,cur[u]=s;

    }

    for(int i=l;i<=mid;i++) add(a[i].x,a[i].y,-);

    for(int i=;i<=p1;i++) id[ql+i-]=t1[i];

    for(int i=;i<=p2;i++) id[ql+p1+i-]=t2[i];

    Sol(l,mid,ql,ql+p1-);

    Sol(mid+,r,ql+p1,qr);

}

int main(){

    freopen("in","r",stdin);

    n=read();Q=read();

    for(int i=;i<=n;i++)

        for(int j=;j<=n;j++) a[++m]=Factor(i,j,read());

    for(int i=;i<=Q;i++)

        q[i].x1=read(),q[i].y1=read(),q[i].x2=read(),q[i].y2=read(),q[i].k=read();

    sort(a+,a++m);

    for(int i=;i<=Q;i++) id[i]=i;

    Sol(,m,,Q);

    for(int i=;i<=Q;i++) printf("%d\n",ans[i]);

}

相关文章