「BZOJ2738」矩阵乘法
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。
题解
整体二分+二维树状数组
二分询问的答案mid，将数值小等mid的全部插入二维树状数组
然后查询每个矩阵内的元素个数，若数量>K-1则放左边，否则放右边
继续向下分治，左边二分l-mid，右边mid-r
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 |
#include<iostream> #include<cstdio> #include<cstring> #include<cstdlib> #include<set> #include<ctime> #include<vector> #include<queue> #include<algorithm> #include<map> #include<cmath> #define inf 1000000000 #define mod 1000000007 #define ll long long using namespace std; inline int read() { int x=0,f=1;char ch=getchar(); while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();} while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();} return x*f; } int n,m,cnt,T; int t[505][505],ans[60005]; int id[60005],tmp[60005]; bool mark[60005]; struct que{ int x1,x2,y1,y2,K; }q[60005]; struct data{ int x,y,val; }a[250005]; bool operator<(data a,data b) { return a.val<b.val; } void add(int x,int y,int val) { for(int i=x;i<=n;i+=i&-i) for(int j=y;j<=n;j+=j&-j) t[i][j]+=val; } int query(int x,int y) { int tmp=0; for(int i=x;i;i-=i&-i) for(int j=y;j;j-=j&-j) tmp+=t[i][j]; return tmp; } int query(int k) { int x1=q[k].x1,y1=q[k].y1,x2=q[k].x2,y2=q[k].y2; return query(x2,y2)+query(x1-1,y1-1)-query(x1-1,y2)-query(x2,y1-1); } void solve(int l,int r,int L,int R) { if(l>r)return; if(L==R) return; int mid=(L+R)>>1; while(a[T+1].val<=mid&&T<cnt){add(a[T+1].x,a[T+1].y,1);T++;} while(a[T].val>mid){add(a[T].x,a[T].y,-1);T--;} int cnt=0; for(int i=l;i<=r;i++) { if(query(id[i])>q[id[i]].K-1) { mark[i]=1;ans[id[i]]=mid;cnt++; } else mark[i]=0; } int l1=l,l2=l+cnt; for(int i=l;i<=r;i++) if(mark[i])tmp[l1++]=id[i]; else tmp[l2++]=id[i]; for(int i=l;i<=r;i++)id[i]=tmp[i]; solve(l,l1-1,L,mid);solve(l1,l2-1,mid+1,R); } int main() { n=read();m=read(); int mx=0; for(int i=1;i<=n;i++) for(int j=1;j<=n;j++) { a[++cnt].x=i,a[cnt].y=j,a[cnt].val=read(); mx=max(a[cnt].val,mx); } 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(); } for(int i=1;i<=m;i++)id[i]=i; solve(1,m,0,mx+1); for(int i=1;i<=m;i++) printf("%d\n",ans[i]); return 0; } |
Subscribe
计数器 9774785
OI 课件=>
OI 课件=>