给你一个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
矩阵中数字是109以内的非负整数;
20%的数据:N<=100,Q<=1000;
40%的数据:N<=300,Q<=10000;
60%的数据:N<=400,Q<=30000;
100%的数据:N<=500,Q<=60000。
很想问出题人题目的名字是什么情况……
完全和题目内容无关的名字啊……
其实咱是来学二维树状数组的……
思路:
第一眼CDQ……
然后发现好像不太会写……
那就整体二分吧。
那么考虑把输入的每个点按值排序,整体二分答案的值。
每次二分时,维护一个二维树状数组,将值小于当前二分值的点加入树状数组。
那么对于每个询问,以树状数组的查询结果是否大于k作为判断依据即可~
#include#include #include #include #include using namespace std; typedef long long ll; const int N=509; const int M=60009; inline int read() { int x=0;char ch=getchar(); while(ch<'0' || '9' >1; if(st>ed)return; if(l==r) { for(int i=st;i<=ed;i++) ans[q[i].id]=mid; return; } while(cur mid) add(g[cur].x,g[cur].y,-1),cur--; int ltp=st-1,rtp=ed+1; for(int i=st;i<=ed;i++) { int val=query(q[i].x2,q[i].y2)-query(q[i].x2,q[i].y1-1)-query(q[i].x1-1,q[i].y2)+query(q[i].x1-1,q[i].y1-1); if(q[i].k<=val) tq[++ltp]=q[i]; else tq[--rtp]=q[i]; } for(int i=st;i<=ed;i++) q[i]=tq[i]; solve(st,ltp,l,mid); solve(rtp,ed,mid+1,r); } int main() { n=read(); m=read(); int mval=0; for(int i=1;i<=n;i++) for(int j=1;j<=n;j++) { g[++tot]=(node){read(),i,j}; mval=max(mval,g[tot].val); } sort(g+1,g+tot+1); for(int i=1;i<=m;i++) { q[i].x1=read(); q[i].y1=read(); q[i].x2=read(); q[i].y2=read(); q[i].k=read(); q[i].id=i; } solve(1,m,1,mval); for(int i=1;i<=m;i++) printf("%d\n",ans[i]); return 0; }