1862G - The Great Equalizer - CodeForces Solution

#pragma GCC optimize("O3,unroll-loops")
#pragma GCC target("avx2,bmi,bmi2,popcnt,lzcnt")
// #pragma GCC target("avx2,sse4.2,bmi,bmi2,popcnt,lzcnt")
#include <bits/stdc++.h>
#define ll long long
#define pb push_back
#define mod 998244353
#define fr(i, a, b) for (ll i = a; i < b; i++)
#define rev(i, a, b) for (ll i = a; i >= b; i--)
#define in(a, n) fr(i, 0, n) cin >> a[i]
#define out(a, n) fr(i, 0, n) cout << a[i] << ' '; cout<<'\n'
#define ub upper_bound
#define lb lower_bound
#define vi vector<int>
#define si set<int>
#define mii map<int,int>
#define vll vector<long long>
#define vb vector<bool>
#define vvi vector<vector<int>>
#define MAX 2e5
using namespace std;

// pair<ll,ll> modular_inverse(ll a, ll m)
// {
//     if(m==0)
//         return {1,0};

//     pair<ll,ll> x=modular_inverse(m,a%m);
//     ll b=x.first;
//     ll c=x.second;
//     return {c,b-a/m*c};
// }

// ll fact(ll x)
// {
//     ll s=1;
//     while(x)
//         s=(s*x--)%mod;
//     return s;
// }

// ll commod(ll n,ll r,ll* fac)
// {
//     ll a=fac[n];
//     ll b=bin_exp(fac[n],mod-2,mod);
//     ll c=bin_exp(fac[n],mod-2,mod);
//     return (a*b%mod)*c%mod;
// }

// ll bin_exp_rec(ll a,ll b,ll m)
// {
//     if(b==0)    return 1;
    
//     ll c=bin_exp(a,b/2,m);
//     if(b&1)     return (c*c%m)*a%m;
//     else        return c*c%m;
// }

// ll bin_exp(ll a,ll b)
// {
//     ll p=1;

//     while(b)
//     {
//         if(b&1) p=p*a%mod;
//         a=a*a%mod;
//         b>>=1;
//     }
//     return p;
// }

// void yn(bool f)
// {
//     if(f)    cout<<"Yes"<<'\n';
//     else        cout<<"No"<<'\n';
// }

// vi prime;
// void seive()
// {
//     int p[int(MAX)+5]={0};
//     p[0]=1,p[1]=1;
//     fr(i,2,int(MAX)+5)
//     {
//         if(p[i]==0)
//         {
//             prime.pb(i);
//             int j=2*i;
//             while(j<(int)MAX+5)
//             {
//                 p[j]=1;
//                 j+=i;
//             }
//         }
//     }
// }

// ll kadence(ll* a, ll n)
// {
//     ll max=a[0],sum=a[0];
//     fr(i,1,n)
//     {
//         if(sum<0)   sum=0;
//         sum+=a[i];

//         if(max<sum) max=sum;
//     }
//     return max;
// }

