【2024广东集训01-1】specie 做题记录

动物园是一个 $n\times m$ 的网格，初始每个位置都没有动物。

有 $t$ 种动物，每种动物有五个参数 $xl_i,yl_i,xr_i,yr_i,c_i$ 表示这种动物有 $c_i$ 只且不适宜生活在 $(xl_i,yl_i)$ 为左上角，$(xr_i,yr_i)$ 为右下角的矩形中。

保证每种动物至少有一个位置适宜生活。

每只动物需要分配一个适宜生活的位置，每个位置可以容纳无限个动物。

对于一种分配方案，设 $(i,j)$ 有 $c_{i,j}$ 只动物，则其权值为 $\sum \frac{c_{i,j}(c_{i,j}-1)}{2}$。

求最大权值。

$1\le n,m\le 10^3$，$1\le t\le 10^6$。

首先由于 $x(x-1)$ 是凸函数，所以一定是按某个顺序找格子，每次把能放的都放了。

不难注意到一个有用的性质：每种动物都不可能同时覆盖到对角位置（$(1,1)$ 和 $(n,m)$、$(1,m)$ 和 $(n,1)$）*。

设第一个放的位置是 $(x,y)$，则剩下动物的矩形必然包含 $(x,y)$，之后的位置 $(x',y')$ 若在其左上方则令 $(x',y')$ 变为 $(1,1)$ 一定不劣，因为包含 $(x,y)$ 但不包含其左上方某个位置的矩形一定不包含 $(1,1)$。

同理，放完 $(x,y)$ 后只可能在角上放。

根据性质*，放完 $(x,y)$ 后放两个对角一定是最优的。

那么做几次二位前缀和，枚举 $(x,y)$ 统计答案即可。

代码如下：

#include <iostream>
#include <algorithm>
#include <cstdio>

using namespace std;

const int S=1000005,MS=1005;

typedef long long ll;

template<typename T>
inline void read(T &x)
{
	x=0;
	T w=1;
	char c=getchar();
	while(c<'0'||c>'9') w=(c=='-'?-w:w),c=getchar();
	while(c>='0'&&c<='9') x=x*10+c-'0',c=getchar();
	x*=w;
}

int tt,n,m;
int lx[S],rx[S],ly[S],ry[S];
ll a[S];
ll sm,c[MS][MS],d[4][MS][MS];

inline void csum(ll c[MS][MS])
{
	for(int i=1;i<=n;i++)
	{
		for(int j=1;j<=m;j++)
		{
			c[i][j]+=c[i-1][j]+c[i][j-1]-c[i-1][j-1];
		}
	}
}

inline void add(int st,int lx,int rx,int ly,int ry,ll w)
{
	d[st][lx][ly]+=w;
	d[st][lx][ry+1]-=w;
	d[st][rx+1][ly]-=w;
	d[st][rx+1][ry+1]+=w;
}

int main()
{
	freopen("specie.in","r",stdin);
	freopen("specie.out","w",stdout);
	read(tt),read(n),read(m);
	for(int i=1;i<=tt;i++)
	{
		read(lx[i]),read(ly[i]),read(rx[i]),read(ry[i]),read(a[i]);
		sm+=a[i];
		c[lx[i]][ly[i]]+=a[i];
		c[lx[i]][ry[i]+1]-=a[i];
		c[rx[i]+1][ly[i]]-=a[i];
		c[rx[i]+1][ry[i]+1]+=a[i];
		if(lx[i]!=1||ly[i]!=1) add(0,lx[i],rx[i],ly[i],ry[i],a[i]);
		if(rx[i]!=n||ry[i]!=m) add(1,lx[i],rx[i],ly[i],ry[i],a[i]);
		if(lx[i]!=1||ry[i]!=m) add(2,lx[i],rx[i],ly[i],ry[i],a[i]);
		if(rx[i]!=n||ly[i]!=1) add(3,lx[i],rx[i],ly[i],ry[i],a[i]);
	}
	csum(c);
	for(int x=0;x<4;x++) csum(d[x]);
	ll ans=0;
	for(int i=1;i<=n;i++)
	{
		for(int j=1;j<=m;j++)
		{
			ll pre=0;
			for(int k=0;k<4;k++)
			{
				pre=max(pre,d[k][i][j]*(d[k][i][j]-1)/2+(c[i][j]-d[k][i][j])*(c[i][j]-d[k][i][j]-1)/2);
			}
			pre+=(sm-c[i][j])*(sm-c[i][j]-1)/2;
			ans=max(ans,pre);
		}
	}
	printf("%lld\n",ans);
	return 0;
}