题解：P11847 [USACO25FEB] True or False Test P
Purslane
·
·
题解
Solution
如果 Bessie 选定了某些考试（k 给定），Elsie 如何让 Bessie 获得最低的成绩呢？
显然 Elsie 会选择 a_i+b_i 最大的 k 场考试。
所以，我们可以将考试按照 a_i+b_i 排序。Bessie 要选出若干场考试，在前 k 场获得 -b_i 的分数，后若干场获得 a_i 的分数。
贪心的，后若干场的 a_i 应该全选，而前若干场的 b_i 应该选前 k 小的。
因此你可以得到一个 O(n \log n) 单组询问的方法——从前往后扫描，维护前缀的 b 的前 k 小的和。
当然你也可以 DP。设 dp_{i,j} 为，考虑了位置 \ge i 的数，选了 j 场考试给 Elsie 攻击你能获得的最大代价。
转移是容易的：
显然 $dp_{i,*}$ 是单调递减的。看起来不太好优化，那就上 Slope Tricks！
打表发现，$dp_{i,*}$ 的差分数组是单峰的。虽然没有凹凸性，但是总比啥都没有强。画一个示意图：
先考虑优化 $dp_{i,j} = \max\{dp_{i+1,j},dp_{i+1,j-1}-b_i\}$。
这相当于什么呢？如果 $dp_{i+1,j-1} - dp_{i+1,j} \ge b_i$，就从 $(i+1,j-1)$ 转移到 $(i,j)$；否则从 $(i+1,j)$ 转移到 $(i,j)$。
发现这样的 $j$ 是一段前缀和后缀。所以我们使用 multiset 维护两个部分的差分数组，容易发现每次只有 $O(1)$ 个位置的差分发生变化（这里是 slope tricks 的基础操作，不赘述）。
使用数学归纳法也确实能够证明，差分数组一直是单峰的。
注意修改两个 multiset 的时候，如果修改的是最靠近拐点的差分，要注意判断单调性是否仍然成立，要将 $O(1)$ 个元素所在的集合进行微调。
细节有点多，场上调了整整一个小时。 /tuu
```cpp
#include<bits/stdc++.h>
#define int long long
#define ffor(i,a,b) for(int i=(a);i<=(b);i++)
#define roff(i,a,b) for(int i=(a);i>=(b);i--)
using namespace std;
const int MAXN=2e5+10;
int n,q,a[MAXN],b[MAXN],suf[MAXN],ans[MAXN];
signed main() {
ios::sync_with_stdio(false),cin.tie(0),cout.tie(0);
cin>>n>>q;
vector<pair<int,int>> vc;
ffor(i,1,n) cin>>a[i]>>b[i],vc.push_back({a[i],b[i]});
sort(vc.begin(),vc.end(),[](pair<int,int> A,pair<int,int> B) {return A.first+A.second>B.first+B.second;});
ffor(i,1,n) a[i]=vc[i-1].first,b[i]=vc[i-1].second;
multiset<int> d1,d2;
d1.insert(a[n]+b[n]);
roff(i,n-1,1) {
int flg=0;
if(*d1.begin()<b[i]) flg=1;
if(!flg) {
d1.insert(a[i]+b[i]);
continue ;
}
flg=0;
if(*(--d1.end())>b[i]) flg=1;
if(!d2.empty()&&*(--d2.end())>b[i]) flg=1;
if(!flg) {
int m=*(--d1.end());
d1.erase(--d1.end());
d1.insert(m+a[i]);
d2.insert(b[i]);
if(*d2.begin()<*d1.begin()) d1.insert(*d2.begin()),d2.erase(d2.begin());
continue ;
}
if(*(--d1.end())<=b[i]) {
d2.insert(b[i]);
int m=*(--d1.end());
d1.erase(--d1.end());
d1.insert(m+a[i]);
if(*d2.begin()<*d1.begin()) d1.insert(*d2.begin()),d2.erase(d2.begin());
continue ;
}
auto it=d1.upper_bound(b[i]);
int c=*prev(it),ov=*it;
d1.erase(prev(it)),d1.insert(c+ov-b[i]),d1.erase(d1.find(ov)),d1.insert(a[i]+b[i]),d2.insert(b[i]);
if(*d2.begin()<*d1.begin()) d1.insert(*d2.begin()),d2.erase(d2.begin());
}
int tot=0;
ffor(i,1,n) tot+=a[i];
ffor(i,0,n) {
ans[i]=tot;
if(!d1.empty()) tot-=*(--d1.end()),d1.erase(--d1.end());
else if(!d2.empty()) tot-=*(d2.begin()),d2.erase(d2.begin());
}
ffor(i,1,q) {
int k;
cin>>k;
cout<<ans[k]<<'\n';
}
return 0;
}
```