Codeforces 1637 E. best pair - Thinking

This way

The question ：

Here you are. n Number ,cnt[i] Express i Number of occurrences .
Find the largest (x+y)*(cnt[x]+cnt[y])
x It's not equal to y And give you some logarithms that you can't take .

Answer key ：

At first, I thought about the dichotomy that the number of occurrences decreases monotonically as the value increases . But this kind of situation that cannot be taken will lead to the possibility that it is not optimal , Then I can't figure out how to do dichotomy .
I can't think of another way , Enumerate by the number of occurrences , We will find that the most frequent occurrence of different kinds is $O(\sqrt{n})$ Time .
The worst case scenario would be ： appear 1 The next time is 1 individual ,2 The next time is 1 individual ,3 The next time is 1 individual … The number of cases is (1+x)*x/2<=n.
And then because we want to maximize the product , For the same number of occurrences, we just need to find the largest one . But there is a problem here, that is, there is a right that cannot be taken , So for the same number of occurrences , We still need to find the value that can be taken from high to low . Because this time complexity is independent , So the total time complexity is O(NlogN).

#include<bits/stdc++.h>
using namespace std;
#define ll long long
const int N=3e5+5;
const ll M=1e9+7;
struct node{
    
    ll val,num;
}a[N];
#define pll pair<ll,ll>
struct pair_hash{
    
    template<class T1,class T2>
    std::size_t operator()(const std::pair<T1,T2>&p)const {
    
        auto h1 = std::hash<T1>{
    }(p.first);
        auto h2 = std::hash<T2>{
    }(p.second);
        return h1*M+h2;
    }
};
unordered_map<pll,ll,pair_hash>mp;
unordered_map<ll,ll>num;
ll check(ll x,ll i){
    
    return (a[x].val+i)*(a[x].num+num[i]);
}
int main()
{
    
    int t;
    scanf("%d",&t);
    while(t--){
    
        num.clear();
        mp.clear();
        int n,k;
        ll x,y;
        scanf("%d%d",&n,&k);
        for(int i=1;i<=n;i++)scanf("%lld",&x),num[x]++;
        for(int i=1;i<=k;i++)
            scanf("%lld%lld",&x,&y),mp[{
    x,y}]=mp[{
    y,x}]=1;
        ll all=0,mx=0;
        for(auto i :num){
    
            int l=1,r=all,ans=0,mid;
            if(all){
    
                while(r>=l){
    
                    mid=l+r>>1;
                    if(!ans)ans=mid;
                    if(check(mid,i.first)>check(ans,i.first))
                        ans=mid;
                    if(check(mid,i.first)>=check(mid+1,i.first))r=mid-1;
                    else l=mid+1;
                }
                if(mp[{
    i.first,a[ans].val}]){
    
                    l=r=ans;
                    while(l&&mp[{
    i.first,a[l].val}])l--;
                    while(r<=all&&mp[{
    i.first,a[r].val}])r++;
                    if(l)mx=max(mx,check(l,i.first));
                    if(r-all-1)mx=max(mx,check(r,i.first));
                }
                else
                    mx=max(mx,check(ans,i.first));
            }

            while(all&&i.second>=a[all].num)all--;
            a[++all]={
    i.first,i.second};
        }
        printf("%lld\n",mx);
    }
    return 0;
}