矩阵乘法 bzoj-2738

题目大意：给定一个$n*n$的矩阵。每次给定一个矩阵求矩阵$k$小值。

注释：$1\le n\le 500$，$1\le q\le 6\cdot 10^4$。

想法：

新操作整体二分。

整体二分是一个必须离线的算法而且所求的答案必须满足单调性。

所谓单调性就是比如这个题：k越大那么对应的答案越大。

进而我们将所有操作在权值上整体二分。

每次假设当前权值区间为$[l,r]$。

先用二维树状数组求出每个矩形[l,mid]中的点个数然后暴力转移即可。

暴力转移就是看一下$k_i$和个数哪个比较大，考虑把当前操作扔进左区间还是右区间。

Code：

#include 
     
      #include 
      
       #include 
       
        #include 
        
         #define N 510 #define M 60010 using namespace std;int tree[N<<1][N<<1],ans[M],n,m;struct pnt {int x,y,val;}a[N*N]; inline bool cmp(const pnt &a,const pnt &b) {return a.val
         
          =1;i-=lowbit(i)) for(int j=y;j>=1;j-=lowbit(j)) ans+=tree[i][j];	return ans;}void solve(int x,int y,int l,int r){	int tl=x,tr=y;	if(x>y) return;	if(l==r)	{		for(int i=x;i<=y;i++) ans[q[i].id]=a[l].val;		return;	}	int mid=(l+r)>>1;	for(int i=l;i<=mid;i++) update(a[i].x,a[i].y,1);	for(int i=x;i<=y;i++)	{		int dlt=query(q[i].x1-1,q[i].y1-1)+query(q[i].x2,q[i].y2)-query(q[i].x1-1,q[i].y2)-query(q[i].x2,q[i].y1-1);		if(q[i].k<=dlt) t[tl++]=q[i];		else q[i].k-=dlt,t[tr--]=q[i];	}	for(int i=x;i<=y;i++) q[i]=t[i];	for(int i=l;i<=mid;i++) update(a[i].x,a[i].y,-1);	solve(x,tr,l,mid); solve(tl,y,mid+1,r);}int main(){	n=rd(),m=rd(); for(int i=1;i<=n;i++) for(int j=1;j<=n;j++)	{		int id=(i-1)*n+j;		a[id].val=rd(); a[id].x=i,a[id].y=j;	}	sort(a+1,a+n*n+1,cmp);	for(int i=1;i<=m;i++) q[i].x1=rd(),q[i].y1=rd(),q[i].x2=rd(),q[i].y2=rd(),q[i].k=rd(),q[i].id=i;	solve(1,m,1,n*n);	for(int i=1;i<=m;i++) printf("%d\n",ans[i]);	return 0;}