P6646 [CCO 2020] Shopping Plans 做题记录

有 $n$ 个商品和 $m$ 种颜色，第 $i$ 个物品颜色为 $a_i$，价格为 $c_i$。

对于一个购买物品的方案 $S\subseteq\{1,2,3,\dots,n\}$，定义其价格为 $\sum\limits_{i\in S}a_i$。

一个方案合法当且仅当：

• 对于第 $j$ 种颜色，购买的该种颜色的商品的个数必须要在区间 $[l_j,r_j]$ 中；

对于所有合法的方案，将其按照价格升序排序后，对于 $i\in [1,k]$，求出第 $i$ 种合法方案的价格（合法方案数不足 $i$ 则输出 $-1$）。

$1\le n,m,k\le 2\times 10^5$，$1\le a_i\le m$，$1\le c_i\le 10^9$，$0\le l_i\le r_i\le n$。

对于这种题，一种思路是考虑第 $i$ 小和第 $i+1$ 小的方案间的差异，不过这种思路在本题行不通。

还有一种思路是考虑设计一种转移顺序，使得每种方案都可以被简单表示，每种方案的后继方案只有 $O(1)$ 个，转移到每种方案的路径唯一，且转移路径上方案的代价单调。这其实相当于隐式建出一个包含所有方案的 DAG，满足：

• 每个点代表一种方案，且可以用 $O(1)$ 的信息量存储；
• 入度为 $0$ 的点是最优方案 $x$；
• 每个点的出点都比它劣；
• 从 $x$ 到每个点的路径有且仅有一条；
• 每个点的出点个数只有 $O(1)$ 个；

这样就可以用优先队列来 $O(k\log k)$ 求解第 $[1,k]$ 优的方案，即每次取出优先队列中的最优方案，将其所有后继方案加入优先队列。

Part 1：$m=1,l=r$

先给 $a$ 升序排序。注意到最优方案显然是选择前 $l$ 个，次优方案则是将第 $l$ 个选择的物品往后推一位（即用 $c_{l+1}$ 替代 $c_l$）。

观察到对于一段连续的选择的 $c_{[lb,rb]}$，将 $c_{i\in [lb,rb]}$ 替换为 $c_j$（$rb<j$）显然不如将 $c_{rb}$ 替换为 $c_j$，所以得到一个方案的路径一定形如：

• 将第 $x$ 个选择的物品往后推若干位，但不能越过第 $x+1$ 个选择的物品（初始 $x=l$）；
• 令 $x\to x-1$；

不难发现，第 $i+1$ 个物品若没有往后推过，则第 $i$ 个物品无法往后推，故可以让 $x$ 减一的时候顺便将该物品往后推一位，这样就只用考虑当前物品往后推一位的情况，出点个数就对了。

则可以这样设计 DAG：

• 每个点为四元组 $(sm,p,i,rb)$，表示代价为 $sm$，当前 $x=p+1$，第 $x$ 个选择的物品是 $c_i$，第 $x+1$ 个选择的物品是 $c_{rb}$；

• 最优方案为 $(\sum_{i\le l}c_i,l-1,l,\infin)$；

• 点 $(sm,p,i,rb)$ 的出点为：

  • $(sm-c_i+c_{i+1},p,i+1,rb)$（要求 $i+1<rb$）；

  • $(sm-c_p+c_{p+1},p-1,p+1,i)$（要求 $p+1<i$）；

Part 2：$m=1,l\le r$

当 $p=i-1$，$i<r$ 且 $rb=\infin$ 时加入出点 $(sm+c_{i+1},i,i+1,\infin)$ 即可。

Part 3：All

不妨将每种颜色看成黑盒，即设 $a_{i,j}$ 表示颜色 $i$ 的第 $j$ 小方案的代价，那么状态可以看作一个长 $m$ 的序列 $b$，其代价为 $\sum\limits_{1\le i\le m}a_{i,b_i}$，最优状态为 $\{1,1,1,\dots,1\}$。不难发现可以这样设计转移使得路径唯一：

• 将 $b_x$ 加一（不能超过颜色 $x$ 的总方案数，初始 $x=1$）；
• 将 $x$ 加一；

但是这样后继状态数太多了。

注意到，将颜色按照 $a_{i,2}-a_{i,1}$ 升序排序即可避免这个问题，本质上是将一个点 $u$ 的所有出点按照代价从小到大排序后连成一条链，这样 $u$ 就只需要连代价最小的出点。

这样设计 DAG：

• 每个点为三元组 $(sm,i,ct)$，表示代价为 $sm$，当前 $x=i$，$b_x=ct$；
• 特判掉最优方案，从次优方案 $(a_{1,2}+\sum_{2\le i\le m}a_{i,1},1,2)$ 开始；
• $(sm,i,ct)$ 的出点为：
  • $(sm-a_{i,ct}+a_{i,ct+1},i,ct+1)$（要求 $a_{i,ct+1}$ 存在）；
  • $(sm-a_{i+1,1}+a_{i+1,2},i+1,2)$（要求 $i<m$）；
  • $(sm-a_{i,2}+a_{i,1}-a_{i+1,1}+a_{i+1,2},i+1,2)$（要求 $i<m$ 且 $ct=2$）；

