BZOJ2738 矩阵乘法（整体二分+树状数组）

时间：2023-03-09 23:29:11
BZOJ2738 矩阵乘法（整体二分+树状数组）

　　单个询问二分答案即可，多组询问直接整体二分再二维BIT。注意保证复杂度。

#include<iostream>

#include<cstdio>

#include<cmath>

#include<cstdlib>

#include<cstring>

#include<algorithm>

using namespace std;

#define ll long long

#define N 510

#define M 60010

char getc(){char c=getchar();while ((c<'A'||c>'Z')&&(c<'a'||c>'z')&&(c<'0'||c>'9')) c=getchar();return c;}

int gcd(int n,int m){return m==0?n:gcd(m,n%m);}

int read()

{

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

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

    while (c>='0'&&c<='9') x=(x<<1)+(x<<3)+(c^48),c=getchar();

    return x*f;

}

int n,m,a[N][N],ans[M],tree[N][N],t;

struct data{int xl,yl,xr,yr,k,i;

}q[M],p[M];

struct data2

{

    int x,y,k;

    bool operator <(const data2&a) const

    {

        return k<a.k;

    }

}b[N*N];

int query(int x,int y)

{

    int s=0;

    for (int i=x;i;i^=i&-i)

        for (int j=y;j;j^=j&-j)

        s+=tree[i][j];

    return s;

}

void add(int x,int y,int p)

{

    for (int i=x;i<=n;i+=i&-i)

        for (int j=y;j<=n;j+=j&-j)

        tree[i][j]+=p;

}

int query(int xl,int yl,int xr,int yr){return query(xr,yr)-query(xl-1,yr)-query(xr,yl-1)+query(xl-1,yl-1);}

void solve(int l,int r,int x,int y)

{

    if (l>r) return;

    if (x==y)

    {

        for (int i=l;i<=r;i++) ans[q[i].i]=b[x].k;

        return;

    }

    int mid=x+y>>1,L=l,R=r;

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

    for (int i=l;i<=r;i++)

    {

        int u=query(q[i].xl,q[i].yl,q[i].xr,q[i].yr);

        if (u<q[i].k) q[i].k-=u,p[R--]=q[i];

        else p[L++]=q[i];

    }

    for (int i=l;i<=r;i++) q[i]=p[i];

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

    solve(l,L-1,x,mid);

    solve(R+1,r,mid+1,y);

}

int main()

{

#ifndef ONLINE_JUDGE

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

    freopen("matrix.out","w",stdout);

    const char LL[]="%I64d\n";

#else

    const char LL[]="%lld\n";

#endif

    n=read(),m=read();

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

        for (int j=1;j<=n;j++)

        {

            a[i][j]=read();

            t++;b[t].k=a[i][j],b[t].x=i,b[t].y=j;

        }

    sort(b+1,b+t+1);

    for (int i=1;i<=m;i++) q[i].xl=read(),q[i].yl=read(),q[i].xr=read(),q[i].yr=read(),q[i].k=read(),q[i].i=i;

    solve(1,m,1,n*n);

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

    return 0;

}

相关文章