void solve()
{
    int n;
    cin>>n;
    int b[n];
    map<ll,ll> a,dst;
    fr(i,0,n)
    {
        int x;
        cin>>x;
        b[i]=x;
        a[x]++;
    }
    auto i=a.begin();
    dst[0]=i->second-1;
    i=next(i);
    for(;i!=a.end();i++)
    {
        dst[0]+=i->second-1;
        dst[i->first-prev(i)->first]++;
    }

    // cout<<"A : ";
    // for(auto i: a)
    //     cout<<i.first<<' '<<i.second<<'\n';
    // cout<<"D : ";
    // for(auto i: dst)
    //     cout<<i.first<<' '<<i.second<<'\n';

    ll ans=0;
    int z=n;
    ll last=0;
    for(auto i:dst)
    {
        ans+=z*(i.first-last);
        z-=i.second;
        last=i.first;
    }
    // cout<<ans<<'\n';

    int q;
    cin>>q;
    fr(i,0,q)
    {
        ll x,y;
        cin>>x>>y;
        x--;
        a[b[x]]--;
        if(!a[b[x]])
        {
            a.erase(b[x]);
            auto it=a.lower_bound(b[x]);
            if(it!=a.end())
            {
                // cout<<"HI"<<it->first<<' '<<b[x]<<'\n';
                dst[it->first-b[x]]--;
                ans-=it->first-b[x];
                auto ite=dst.lower_bound(it->first-b[x]);
                if(next(ite)==dst.end() & ite->second==0)   ans-=ite->first-prev(ite)->first;
                if(!dst[it->first-b[x]])    dst.erase(it->first-b[x]);
                // cout<<ans<<'\n';
            }
            if(it!=a.begin())
            {
                // cout<<"hi";
                auto it2=prev(it);
                dst[b[x]-it2->first]--;
                ans-=b[x]-it2->first;
                auto ite=dst.lower_bound(b[x]-it2->first);
                if(next(ite)==dst.end() & ite->second==0)   ans-=ite->first-prev(ite)->first;
                if(!dst[b[x]-it2->first])    dst.erase(b[x]-it2->first);
                // cout<<ans<<'\n';
            }
            if(it!=a.end() & it!=a.begin())
            {
                // cout<<"hel";
                dst[it->first-prev(it)->first]++;
                ans+=it->first-prev(it)->first;
                auto ite=dst.lower_bound(it->first-prev(it)->first);
                if(next(ite)==dst.end() & ite->second==1)   ans+=ite->first-prev(ite)->first;
                // cout<<ans<<'\n';
            }
        }
        else    dst[0]--;

        // cout<<"\nA : ";
        // for(auto i: a)
        //     cout<<i.first<<' '<<i.second<<'\n';
        // cout<<"D : ";
        // for(auto i: dst)
        //     cout<<i.first<<' '<<i.second<<'\n';

        b[x]=y;
        a[y]++;
        if(a[y]==1)
        {
            auto it=a.lower_bound(y);
            if(it!=a.begin())
            {
                // cout<<"HI";
                auto it2=prev(it);
                dst[y-it2->first]++;
                ans+=y-it2->first;
                auto ite=dst.lower_bound(y-it2->first);
                if(next(ite)==dst.end() & ite->second==1)   ans+=ite->first-prev(ite)->first;
                // cout<<ans<<'\n';
            }
            if(it!=--a.end())
            {
                // cout<<"hi";
                auto it2=next(it);
                dst[it2->first-y]++;
                ans+=it2->first-y;
                auto ite=dst.lower_bound(it2->first-y);
                if(next(ite)==dst.end() & ite->second==1)   ans+=ite->first-prev(ite)->first;
                // cout<<ans<<'\n';
            }
            if(it!=a.begin() & it!=--a.end())
            {
                // cout<<"hel";
                dst[next(it)->first-prev(it)->first]--;
                ans-=next(it)->first-prev(it)->first;
                auto ite=dst.lower_bound(next(it)->first-prev(it)->first);
                // cout<<ite->first<<' '<<ite->second<<'\n';
                if(next(ite)==dst.end() & ite->second==0)   ans-=ite->first-prev(ite)->first;
                if(!dst[next(it)->first-prev(it)->first])
                    dst.erase(next(it)->first-prev(it)->first);
                // cout<<ans<<'\n';
            }
        }
        else    dst[0]++;

        // cout<<"\nA : ";
        // for(auto i: a)
        //     cout<<i.first<<' '<<i.second<<'\n';
        // cout<<"D : ";
        // for(auto i: dst)
        //     cout<<i.first<<' '<<i.second<<'\n';

        // cout<<ans<<'\n';
        cout<<a.begin()->first+ans<<' ';
    }
    cout<<'\n';
}

int main()
{
    #ifndef ONLINE_JUDGE
        freopen("input.txt", "r", stdin);
        freopen("output.txt", "w", stdout);
    #endif

    ios_base::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);

    ll tc=1;
    cin >> tc;
    while (tc--)
    {
        solve();
    }
}