題目傳送門

矩陣乘法

題目描述

給你一個N*N的矩陣，不用算矩陣乘法，但是每次詢問一個子矩形的第K小數。

輸入輸出格式

輸入格式：

?

第一行兩個數N,Q，表示矩陣大小和詢問組數；

接下來N行N列一共N*N個數，表示這個矩陣；

再接下來Q行每行5個數描述一個詢問：x1,y1,x2,y2,k表示找到以(x1,y1)為左上角、以(x2,y2)為右下角的子矩形中的第K小數。

?

輸出格式：

?

對于每組詢問輸出第K小的數。

?

輸入輸出樣例

輸入樣例#1：?
2 2 2 1 3 4 1 2 1 2 1 1 1 2 2 3 輸出樣例#1：?
1 3

說明

矩陣中數字是10^9以內的非負整數；

20%的數據：N<=100,Q<=1000；

40%的數據：N<=300,Q<=10000；

60%的數據：N<=400,Q<=30000；

100%的數據：N<=500,Q<=60000。

---

　　分析：

　　是的，這道題雖然叫矩陣乘法，但是和矩陣乘法一點關系都沒有。

　　求矩陣$k$小就能想到用整體二分，不過因為是二維，所以需要用二維樹狀數組，然后寫法需要漂亮一點，因為這題有點卡常。

　　另外，有一點需要講一下，平常我寫樹狀數組都是這樣的：

?

inline void add(int pos,int x) {for(; pos<=n; pos+=lowbit(pos)) c[pos]+=x; }

?

　　但是在二維樹狀數組中就不能這么寫，應該寫成：

?

inline void add(int x,int y,int v) {for(int i=x; i<=n; i+=lowbit(i))for(int j=y; j<=n; j+=lowbit(j)) c[i][j]+=v; }

?

　　Code：

?

//It is made by HolseLee on 6th Oct 2018 //Luogu.org P1527 #include<cstdio> #include<cstring> #include<iostream> #include<algorithm> using namespace std;const int N=4e5+7; int n,m,cnt,c[505][505],q1[N],q2[N],id[N],ans[N]; struct Node {int x,y,v;Node() {}Node(const int _x,const int _y,const int _v):x(_x), y(_y), v(_v) {}bool operator < (const Node a) const {return v < a.v;} }a[N]; struct Qus {int x1,y1,x2,y2,k; }q[N];inline int read() {char ch=getchar(); int num =0; bool flag=false;while( ch<'0' || ch>'9' ) {if( ch=='-' ) flag=true; ch=getchar();}while( ch>='0' && ch<='9' ) {num=num*10+ch-'0'; ch=getchar();}return flag ? -num : num; }inline int lowbit(int x) {return x&(-x); }inline void add(int x,int y,int v) {for(int i=x; i<=n; i+=lowbit(i)) for(int j=y; j<=n; j+=lowbit(j)) c[i][j]+=v; }inline int quary(int x,int y) {int ret=0;for(int i=x; i; i-=lowbit(i)) for(int j=y; j; j-=lowbit(j)) ret+=c[i][j];return ret; }inline int get(int x1,int y1,int x2,int y2) {return quary(x2,y2)-quary(x1-1,y2)-quary(x2,y1-1)+quary(x1-1,y1-1); }void solve(int l,int r,int L,int R) {if( l>r || L>R ) return;if( l==r ) {for(int i=L; i<=R; ++i) ans[id[i]]=a[l].v;return;}int mid=(l+r)>>1, cnt1=0, cnt2=0;for(int i=l; i<=mid; ++i) add(a[i].x,a[i].y,1);for(int i=L; i<=R; ++i) {int tmp=get(q[id[i]].x1,q[id[i]].y1,q[id[i]].x2,q[id[i]].y2);if( tmp>=q[id[i]].k ) q1[++cnt1]=id[i];else q[id[i]].k-=tmp, q2[++cnt2]=id[i];}for(int i=l; i<=mid; ++i) add(a[i].x,a[i].y,-1);for(int i=1; i<=cnt1; ++i) id[L+i-1]=q1[i];for(int i=1; i<=cnt2; ++i) id[L+cnt1+i-1]=q2[i];solve(l,mid,L,L+cnt1-1); solve(mid+1,r,L+cnt1,R); }int main() {n=read(), m=read();for(int i=1; i<=n; ++i) for(int j=1; j<=n; ++j){a[++cnt]=Node(i,j,read());}sort(a+1,a+cnt+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(); id[i]=i;}solve(1,cnt,1,m);for(int i=1; i<=m; ++i) printf("%d\n",ans[i]);return 0; }

?

轉載于:https://www.cnblogs.com/cytus/p/9747127.html

總結

以上是生活随笔為你收集整理的洛谷P1527 [国家集训队] 矩阵乘法 [整体二分，二维树状数组]的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。