最后一种出点相当于撤销了 $i$ 的一次操作，即通过两次实现“跳过颜色 $i$”这个操作。由于按照 $a_{i,2}-a_{i,1}$ 升序排序，故这样做是对的。

时间复杂度 $O(n\log n)$，实现起来要特判只有一种方案的颜色。

代码如下：

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

using namespace std;

typedef long long ll;

const int S=200005,inf=1e8;

int n,m,k;
vector<ll> a[S];
int lb[S],rb[S];
priority_queue<pair<ll,pair<int,pair<int,int> > > > que[S];
vector<ll> vec[S];
vector<pair<ll,int> > idx;
priority_queue<pair<ll,pair<int,int> > > q;

inline void insnxt(int id,ll pre,int p,int i,int nxt)
{
	int r=rb[id];
	auto &c=a[id];
	if(i>0&&i<c.size()&&i+1<nxt)
		que[id].emplace(-(pre-c[i-1]+c[i]),make_pair(p,make_pair(i+1,nxt)));
	if(p>0&&p+1<i)
		que[id].emplace(-(pre-c[p-1]+c[p]),make_pair(p-1,make_pair(p+1,i)));
	if(p==i-1&&i<r&&nxt==inf)
		que[id].emplace(-(pre+c[i]),make_pair(i,make_pair(i+1,inf)));
}
inline void init(int id)
{
	ll sm=0;
	for(int i=0;i<lb[id];i++) sm+=a[id][i];
	vec[id].push_back(sm);
	insnxt(id,sm,lb[id]-1,lb[id],inf);
}
inline bool getnxt(int id)
{
	if(que[id].empty()) return false;
	auto t=que[id].top();
	que[id].pop();
	vec[id].push_back(-t.first);
	insnxt(id,-t.first,t.second.first,t.second.second.first,t.second.second.second);
	return true;
}
inline ll getrk(int id,int rk)
{
	while(vec[id].size()<rk) if(!getnxt(id)) return -1;
	return vec[id][rk-1];
}

inline void insnxt(ll pre,int i,int ct)
{
	int id=idx[i].second;
	if(getrk(id,ct+1)!=-1)
		q.emplace(-(pre-getrk(id,ct)+getrk(id,ct+1)),make_pair(i,ct+1));
	if(i+1<idx.size())
		q.emplace(-(pre-getrk(idx[i+1].second,1)+getrk(idx[i+1].second,2)),make_pair(i+1,2));
	if(ct==2&&i+1<idx.size())
		q.emplace(-(pre-getrk(id,2)+getrk(id,1)-getrk(idx[i+1].second,1)+getrk(idx[i+1].second,2)),make_pair(i+1,2));
}

int main()
{
	ios::sync_with_stdio(false),cin.tie(0),cout.tie(0);
	cin>>n>>m>>k;
	for(int i=1;i<=n;i++)
	{
		int x,y;
		cin>>x>>y;
		a[x].push_back(y);
	}
	for(int i=1;i<=m;i++) cin>>lb[i]>>rb[i];
	for(int i=1;i<=m;i++) sort(a[i].begin(),a[i].end());
	for(int i=1;i<=m;i++)
	{
		// printf("[%d %d]\n",lb[i],rb[i]);
		// for(int x:a[i]) cout<<x<<' ';cout<<'\n';
		rb[i]=min(rb[i],(int)a[i].size());
		if(lb[i]>rb[i])
		{
			for(int i=1;i<=k;i++) cout<<"-1\n";
			return 0;
		}
	}
	ll sm=0;
	for(int i=1;i<=m;i++)
	{
		init(i);
		sm+=getrk(i,1);
		if(getrk(i,2)!=-1) idx.emplace_back(getrk(i,2)-getrk(i,1),i);
	}
	// for(int i=1;i<=m;i++)
	// {
		// for(int j=1;j<=10;j++) cout<<getrk(i,j)<<' ';
		// cout<<'\n';
	// }
	sort(idx.begin(),idx.end());
	if(idx.size()>0)
	{
		int id=idx[0].second;
		q.emplace(-(sm-getrk(id,1)+getrk(id,2)),make_pair(0,2));
	}
	cout<<sm<<'\n';
	for(int i=1;i<=k-1;i++)
	{
		if(q.empty()) cout<<"-1\n";
		else
		{
			auto t=q.top();
			q.pop();
			cout<<(-t.first)<<'\n';
			insnxt(-t.first,t.second.first,t.second.second);
		}
	}
	return 0;
}