题解：P11847 [USACO25FEB] True or False Test P

· · 题解

Elsie 改一道题目的答案的贡献是把得分减去 a_i+b_i，所以我们先将所有题目按照 a_i+b_i 排序。

那么相当于 Bessie 选择一些点，使得前 k 个造成 -b_i 贡献，后面的造成 a_i 的贡献。

对于每一组询问，我们考虑枚举一个分界点 x，就相当于在分界点前选 k 个 -b_i,分界点后选任意个 a_i。

那么分界点之后的显然全选，分界点之前显然选择最大的 k 个 -b_i。

那么对于每个询问，枚举分界点，用主席树求出前缀前 k 大即可。

这样复杂度是 O(qn\log n)，能过 35 分。

正解：可以通过感受（或者打表）的方式发现最优的分界点 x 随 k 增大而单调增大。

证明：考虑 k,k+1 的最优分界点 x_k,x_{k+1}，显然x_k 和 x_{k+1} 这两个点一定会在对应方案被选。

如果 x_k>x_{k+1}，考虑 k+1 选择方案中分界点前的任意一个被选择的点 i，考虑把它替换成 x_k，根据定义显然都不会更优，那么你把 k 的最优方案中的 x_k 替换成 k+1 方案中的任意一个没有在 k 的最优方案中出现过的数一定会更优（显然一定会有一个位置没有出现过），那么新的对 k 的最优方案的决策点就是 x_{k+1} 了。

也就是说有决策单调性，直接套个分治板子就行了，时间复杂度 O(q\log^2n)。

code

#include<bits/stdc++.h>
using namespace std;
#define usefile(p) freopen(#p".in","r",stdin),freopen(#p".out","w",stdout);
#define fo(i,a,b) for(int i=(a);i<=(b);++i)
#define fu(i,a,b) for(int i=(a);i<(b);++i)
#define fd(i,a,b) for(int i=(a);i>=(b);--i)
#define mk make_pair
#define ll long long
#define eb emplace_back
#define pii pair<int,int>
const int N=2e5+5;
const ll inf=1e16;
int n,Q,v[N],rt[N],cnt;
ll Ans[N],s[N];
struct pro{int a,b;};
pro c[N],d[N],q[N];
inline bool cmp(pro u,pro v){return u.a+u.b>v.a+v.b;}
inline bool cmp2(pro u,pro v){return u.a<v.a;}
struct nd{int ls,rs,sum;ll val;};
nd t[N<<5];
inline void pushup(int o)
{
    t[o].sum=t[t[o].ls].sum+t[t[o].rs].sum;
    t[o].val=t[t[o].ls].val+t[t[o].rs].val;
}
inline int newnd(int o){++cnt;t[cnt]=t[o];return cnt;}
int modify(int o,int l,int r,int x)
{
    o=newnd(o);
    if(l==r){++t[o].sum;t[o].val+=d[l].a;return o;}
    int mid=l+r>>1;
    if(x<=mid)t[o].ls=modify(t[o].ls,l,mid,x);
    else t[o].rs=modify(t[o].rs,mid+1,r,x);
    pushup(o);return o;
}
ll query(int o,int l,int r,int k)
{
    if(l==r)return t[o].val;
    int mid=l+r>>1;
    if(t[t[o].ls].sum>=k)return query(t[o].ls,l,mid,k);
    else return t[t[o].ls].val+query(t[o].rs,mid+1,r,k-t[t[o].ls].sum); 
}
void solve(int l,int r,int L,int R)
{
    if(l>r)return ;
    int mid=l+r>>1,le=max(L,q[mid].a),p=0;
    int id=q[mid].b;
    fo(i,le,R)
    {
        ll val=s[n]-s[i]-query(rt[i],1,n,q[mid].a);
        if(val>Ans[id])Ans[id]=val,p=i;
    }
    solve(l,mid-1,L,p);solve(mid+1,r,p,R);
}
int main()
{
    scanf("%d%d",&n,&Q);
    fo(i,1,n)scanf("%d%d",&c[i].a,&c[i].b);
    sort(c+1,c+n+1,cmp);
    fo(i,1,Q)scanf("%d",&q[i].a),q[i].b=i,Ans[i]=-inf;
    fo(i,1,n)d[i].a=c[i].b,d[i].b=i,s[i]=s[i-1]+c[i].a;
    sort(d+1,d+n+1,cmp2);sort(q+1,q+Q+1,cmp2);
    fo(i,1,n)c[d[i].b].b=i;
    fo(i,1,n)rt[i]=modify(rt[i-1],1,n,c[i].b);
    solve(1,Q,0,n);
    fo(i,1,Q)printf("%lld\n",Ans[i]);
    return 0;
}