[LOJ3192] 「ROI 2019 Day2」课桌

前言

我收回上一篇题解的话，这题我自己做复杂度铁定优化不下去，本地最多 (94pts)。

但是没有时间，只拿了 (12pts)，亏大了。

题目

LOJ

讲解

这题其实就利用一个东西：单调性。

我个人认为这题的结论应该比较显然。

排除掉完全没用的桌子(范围被其它桌子完全包含)，假如我们已经选好了桌子，将桌子按左端点排序后，每组的学生也应该按高度从低到高坐到座位上。

此时我们不再把学生分为 (m) 组，因为组内没什么联系，我们将坐在同一张桌子的同学视为一组，共有 (2m) 组，每组 (n) 个同学。

每组同学使用同一张桌子，这 (2m) 组使用的桌子按左端点单调不降。

然后我们直接对新定义的组分治，求出中间那个组的贡献之后，由于桌子也是单调的，往两边分治就好了。

用飘飘蛋的话来说：实现的时候要精细一点，用 two-pointer 可以显著降低复杂度。

时间复杂度 (O((k+nm)log_2n))。

代码

不精细的实现

//12252024832524
#include <bits/stdc++.h>
#define TT template<typename T>
using namespace std;

typedef long long LL;
const int MAXN = 200005;
const LL INF = 1ll << 60;
int m,n,k;
int o[MAXN << 1]; 
bool tag[MAXN];
struct desk
{
	int l,r;
	bool operator < (const desk &px)const{
		if(l^px.l) return l < px.l;
		return r > px.r;
	}
}d[MAXN];
vector<desk> a[MAXN];

LL Read()
{
	LL x = 0,f = 1; char c = getchar();
	while(c > '9' || c < '0'){if(c == '-')f = -1;c = getchar();}
	while(c >= '0' && c <= '9'){x = (x*10) + (c^48);c = getchar();}
	return x * f;
}
TT void Put1(T x)
{
	if(x > 9) Put1(x/10);
	putchar(x%10^48);
}
TT void Put(T x,char c = -1)
{
	if(x < 0) putchar('-'),x = -x;
	Put1(x); if(c >= 0) putchar(c);
}
TT T Max(T x,T y){return x > y ? x : y;}
TT T Min(T x,T y){return x < y ? x : y;}
TT T Abs(T x){return x < 0 ? -x : x;}

LL Get(desk stu,desk des)//student & desk
{
	LL ret = 0;
	if(stu.l < des.l) ret += des.l - stu.l;
	if(stu.l > des.r) ret += stu.l - des.r;
	if(stu.r < des.l) ret += des.l - stu.r;
	if(stu.r > des.r) ret += stu.r - des.r;
	return ret;
}
LL solve(int sl,int sr,int dl,int dr)//student lr,desk lr,好像是个暴力吧？ LOJ有78 (Ofast)
{
	if(sl > sr) return 0;
	LL ret = 0;
	if(dl == dr)
	{
		for(int i = 1;i <= m;++ i)
			for(int j = sl;j <= sr;++ j)
				ret += Get(a[i][j],d[dl]);
		return ret;
	}
	int mid = (sl+sr) >> 1,B = dl; LL MIN = INF;
	for(int i = dl;i <= dr;++ i)
	{
		LL cur = 0;
		for(int j = 1;j <= m;++ j) cur += Get(a[j][mid],d[i]);
		if(cur < MIN) B = i,MIN = cur;
	}
	return MIN+solve(sl,mid-1,dl,B)+solve(mid+1,sr,B,dr);
}

