矩阵乘法 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 <iostream>

#include <cstdio>

#include <cstring>

#include <algorithm>

#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<b.val;}

struct Node {int x1,x2,y1,y2,k,id;}q[M],t[M];

inline char nc() {static char *p1,*p2,buf[100000]; return (p1==p2)&&(p2=(p1=buf)+fread(buf,1,100000,stdin),p1==p2)?EOF:*p1++;}

int rd() {int x=0; char c=nc(); while(!isdigit(c)) c=nc(); while(isdigit(c)) x=(x<<3)+(x<<1)+(c^48),c=nc(); return x;}

inline int lowbit(int x) {return x&(-x);}

void update(int x,int y,int val)

{

	for(int i=x;i<=n+1;i+=lowbit(i)) for(int j=y;j<=n+1;j+=lowbit(j)) tree[i][j]+=val;

}

int query(int x,int y)

{

	int ans=0; for(int i=x;i>=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;

}

小结：整体二分好好玩~

巴特西

[bzoj2738]矩阵乘法_整体二分_树状数组

矩阵乘法 bzoj-2738

最新文章

热门文章