时间限制：2.0s   内存限制：256.0MB  

总提交次数：515   AC次数：211   平均分：54.14

 

将本题分享到：

      

查看未格式化的试题   提交   试题讨论

试题来源

　　2012中国国家集训队命题答辩

问题描述

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

输入格式

　　第一行两个数N,Q，表示矩阵大小和询问组数；
　　接下来N行N列一共N*N个数，表示这个矩阵；
　　再接下来Q行每行5个数描述一个询问：x1,y1,x2,y2,k表示找到以(x1,y1)为左上角、以(x2,y2)为右下角的子矩形中的第K小数。

输出格式

　　对于每组询问输出第K小的数。

样例输入

2 2
2 1
3 4
1 2 1 2 1
1 1 2 2 3

样例输出

1
3

数据规模和约定

　　矩阵中数字是10⁹以内的非负整数；
　　20%的数据：N<=100,Q<=1000；
　　40%的数据：N<=300,Q<=10000；
　　60%的数据：N<=400,Q<=30000；
　　100%的数据：N<=500,Q<=60000。

#include<cstdio>

#include<iostream>

using namespace std;

inline int read(){

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

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

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

    return x*f;

}

const int N=,Z=3.5e5+;

const int inf=2e9;

struct node{

    int x1,x2,y1,y2,k,opt,id;

}p[Z],p1[Z],p2[Z];

int n,m,tot,BIT[N][N],ans[Z];

int mx,mn;

inline int lowbit(int x){

    return x&-x;

}

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

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

        for(int j=y;j<=n;j+=lowbit(j)){

            BIT[i][j]+=v;

        }

    }

}

inline int query(int x,int y){

    int res=;

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

        for(int j=y;j;j-=lowbit(j)){

            res+=BIT[i][j];

        }

    }

    return res;

}

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

    if(l>r||x>y) return ;

    if(x==y){

        for(int i=l;i<=r;i++) if(p[i].opt) ans[p[i].id]=x;

        return ;

    }

    int mid=x+y>>,i,t1(),t2(),tt();

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

        if(!p[i].opt){

            if(p[i].k<=mid){

                p1[++t1]=p[i];

                update(p1[t1].x1,p1[t1].y1,);

            }

            else{

                p2[++t2]=p[i];

            }

        }

        else{

            tt=query(p[i].x2,p[i].y2)-query(p[i].x1-,p[i].y2)-query(p[i].x2,p[i].y1-)+query(p[i].x1-,p[i].y1-);

            if(p[i].k<=tt){

                p1[++t1]=p[i];

            }

            else{

                p[i].k-=tt;

                p2[++t2]=p[i];

            }

        }

    }

    for(i=;i<=t1;i++) if(!p1[i].opt) update(p1[i].x1,p1[i].y1,-);

    for(i=;i<=t1;i++) p[l+i-]=p1[i];

    for(i=;i<=t2;i++) p[l+t1+i-]=p2[i];

    solve(l,l+t1-,x,mid);

    solve(l+t1,r,mid+,y);

}

int main(){

    mx=-inf;mn=inf;

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

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

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

            p[++tot].opt=;

            p[tot].x1=i;

            p[tot].y1=j;

            p[tot].k=read();

            mx=max(mx,p[tot].k);

            mn=min(mn,p[tot].k);

        }

    }

    for(int i=;i<=m;i++){

        p[++tot].opt=;

        p[tot].x1=read();

        p[tot].y1=read();

        p[tot].x2=read();

        p[tot].y2=read();

        p[tot].k=read();

        p[tot].id=i;

    }

    solve(,tot,mn,mx);

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

    return ;

}