瑞安 网站建设培训,让医院做网站的策划书,高端的赣州网站建设,成功的营销型网站案例正题
题目链接:https://www.luogu.org/problem/P1527 题目大意
给出一个矩阵#xff0c;每个询问求子矩阵中的第kkk小数。 解题思路
我们发现我们对于每个询问我们可以二分答案#xff0c;然后查找该子矩阵中有多少个数≤mid\leq mid≤mid来判断。
但是这样时间复杂度和空…正题
题目链接:https://www.luogu.org/problem/P1527 题目大意
给出一个矩阵每个询问求子矩阵中的第kkk小数。 解题思路
我们发现我们对于每个询问我们可以二分答案然后查找该子矩阵中有多少个数≤mid\leq mid≤mid来判断。
但是这样时间复杂度和空间复杂度显然无法接受。
所以我们考虑整体二分我们将所有的询问放在一起二分然后单独处理左边的再处理右边的。其中我们可以用二维树状数组可以在O(midqlog2n)O(midq\log^2 n)O(midqlog2n)的时间内处理子矩阵中有多少个数≤mid\leq mid≤mid codecodecode
// luogu-judger-enable-o2
#includecstdio
#includecstring
#includealgorithm
#define lowbit(x) (x-x)
using namespace std;
const int N510,M61000;
int n,m,t[N][N],cnt,ans[M],last;
struct node{int x,y,w;
}a[N*N];
struct Que_node{int x1,y1,x2,y2,k,pos;
}q[M],q1[M],q2[M];
void change(int x,int y,int val)
{for(int ix;in;ilowbit(i))for(int jy;jn;jlowbit(j))t[i][j]val;return;
}
int ask(int x,int y)
{int ans0;for(int ix;i;i-lowbit(i))for(int jy;j;j-lowbit(j))anst[i][j];return ans;
}
int query(int x1,int y1,int x2,int y2)
{return ask(x2,y2)ask(x1-1,y1-1)-ask(x1-1,y2)-ask(x2,y1-1);}
void get_ans(int l,int r,int L,int R)
{int mid(lr)1;if(LR) return;if(lr){for(int iL;iR;i)ans[q[i].pos]a[l].w;return;}for(int il;imid;i)change(a[i].x,a[i].y,1);int cnt10,cnt20;for(int iL;iR;i){int xquery(q[i].x1,q[i].y1,q[i].x2,q[i].y2);if(xq[i].k) q1[cnt1]q[i];else q[i].k-x,q2[cnt2]q[i];}for(int il;imid;i)change(a[i].x,a[i].y,-1);int zL-1;for(int i1;icnt1;i)q[z]q1[i];for(int i1;icnt2;i)q[z]q2[i];get_ans(l,mid,L,Lcnt1-1);get_ans(mid1,r,Lcnt1,R);return;
}
bool cMp(node x,node y)
{return x.wy.w;}
int main()
{scanf(%d%d,n,m);for(int i1;in;i)for(int j1;jn;j){int x;scanf(%d,x);a[cnt](node){i,j,x};}sort(a1,a1cnt,cMp);for(int i1;im;i)scanf(%d%d%d%d%d,q[i].x1,q[i].y1,q[i].x2,q[i].y2,q[i].k),q[i].posi;get_ans(1,cnt,1,m);for(int i1;im;i)printf(%d\n,ans[i]);
}
/*
3 3
2 0 6
3 4 0
8 9 5
1 2 2 3 1
1 1 3 3 7
*/
