题解 CF2053D Refined Product Optimality

· · 题解

复活后的第一篇题解和比赛。

感觉这是一个很有意思的题。

题意

有两个长度为 n 的序列 a,b。

有 q 次修改，每次修改给出两个整数 o,x：

设 p 是 b 的一种排列，在第一次修改前和每次修改后，你需要求出所有满足条件的 p 中 \prod\limits_{i=1}^n \min(a_i, p_i) 的最大值。

由于答案可能很大，所以对 998244353 取模。

分析

不难证明，最大值即为将 a,b 升序排列后所求的值。

简单证明一下，假设 a_1 < a_2, b_1 < b_2，那么 \min(a_1,b_2) \times \min(a_2,b_1) \le \min(a_1,b_1) \times \min(a_2,b_2)，所以降序排列会使答案变得更劣。

于是就可以在 O(n \log n) 的时间复杂度内求出修改前答案的值，接下来考虑修改操作。

修改只会修改一个，也只会增加 1 的值，所以对答案的影响并不会很大。

修改的时候如果要调整序列来维持单调性是一件很麻烦的事情。假设我们修改的是 a_x，只需要在排序的序列中修改最后一个值为 a_x 的位置，就不会影响其单调性。

于是求出这个位置后，可以撤销该位置对答案原有的贡献，乘上该位置的逆元，然后修改后再将贡献加入进去即可。

以上操作就可以用二分和快速幂解决，修改 b 序列的情况同理。

总体时间复杂度为 O(n \log n + q \log n)

代码

//the code is from chenjh
#include<bits/stdc++.h>
#define MAXN 200002
using namespace std;
typedef long long LL;
constexpr int mod=998244353;
int n,q;
int qpow(int a,int b=mod-2){
    int ret=1;
    for(;b;b>>=1,a=(LL)a*a%mod)if(b&1)ret=(LL)ret*a%mod;
    return ret%mod;
}
int a[MAXN],b[MAXN],c[MAXN],d[MAXN];//c,d 序列表示排序后的 a,b 序列。
void solve(){
    cin>>n>>q;
    for(int i=1;i<=n;i++) cin>>a[i],c[i]=a[i];
    for(int i=1;i<=n;i++) cin>>b[i],d[i]=b[i];
    sort(c+1,c+n+1),sort(d+1,d+n+1);
    int ans=1;
    for(int i=1;i<=n;i++) ans=(LL)ans*min(c[i],d[i])%mod;
    cout<<ans<<' ';
    for(int o,x,p;q--;){
        cin>>o>>x;
        p=0;
        if(o==1)
            p=upper_bound(c+1,c+n+1,a[x])-c-1,//找到第一个大于 a_x 的位置的前一个，即最后一个等于 a_x 的位置。
            ans=(LL)ans*qpow(min(c[p],d[p]))%mod,//除以这个数，即乘这个数的逆元。
            ++a[x],++c[p];//对这些位置进行修改。
        else if(o==2)
            p=upper_bound(d+1,d+n+1,b[x])-d-1,//b 序列同理。
            ans=(LL)ans*qpow(min(c[p],d[p]))%mod,
            ++b[x],++d[p];
        ans=(LL)ans*min(c[p],d[p])%mod;//乘上修改后这个位置的贡献。
        cout<<ans<<' ';
    }
    cout<<'\n';
}
int main(){
    ios::sync_with_stdio(false),cin.tie(nullptr);
    int T;cin>>T;
    while(T--) solve(); 
    return 0;
}