好好玩的题。
思路
对于前 \(K\) 小方案问题。
我们可以考虑当前方案对下一个方案的转移。
重点在于转移的最优化与不重不漏。
只有一种种类
假设没有 \(l,r\) 的限制怎么做。
我们不妨把所有价格排序。
发现一种状态转移到另一种状态，无异与将其中已选择的一个物品不选，选择他后面的一个物品。
这样可以得到一个更劣的状态。
考虑使用 \((now, nxt, val)\) 来表示当前状态。
\(now\) 表示我们当前准备不选的物品。
\(nxt\) 表示 \(now\) 后面第一个选择的物品。
那么有转移：
\[(now,nxt,val)\rightarrow(now+1,nxt,val-c_{now}+c_{now+1}) \]当然，这样的转移没有包括所有的物品。
那么我们不妨在加入一维。
考虑使用 \((pre, now, nxt, val)\) 来表示当前状态。
\(pre\) 表示 \(now\) 前面有几个元素，由于 \(pre\) 个元素都没有位移过，所以它必然是一段 \(1\sim pre\) 的前缀。
那么有转移：
\[(pre,now,nxt,val)\rightarrow(pre,now+1,nxt,val-c_{now}+c_{now+1}) \]\[(pre,now,nxt,val)\rightarrow(pre-1,pre,now,val) \]发现第二种转移与当前的方案是同一种，所以我们可以钦定每一次转移必须位移一次。
那么有：
\[(pre,now,nxt,val)\rightarrow(pre-1,pre+1,now,val-c_{pre}+c_{pre+1}) \]初始状态为：
\[(i,i,n+1,sum_i) \]至于 \(l,r\) 的限制也变得比较简单。
\[i\in[l,r],(i,i,n+1,sum_i) \]有多种种类
可以发现，每一种种类之前是比较独立的。
所以我们同样可以用之前的方法求出单种种类的第 \(k\) 小。
设 \(kth_j(i)\) 为第 \(j\) 种颜色中，第 \(i\) 小的方案。
使用同样的状态维护外层的贪心。
\((now,k,val)\) 表示当前在第 \(now\) 个颜色，使用的是第 \(k\) 小方案。
那么有转移：
\[(now,k,val)\rightarrow(now,k+1,val-kth_{now}(k)+kth_{now}(k+1)) \]\[(now,k,val)\rightarrow(now+1,2,val-kth_{now+1}(1)+kth_{now+1}(2)) \]这样的转移还存在一点瑕疵。
我们有可能会跳过一些颜色。
那么对于 \(k=2,now\not = 1\)，我们有转移：
\[(now,2,val)\rightarrow(now+1,2,val-(kth_{now+1}(1)-kth_{now+1}(2))+(kth_{now}(1)-kth_{now}(2))) \]这样，我们把所有颜色按 \(kth(1)-kth(2)\) 从大到小排序，就可以正常转移了。
初始状态 \((1,1,\sum kth(1))\)。
时间复杂度：\(O(k\log k)\)。
Code
#include <bits/stdc++.h>
using namespace std;
#define x first
#define y second
#define int long long
#define mp(x, y) make_pair(x, y)
#define eb(...) emplace_back(__VA_ARGS__)
#define fro(i, x, y) for(int i = (x); i <= (y); i++)
#define pre(i, x, y) for(int i = (x); i >= (y); i--)
inline void JYFILE19();
typedef long long i64;
typedef pair<int, int> PII;
bool ST;
const int N = 1e6 + 10;
const int mod = 998244353;
int n, m, k, ct, ans, a[N], c[N], id[N];
vector<int> d[N], g[N];
struct Node {
int pr, cr, nt, vl;
inline bool operator<(const Node &tmp) const {
return vl > tmp.vl;
}
};
priority_queue<Node> q[N], f;
inline int get(int p) {
if(q[p].empty()) return -1;
auto x = q[p].top(); q[p].pop();
if(x.cr && x.cr + 1 < x.nt)
q[p].push({x.pr, x.cr + 1, x.nt, x.vl - d[p][x.cr] + d[p][x.cr + 1]});
if(x.pr && x.pr + 1 < x.cr)
q[p].push({x.pr - 1, x.pr + 1, x.cr, x.vl - d[p][x.pr] + d[p][x.pr + 1]});
return x.vl;
}
inline int ask(int p, int k) {
while(k > g[p].size()) {
int v = get(p); g[p].eb(v);
}
return g[p][k - 1];
}
inline int ask() {
if(f.empty()) return -1;
auto x = f.top(); f.pop();
if(x.cr + 1 == 2 && ask(id[x.pr], 2)) {
f.push({x.pr, x.cr + 1, ask(id[x.pr], 2), x.vl - x.nt + ask(id[x.pr], 2)});
}
if(x.cr + 1 != 2) {
int v = ask(id[x.pr], x.cr + 1);
if(v != -1) {
f.push({x.pr, x.cr + 1, v, x.vl - x.nt + v});
}
}
if(x.pr + 1 <= ct) {
f.push({x.pr + 1, 2, ask(id[x.pr + 1], 2), x.vl - ask(id[x.pr + 1], 1) + ask(id[x.pr + 1], 2)});
}
if(x.pr != 1 && x.cr == 2 && x.pr + 1 <= ct) {
f.push({x.pr + 1, 2, ask(id[x.pr + 1], 2), x.vl - ask(id[x.pr + 1], 1) + ask(id[x.pr + 1], 2) + ask(id[x.pr], 1) - ask(id[x.pr], 2)});
}
return x.vl;
}
signed main() {
JYFILE19();
cin >> n >> m >> k;
fro(i, 1, n) cin >> a[i] >> c[i];
fro(i, 1, n) d[a[i]].eb(c[i]);
fro(i, 1, m) {
d[i].eb(0);
sort(d[i].begin(), d[i].end());
int x, y, sm = 0, len = d[i].size();
cin >> x >> y;
x = min(x, len);
y = min(y, len - 1);
fro(j, 1, x - 1)
sm += d[i][j];
fro(j, x, y) {
sm += d[i][j];
q[i].push({j - 1, j, len, sm});
}
}
int res = 0;
fro(i, 1, m) {
if(ask(i, 1) == -1) {
fro(i, 1, k) {
cout << -1 << "\n";
}
return 0;
}
if(ask(i, 2) != -1) {
id[++ct] = i, res += ask(i, 1);
}
else {
ans += ask(i, 1);
}
}
if(ct == 0) {
cout << ans << "\n";
fro(i, 2, k) {
cout << -1 << "\n";
}
return 0;
}
sort(id + 1, id + ct + 1, [&](int x, int y) {
return ask(x, 1) - ask(x, 2) > ask(y, 1) - ask(y, 2);
});
f.push({1, 1, ask(id[1], 1), res});
fro(i, 1, k) {
int x = ask();
cout << (x == -1 ? x : x + ans) << "\n";
}
return 0;
}
bool ED;
inline void JYFILE19() {
// freopen("", "r", stdin);
// freopen("", "w", stdout);
ios::sync_with_stdio(0), cin.tie(0);
double MIB = fabs((&ED-&ST)/1048576.), LIM = 500;
cerr << "MEMORY: " << MIB << endl, assert(MIB<=LIM);
}