题解：CF2053D Refined Product Optimality

lalaji2010 · 2024-12-29 17:27:52 · 题解

CF2053D Refined Product Optimality

分析

由于对应位置上的数取最小值相乘，那么大数配小数只会浪费大数，所以贪心，我们升序排列，令大数与大数相对应，然后就做完了第一问。

后面需要我们维护这个升序序列，由于修改是在原序列上进行，所以我们不妨再记录一下原序列的每个位置的元素，当其进行修改时，我们只需要在升序排序的序列中二分找到最后一个等于它的数然后加 1 即可。再加完之后，我们判断一下当前两个升序排列数组中修改位置的两个对应元素的最小值是否变大，若变大，记原最小值为 mne，先最小值为 mn，答案令 res 的值修改为 res \div mne \times mn 即可。由于需要取模 998244353，所以用费马小定理求逆元即可。

AC CODE

#include<bits/stdc++.h>
#define int long long
using namespace std;
const int mod=998244353;
int t;
int n,q;
int a[200005],b[200005],ae[200005],be[200005];
long long ksm(long long a,long long b){
    long long res=1;
    while(b){
        if(b&1){
            res=res*a%mod;
        }
        a=a*a%mod;
        b>>=1;
    }
    return res;
}
signed main(){
    std::ios::sync_with_stdio(false);
    std::cin.tie(nullptr); std::cout.tie(nullptr);
    cin>>t;
    while(t--){
        cin>>n>>q;
        for(int i=1;i<=n;i++){
            cin>>a[i];
            ae[i]=a[i];
        }
        for(int i=1;i<=n;i++){
            cin>>b[i];
            be[i]=b[i];
        }
        sort(a+1,a+1+n);
        sort(b+1,b+1+n);
        long long ans=1;
        for(int i=1;i<=n;i++){
            ans=ans*min(a[i],b[i])%mod;
        }
        cout<<ans<<" ";
        while(q--){
            int o,x;
            cin>>o>>x;
            if(o==1){
                int pos=upper_bound(a+1,a+1+n,ae[x])-a-1;
                int mne=min(a[pos],b[pos]);
                a[pos]++;
                ae[x]++;
                int mn=min(a[pos],b[pos]);
                //if(mne==mn) continue;
                int inv=ksm(mne,mod-2);
                ans=ans*inv%mod*mn%mod;
            }else{
                int pos=upper_bound(b+1,b+1+n,be[x])-b-1;
                int mne=min(a[pos],b[pos]);
                b[pos]++;
                be[x]++;
                int mn=min(a[pos],b[pos]);
                //if(mne==mn) continue;
                int inv=ksm(mne,mod-2);
                ans=ans*inv%mod*mn%mod;
            }
            cout<<ans<<" ";
        }
        puts("");
    }
    return 0;
}