[luogu P1527]矩阵乘法（矩形k小）

传送门

Description

给你一个N*N的矩阵，不用算矩阵乘法，但是每次询问一个子矩形的第K小数。

Solution

整体二分

练习一波。。。

就是一堆询问放在一起二分

另外的，第一次发现原来矩形求和是可以用二维树状数组来维护的

果然是pac太菜了

class BIT

{

    #define NM 505

    #define lb(x) (x&(-x))

    private:

        int t[NM][NM],N,M;

        BIT() {}

    public:

        BIT(int _N=0,int _M=0):N(_N),M(_M){memset(t,0,sizeof t);}

        inline void C(int x,int y,int v)

        {

            register int i,j;

            for(i=x;i<=N;i+=lb(i))for(j=y;j<=M;j+=lb(j)) t[i][j]+=v;

        }

        inline int G(int x,int y)

        {

            register int i,j,ret=0;

            for(i=x;i;i-=lb(i))for(j=y;j;j-=lb(j)) ret+=t[i][j];

            return ret;

        }

        inline int GM(int x,int y,int a,int b){return G(a,b)-G(x-1,b)-G(a,y-1)+G(x-1,y-1);}

};

Code

#include<bits/stdc++.h>

#define ll long long

#define max(a,b) ((a)>(b)?(a):(b))

#define min(a,b) ((a)<(b)?(a):(b))

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<<3)+(x<<1)+ch-'0';ch=getchar();}

    return x*f;

}

#define MN 60002

#define MS 250005

int N,Q,Ans[MN];

struct ques{int x1,y1,x2,y2,k,id;}q[MN],b[MN];

struct nums{

    int x,y,val;

    bool operator <(const nums &o) const{return val<o.val;}

}s[MS];

class BIT

{

    #define NM 505

    #define lb(x) (x&(-x))

    private:

        int t[NM][NM],N,M;

        BIT() {}

    public:

        BIT(int _N=0,int _M=0):N(_N),M(_M){memset(t,0,sizeof t);}

        inline void C(int x,int y,int v)

        {

            register int i,j;

            for(i=x;i<=N;i+=lb(i))for(j=y;j<=M;j+=lb(j)) t[i][j]+=v;

        }

        inline int G(int x,int y)

        {

            register int i,j,ret=0;

            for(i=x;i;i-=lb(i))for(j=y;j;j-=lb(j)) ret+=t[i][j];

            return ret;

        }

        inline int GM(int x,int y,int a,int b){return G(a,b)-G(x-1,b)-G(a,y-1)+G(x-1,y-1);}

};

void solve(int l=1,int r=N*N,int ql=1,int qr=Q)

{

    static BIT T(N,N);

    register int i;

    if(ql>qr) return;

    if(l==r)

    {

        for(i=ql;i<=qr;++i) Ans[q[i].id]=l;

        return;

    }

    register int mid=(l+r)>>1,tmpl=ql,tmpr=qr,gm;

    for(i=l;i<=mid;++i) T.C(s[i].x,s[i].y,1);

    for(i=ql;i<=qr;++i) (gm=T.GM(q[i].x1,q[i].y1,q[i].x2,q[i].y2))>=q[i].k?b[tmpl++]=q[i]:(q[i].k-=gm,b[tmpr--]=q[i]);

    for(i=ql;i<=qr;++i) q[i]=b[i];

    for(i=l;i<=mid;++i) T.C(s[i].x,s[i].y,-1);

    solve(l,mid,ql,tmpl-1);solve(mid+1,r,tmpr+1,qr);

}

int main()

{

    N=read();Q=read();

    register int i,j;

    for(i=1;i<=N;++i)for(j=1;j<=N;++j) s[(i-1)*N+j]=(nums){i,j,read()};

    for(i=1;i<=Q;++i) q[i].x1=read(),q[i].y1=read(),q[i].x2=read(),q[i].y2=read(),q[i].k=read(),q[i].id=i;

    std::sort(s+1,s+N*N+1);

    solve();

    for(i=1;i<=Q;++i) printf("%d\n",s[Ans[i]].val);

    return 0;

}

Blog来自PaperCloud，未经允许，请勿转载，TKS！

巴特西

[luogu P1527]矩阵乘法（矩形k小）

传送门

Description

Solution

Code

最新文章

热门文章