CF1637E Best Pair

The question ： Give you a multiple set , seek $(x+y)\times (cn{t}_x+cn{t}_y)$ The maximum of , among $x!=y$ And there are $m$ Yes $(x,y)$ You can't choose
Enumerate first $(x,y)$ yes $O(N^2)$ Of , Let's consider enumerating $(cntx,cnty)$, Because it's different $cntx$ yes $O(\sqrt{N})$ Of , Let's enumerate $(cn{t}_x,cn{t}_y)$. For the number of occurrences $cn{t}_x$ The number can be selected from large to small greedily .
Build a priority queue , initial $push(1,1)$, Express $cn{t}_x$ The sum of the largest numbers in the set $cn{t}_y$ The largest number in the set .（ This process and that contour + The process of priority queue is very similar ）, If $(1,1)$ Illegal continue to put $(1,2)and(2,1)$ Repeat this operation until the first legal , Namely $cn{t}_x$ and $cn{t}_y$ The maximum of . In this way, we can $O(N+Mlog(M))$ complete .
In fact, it feels very simple and freehand , There may be some details in writing .
D If the question is too simple, there is no water .

#include<bits/stdc++.h>
#define ll long long
using namespace std;
struct node
{
    
    int x,y;
    int val;
    bool operator<(const node &ths)const
    {
    
        return val<ths.val;
    }
};
int main()
{
    
    int T;
    scanf("%d",&T);
    while(T--)
    {
    
        int n,m;
        scanf("%d%d",&n,&m);
        vector<int>a(n+1);
        map<int,int>mp;
        for(int i=1;i<=n;i++)
        {
    
            scanf("%d",&a[i]);
            mp[a[i]]++;
        }
        set<pair<int,int>>bad;
        for(int i=1;i<=m;i++)
        {
    
            int tu,tv;
            scanf("%d%d",&tu,&tv);
            if(tu>tv)swap(tu,tv);
            bad.insert({
    tu,tv});
        }
        for(int i=1;i<=n;i++)bad.insert({
    a[i],a[i]});

        int N=sqrt(n);
        vector<pair<int,int>>huge;
        vector<vector<int>>small(N+1);
        for(auto [fi,se]:mp)
        {
    
            if(se<N)small[se].push_back(fi);
            else huge.push_back({
    fi,se});
        }
        for(int i=1;i<N;i++)sort(small[i].begin(),small[i].end(),greater<int>());
        ll ans=-1e18;
        for(int size=2;size<=2*N-2;size++)
        {
    
            for(int sizex=1;sizex<min(size,N);sizex++)
            {
    
                int sizey=size-sizex;

                if(sizey<N&&sizex<=sizey)
                {
    
                    int mark1=0,mark2=0;
                    set<pair<int,int>>vis;
                    priority_queue<node>q;
                    if(mark1<small[sizex].size()&&mark2<small[sizey].size())
                    q.push({
    mark1,mark2,small[sizex][mark1]+small[sizey][mark2]});

                    vis.insert({
    mark1,mark2});
                    while(!q.empty())
                    {
    
                         auto [x,y,val]=q.top();
                         int tx=small[sizex][x],ty=small[sizey][y];
                         if(tx>ty)swap(tx,ty);
                         if(bad.count({
    tx,ty}))
                         {
    
                            if(x+1<small[sizex].size()&&vis.count({
    x+1,y})==0)
                            {
    
                                q.push({
    x+1,y,small[sizex][x+1]+small[sizey][y]});
                                vis.insert({
    x+1,y});
                            }
                            if(y+1<small[sizey].size()&&vis.count({
    x,y+1})==0)
                            {
    
                                q.push({
    x,y+1,small[sizex][x]+small[sizey][y+1]});
                                vis.insert({
    x,y+1});
                            }
                         }
                         else
                         {
    
                            ans=max(ans,1LL*size*val);
                            break;
                         }

                         q.pop();

                    }

                }
            }
        }
        for(int i=0;i<huge.size();i++)
        {
    
            for(int j=i+1;j<huge.size();j++)
            {
    
                auto [num1,cnt1]=huge[i];
                auto [num2,cnt2]=huge[j];
                if(bad.count({
    num1,num2})==0)ans=max(ans,1LL*(1LL*num1+num2)*(1LL*cnt1+cnt2));
            }
        }
        for(int i=0;i<huge.size();i++)
        {
    
            auto [NUM,cnt]=huge[i];
            for(int j=1;j<N;j++)
            {
    
                for(auto num:small[j])
                {
    

                    if(bad.count({
    min(num,NUM),max(num,NUM)})==0)
                    {
    
                        ans=max(ans,1LL*(1LL*NUM+num)*(1LL*cnt+j));
                        break;
                    }
                }
            }
        }
        printf("%lld\n",ans);


    }
    return  0;
}