整体二分+树状数组
过了【BZOJ】【2527】【POI2011】Meteors以后这题就没那么难啦~
关键是【从小到大】依次插入数字，然后整体二分每个查询的第k大是在第几次插入中被插入的……嗯大概就是这样
/**************************************************************
Problem: 2738
User: Tunix
Language: C++
Result: Accepted
Time:11852 ms
Memory:7216 kb
****************************************************************/ //BZOJ 2738
#include<cstdio>
#include<cstring>
#include<cstdlib>
#include<iostream>
#include<algorithm>
#define rep(i,n) for(int i=0;i<n;++i)
#define F(i,j,n) for(int i=j;i<=n;++i)
#define D(i,j,n) for(int i=j;i>=n;--i)
#define pb push_back
using namespace std;
typedef long long LL;
inline int getint(){
int r=,v=; char ch=getchar();
for(;!isdigit(ch);ch=getchar()) if (ch=='-') r=-;
for(; isdigit(ch);ch=getchar()) v=v*-''+ch;
return r*v;
}
const int N=,M=;
/*******************template********************/ int n,m;
struct node{
int v,x,y;
}a[N*N];
bool cmp(node a,node b){return a.v<b.v;}
struct ques{
int x1,y1,x2,y2,k;
void read(){x1=getint(); y1=getint(); x2=getint(); y2=getint(); k=getint();}
}Q[M]; int c[N][N];
int t[M],q[M],ans[M]; void add(int x,int y,int v){
for(int i=x;i<=n;i+=i&(-i))
for(int j=y;j<=n;j+=j&(-j)) c[i][j]+=v;
}
int sum(int x,int y){
int r=;
for(int i=x;i;i-=i&(-i))
for(int j=y;j;j-=j&(-j)) r+=c[i][j];
return r;
}
int sum(int x1,int y1,int x2,int y2){
x1--; y1--;
return sum(x2,y2)-sum(x1,y2)-sum(x2,y1)+sum(x1,y1);
}
void solve(int ql,int qr,int l,int r){
// printf("solve %d %d %d %d",ql,qr,l,r); cout <<endl;
if (ql>qr) return;
if (l==r){
F(i,ql,qr) ans[t[i]]=a[l].v;
return;
}
int t1=ql-,t2=qr+,mid=l+r>>;
F(i,l,mid) add(a[i].x,a[i].y,);
F(i,ql,qr){
int x1=Q[t[i]].x1,y1=Q[t[i]].y1,x2=Q[t[i]].x2,y2=Q[t[i]].y2,k=Q[t[i]].k;
int num=sum(x1,y1,x2,y2);
// printf("%d %d %d %d num=%d\n",x1,y1,x2,y2,num);
if (num>=k) q[++t1]=t[i];
else Q[t[i]].k-=num,q[--t2]=t[i];
}
F(i,ql,qr) t[i]=q[i];
F(i,l,mid) add(a[i].x,a[i].y,-);
solve(ql,t1,l,mid); solve(t2,qr,mid+,r);
} int main(){
#ifndef ONLINE_JUDGE
freopen("2738.in","r",stdin);
freopen("2738.out","w",stdout);
#endif
n=getint(); m=getint();
F(i,,n) F(j,,n){
int t=(i-)*n+j;
a[t].v=getint();
a[t].x=i; a[t].y=j;
}
sort(a+,a+n*n+,cmp);
F(i,,m) Q[i].read(),t[i]=i; solve(,m,,n*n);
F(i,,m) printf("%d\n",ans[i]);
return ;
}
2738: 矩阵乘法
Time Limit: 20 Sec Memory Limit: 256 MB
Submit: 859 Solved: 364
[Submit][Status][Discuss]
Description
给你一个N*N的矩阵，不用算矩阵乘法，但是每次询问一个子矩形的第K小数。
Input
第一行两个数N,Q，表示矩阵大小和询问组数；
接下来N行N列一共N*N个数，表示这个矩阵；
再接下来Q行每行5个数描述一个询问：x1,y1,x2,y2,k表示找到以(x1,y1)为左上角、以(x2,y2)为右下角的子矩形中的第K小数。
接下来N行N列一共N*N个数，表示这个矩阵；
再接下来Q行每行5个数描述一个询问：x1,y1,x2,y2,k表示找到以(x1,y1)为左上角、以(x2,y2)为右下角的子矩形中的第K小数。
Output
对于每组询问输出第K小的数。
Sample Input
2 2
2 1
3 4
1 2 1 2 1
1 1 2 2 3
2 1
3 4
1 2 1 2 1
1 1 2 2 3
Sample Output
1
3
3
HINT
矩阵中数字是109以内的非负整数；
20%的数据：N<=100,Q<=1000；
40%的数据：N<=300,Q<=10000；
60%的数据：N<=400,Q<=30000；
100%的数据：N<=500,Q<=60000。