整体二分 P1527 [国家集训队]矩阵乘法
题目描述
给你一个N*N的矩阵，不用算矩阵乘法，但是每次询问一个子矩形的第K小数。
输入格式
第一行两个数N,Q，表示矩阵大小和询问组数；
接下来N行N列一共N*N个数，表示这个矩阵；
再接下来Q行每行5个数描述一个询问：x1,y1,x2,y2,k表示找到以(x1,y1)为左上角、以(x2,y2)为右下角的子矩形中的第K小数。
输出格式
对于每组询问输出第K小的数。
输入输出样例
输入 #12 2 2 1 3 4 1 2 1 2 1 1 1 2 2 3输出 #11 3说明/提示
矩阵中数字是10^9以内的非负整数；
20%的数据：N<=100,Q<=1000；
40%的数据：N<=300,Q<=10000；
60%的数据：N<=400,Q<=30000；
100%的数据：N<=500,Q<=60000。
1 #include<bits/stdc++.h> 2 #define re register int 3 #define maxn 500+5 4 #define maxn1 60000+5 5 #define maxn2 250000+5 6 7 using namespace std; 8 int n,q; 9 int ans[maxn1],id[maxn1]; 10 int sum[maxn1]; 11 int tree[maxn][maxn]; 12 int tmp1[maxn1],tmp2[maxn1]; 13 struct matr{ 14 int x,y,val; 15 }ma[maxn2]; 16 struct query{ 17 int lx,ly,rx,ry,k; 18 }qu[maxn1]; 19 int cnt,tmp; 20 bool cmp(const matr&a,const matr&b) 21 { 22 return a.val<b.val; 23 } 24 int lowbit(int x) 25 { 26 return x&-x; 27 } 28 void add(int x,int y,int val) 29 { 30 for(re i=x;i<=n;i+=lowbit(i)) 31 for(re j=y;j<=n;j+=lowbit(j)) 32 tree[i][j]+=val; 33 } 34 int cal(int x,int y) 35 { 36 int res=0; 37 for(re i=x;i;i-=lowbit(i)) 38 for(re j=y;j;j-=lowbit(j))//233333不要写j>=0 39 res+=tree[i][j]; 40 return res; 41 } 42 int sol(int lx1,int ly1,int rx1,int ry1) 43 { 44 return cal(rx1,ry1)-cal(lx1-1,ry1)-cal(rx1,ly1-1)+cal(lx1-1,ly1-1); 45 } 46 void dic(int l,int r,int ql,int qr) 47 { 48 if(ql>qr) return; 49 if(l==r) 50 { 51 for(re i=ql;i<=qr;i++) 52 ans[id[i]]=ma[l].val; 53 return; 54 } 55 int mid=(l+r)>>1; 56 int cnt1=0,cnt2=0; 57 for(re i=l;i<=mid;i++) 58 add(ma[i].x,ma[i].y,1);//从l加上<=mid的数，l之前都已经加入sum数组 59 for(re i=ql;i<=qr;i++) 60 { 61 tmp=sol(qu[id[i]].lx,qu[id[i]].ly,qu[id[i]].rx,qu[id[i]].ry); 62 if(tmp+sum[id[i]]>=qu[id[i]].k) tmp1[++cnt1]=id[i]; 63 else sum[id[i]]+=tmp,tmp2[++cnt2]=id[i]; 64 } 65 for(re i=l;i<=mid;i++) 66 add(ma[i].x,ma[i].y,-1); 67 int tmp3=ql-1; 68 for(re i=1;i<=cnt1;i++) 69 id[++tmp3]=tmp1[i]; 70 for(re i=1;i<=cnt2;i++) 71 id[++tmp3]=tmp2[i]; 72 dic(l,mid,ql,ql+cnt1-1); 73 dic(mid+1,r,ql+cnt1,qr); 74 } 75 int main() 76 { 77 ios::sync_with_stdio(false); 78 cin>>n>>q; 79 for(re i=1;i<=n;i++) 80 for(re j=1;j<=n;j++) 81 { 82 cin>>tmp; 83 ma[++cnt].x=i; 84 ma[cnt].y=j; 85 ma[cnt].val=tmp; 86 //毒瘤的坐标存法 87 } 88 sort(ma+1,ma+cnt+1,cmp); 89 for(re i=1;i<=q;i++) 90 cin>>qu[i].lx>>qu[i].ly>>qu[i].rx>>qu[i].ry>>qu[i].k,id[i]=i; 91 dic(1,cnt,1,q); 92 for(re i=1;i<=q;i++) 93 cout<<ans[i]<<endl;//是ans[i]不是ans[id] 94 return 0; 95 }