题解 CF1477E【Nezzar and Tournaments】

· · 题解

我们考虑找到一组好的排列方式。

首先考虑假如这个排列中有一段连续且属于同一个队的部分应该怎样排列。

不妨假设这段开始时，K 的值足够大，则每个位置 x_i 的贡献都是 K+x_i-z，其中 z 是这段开头前一个数。

但是现在 K 不够大。于是现在其贡献可以比 \sum K+x_i-z 更大，因为把 K 减到 0 就不会更小了。

于是我们便想让其更早被减到 0。那么把它递增排列即可。同理，b 应该递减排列。

然后考虑 a,b 间的关系。得出结论是，b 的所有元素都应该放在 a 之前——除了一个特殊的东西，即 c_1。

这需要我们写出在 c 固定时的式子：K-c_1+c_i+\max(0,c_1-K-\min\limits_{j\leq i}\{c_j\})。其中，K-c_1+c_i 是不与 0 取 \max 时的贡献，而后面的那个 \max 是取 \max 时出现的额外贡献。

可以发现 c_1 确实是在这个式子中扮演一个很重要的角色。

令 f(x) 表示选择一个 a_i=x 作为 c_1 时的答案。则有

f(x)=K+\sum\limits_{a_i\text{ except one equals to }x}\Big(K-x+a_i+\max(0,x-K-\min\{a,b\})\Big)-\sum\limits_{b_i}\Big(K-x+b_i+\max(0,x-K-b_i)\Big)\\=K+(n-1)\Big(K-x+\max(0,x-K-\min\{a,b\})\Big)+\Big(\sum a_i\Big)-x-m(K-x)-\sum\limits_{b_i}\Big(b_i+\max(0,x-K-b_i)\Big)\\=(n-m)(K-x)+(n-1)\max(0,x-K-\min\{a,b\})+\Big(\sum a_i\Big)-\Big(\sum b_i\Big)-\sum\limits\max(0,x-K-b_i)

把常数提出来。令 C=(n-m)K+\sum a_i-\sum b_i，最终得到

f(x)=(m-n)x+(n-1)\max(0,x-K-\min\{a,b\})-\sum\limits\max(0,x-K-b_i)+C

考虑把这个函数画在坐标系上：初始有一个 (m-n) 的斜率；在 K+\min 处斜率增加了 n-1（也即，变成了 m-1），然后随着 x 增加在若干个位置减少一。最大值显然发生在斜率为 0 的位置——这意味着是 b 中的次大值加 K 附近。

故可能的极值候选只有这些元素：

现在考虑 g。仍然要推一下式子：

g(x)=\sum\limits_{a_i}\Big(K-x+a_i+\max(0,x-K-\min\{a,b\})\Big)-\sum\limits_{b_i\text{ except one equals to }x}\Big(K-x+b_i+\max(0,x-K-b_i)\Big)-K \\=n\Big(K-x+\max(0,x-K-\min\{a,b\})\Big)+\Big(\sum a_i\Big)-(m-1)(K-x)-\Big(\sum\limits_{b_i}b_i\Big)+x-\sum\limits_{b_i}\max(0,x-K-b_i)-K \\=(n-m)(K-x)+n\max(0,x-K-\min\{a,b\})+\Big(\sum a_i\Big)-\Big(\sum b_i\Big)-\sum\limits\max(0,x-K-b_i) \\=(m-n)x+n\max(0,x-K-\min\{a,b\})-\sum\limits\max(0,x-K-b_i)+C

可以发现这也是类似的。只不过因为斜率是 m，进而直接采取最大值即可。

进而极值候选即为：

于是每次询问时就挑出上述 O(1) 个数进行询问即可。维护询问是简单的。

代码：

#include<bits/stdc++.h>
using namespace std;
const int V=1000000;
typedef long long ll;
int n,m,q,a[200100],b[200100];
ll C;
multiset<int>A,B;
void insertA(int x){A.insert(x),C+=x;}
void eraseA(int x){A.erase(A.find(x)),C-=x;}
#define lson x<<1
#define rson x<<1|1
#define mid ((l+r)>>1)
struct SegTree{int num;ll sum;}seg[V<<2];
void modify(int x,int l,int r,int P,int tp){
    seg[x].num+=tp,seg[x].sum+=tp*P;
    if(l!=r)P<=mid?modify(lson,l,mid,P,tp):modify(rson,mid+1,r,P,tp);
}
ll query(int x,int l,int r,int P){
    if(l>P)return 0;
    if(r<=P)return 1ll*P*seg[x].num-seg[x].sum;
    return query(lson,l,mid,P)+query(rson,mid+1,r,P);
}
int Kth(int x,int l,int r,int K){
    if(l==r)return l;
    return seg[lson].num>=K?Kth(lson,l,mid,K):Kth(rson,mid+1,r,K-seg[lson].num);
}
void insertB(int x){B.insert(x),C-=x,modify(1,0,V,x,1);}
void eraseB(int x){B.erase(B.find(x)),C+=x,modify(1,0,V,x,-1);}
ll queryA(int K,int x){
//  printf("%d %d\n",K,x);
    return 1ll*(n-m)*K+C+1ll*(m-n)*x+1ll*(n-1)*max(0,x-K-min(*A.begin(),*B.begin()))-query(1,0,V,x-K);
}
ll queryB(int K,int x){
    return 1ll*(n-m)*K+C+1ll*(m-n)*x+1ll*n*max(0,x-K-min(*A.begin(),*B.begin()))-query(1,0,V,x-K);
}
ll solve(int K){
    ll ret=max(queryA(K,*A.begin()),queryB(K,*B.begin()));
    auto it=A.lower_bound(Kth(1,0,V,m-1)+K);
    if(it!=A.end())ret=max(ret,queryA(K,*it));
    if(it!=A.begin())ret=max(ret,queryA(K,*--it));
    ret=max(ret,queryB(K,*B.rbegin()));
    return ret;
}
int main(){
    scanf("%d%d%d",&n,&m,&q);
    for(int i=1;i<=n;i++)scanf("%d",&a[i]),insertA(a[i]);
    for(int i=1;i<=m;i++)scanf("%d",&b[i]),insertB(b[i]);
    for(int i=1,tp,x;i<=q;i++){
        scanf("%d%d",&tp,&x);
        if(tp==1)eraseA(a[x]),scanf("%d",&a[x]),insertA(a[x]);
        if(tp==2)eraseB(b[x]),scanf("%d",&b[x]),insertB(b[x]);
        if(tp==3)printf("%lld\n",solve(x));
    }
    return 0;
}