int main()
{
//	freopen("party.in","r",stdin);
//	freopen("party.out","w",stdout);
	m = Read(); n = Read(); k = Read();
	for(int i = 1;i <= k;++ i) d[i].l = Read(),d[i].r = Read();
	sort(d+1,d+k+1);
	int R = 0;
	for(int i = 1;i <= k;++ i)
	{
		if(R >= d[i].r) tag[i] = 1;
		R = Max(R,d[i].r);
	}
	int kk = k; k = 0;
	for(int i = 1;i <= kk;++ i) if(!tag[i]) d[++k] = d[i];
	for(int i = 1;i <= m;++ i)
	{
		for(int j = 0;j < (n<<1);++ j) o[j] = Read();
		sort(o,o+(n<<1));
		for(int j = 0;j < (n<<1);j += 2) a[i].emplace_back(desk{o[j],o[j+1]});
	}
	Put(solve(0,n-1,1,k),'
');
	return 0;
}

精细的实现

//12252024832524
#include <bits/stdc++.h>
#define TT template<typename T>
using namespace std;

typedef long long LL;
const int MAXN = 200005;
const LL INF = 1ll << 60;
int m,n,k;
int o[MAXN << 1]; 
bool tag[MAXN];
struct desk
{
	int l,r;
	bool operator < (const desk &px)const{
		if(l^px.l) return l < px.l;
		return r > px.r;
	}
}d[MAXN];
vector<desk> a[MAXN];
vector<int> fs[MAXN];//final students list

LL Read()
{
	LL x = 0,f = 1; char c = getchar();
	while(c > '9' || c < '0'){if(c == '-')f = -1;c = getchar();}
	while(c >= '0' && c <= '9'){x = (x*10) + (c^48);c = getchar();}
	return x * f;
}
TT void Put1(T x)
{
	if(x > 9) Put1(x/10);
	putchar(x%10^48);
}
TT void Put(T x,char c = -1)
{
	if(x < 0) putchar('-'),x = -x;
	Put1(x); if(c >= 0) putchar(c);
}
TT T Max(T x,T y){return x > y ? x : y;}
TT T Min(T x,T y){return x < y ? x : y;}
TT T Abs(T x){return x < 0 ? -x : x;}

LL Get(int h,desk des)//student & desk
{
	if(h < des.l) return des.l - h;
	if(h > des.r) return h - des.r;
	return 0;
}
LL pre[MAXN << 1];
LL Query(int l,int r)
{
	if(l > r) return 0;
	LL ret = pre[r];
	if(!l) return ret;
	return ret - pre[l-1];
}
LL solve(int sl,int sr,int dl,int dr)//student lr,desk lr,O((k+nm)log_2n)
{
	if(sl > sr) return 0;
	LL cur = 0,MIN = INF;
	int lid = 0,rid = 0,B = dl,mid = (sl+sr) >> 1;
	for(int i = 0;i < (m<<1);++ i) pre[i] = ((i ? pre[i-1] : 0) + fs[mid][i]);
	for(int i = dl;i <= dr;++ i)
	{
		while(lid < (m<<1) && fs[mid][lid] < d[i].l) ++lid;
		while(rid < (m<<1) && fs[mid][rid] <= d[i].r) ++rid;
		cur = 1ll * d[i].l * lid - Query(0,lid-1) + Query(rid,(m<<1)-1) - 1ll * ((m<<1)-rid) * d[i].r;
		if(cur < MIN) MIN = cur,B = i;
	}
	return MIN+solve(sl,mid-1,dl,B)+solve(mid+1,sr,B,dr);
}

int main()
{
//	freopen("party.in","r",stdin);
//	freopen("party.out","w",stdout);
	m = Read(); n = Read(); k = Read();
	for(int i = 1;i <= k;++ i) d[i].l = Read(),d[i].r = Read();
	sort(d+1,d+k+1);
	int R = 0;
	for(int i = 1;i <= k;++ i)
	{
		if(R >= d[i].r) tag[i] = 1;
		R = Max(R,d[i].r);
	}
	int kk = k; k = 0;
	for(int i = 1;i <= kk;++ i) if(!tag[i]) d[++k] = d[i];
	for(int i = 1;i <= m;++ i)
	{
		for(int j = 0;j < (n<<1);++ j) o[j] = Read();
		sort(o,o+(n<<1));
		for(int j = 0;j < (n<<1);j += 2) fs[j >> 1].emplace_back(o[j]),fs[j >> 1].emplace_back(o[j+1]);
	}
	for(int i = 0;i < n;++ i) sort(fs[i].begin(),fs[i].end());
	Put(solve(0,n-1,1,k),'
');
	return 0;
}