tsinsen A1333. 矩阵乘法（梁 盾）

A1333. 矩阵乘法（梁 盾）

时间限制：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。

poj2104 k-th的二维拓展，开个二维树状数组即可！

#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 ;
}