BZOJ-2738: 矩阵乘法

[文章目录]

Description

给你一个N*N的矩阵,不用算矩阵乘法,但是每次询问一个子矩形的第K小数。n<=500 q<=60000

重新看遍题,好像可以线段树套权值主席树做:对于行维护外层线段树,外层线段树上对应的行再对于列维护权值线段树,不同的列间通过主席树的方式递推下去。每次查询矩形区域,我们找到行对应的log段线段,之后在每个主席树上差分列,二分权值即可。时间复杂度,空间
然而这道题是整体二分的模板题。。。
离线询问对于询问和权值范围同时分治,每次查询左区间的权值在所有询问矩形中出现的个数,和K比较递归将询问分治。
n很小,二维树状数组差分维护矩形内出现点的个数即可(懒得扫描线)。
时间复杂度空间

#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
#define N 510 
int n,m;
struct node
{
    int x,y,w;
}a[N*N];
bool cmp(node x,node y){return x.w<y.w;}
struct ques
{
    int x1,x2,y1,y2,k;
}q[61000];
int cg[61000],t[61000],ans[61000];
int f[N][N];
void fix(int x,int y,int w)
{
    int i;
    while(x<=n)
    {
        for(i=y;i<=n;i+=-i&i) f[x][i]+=w;
        x+=-x&x;
    }
}
int query(int x,int y)
{
    int re=0,i;
    while(x>0)
    {
        for(i=y;i>0;i-=-i&i) re+=f[x][i];
        x-=-x&x;
    }
    return re;
}
void solve(int l,int r,int L,int R)
{
    if(l==r)
    {
        for(int i=L;i<=R;++i) ans[cg[i]]=a[l].w;
        return ;
    }
    int mid=(l+r)>>1,tmp,i1=L,i2=R;
    for(int i=l;i<=mid;++i) fix(a[i].x,a[i].y,1);
    for(int i=L;i<=R;++i)
    {
        tmp=query(q[cg[i]].x2,q[cg[i]].y2)-query(q[cg[i]].x1-1,q[cg[i]].y2)
        -query(q[cg[i]].x2,q[cg[i]].y1-1)+query(q[cg[i]].x1-1,q[cg[i]].y1-1);
        if(q[cg[i]].k<=tmp) t[i1++]=cg[i];
        else t[i2--]=cg[i],q[cg[i]].k-=tmp;
    }
    for(int i=L;i<=R;++i) cg[i]=t[i];
    for(int i=l;i<=mid;++i) fix(a[i].x,a[i].y,-1);
    if(i2>=L) solve(l,mid,L,i2);
    if(i1<=R) solve(mid+1,r,i1,R);
}
int main()
{
    scanf("%d%d",&n,&m);
    int t=0;
    for(int i=1;i<=n;++i)
        for(int j=1;j<=n;++j)
        {
            ++t;
            scanf("%d",&a[t].w);
            a[t].x=i; a[t].y=j;
        }
    sort(a+1,a+t+1,cmp);
    for(int i=1;i<=m;++i) scanf("%d%d%d%d%d",&q[i].x1,&q[i].y1,&q[i].x2,&q[i].y2,&q[i].k),cg[i]=i;
    solve(1,t,1,m);
    for(int i=1;i<=m;++i) printf("%d\n",ans[i]);
    return 0;
}

发表评论

邮箱地址不会被公开。 必填项已用*标注