Chopped Pairs#12439

Chopped Pairs (Editorial)

Problem Author:	De3b0o
Prepared by:	De3b0o
Edited by:	Hasan Saleh (MathModel)

Solution

For a fixed $i d$ , after we set $c_{i d} = a_{1}$ c_{id} = a_1, there are only two possible indices $j$ for $i = 2$ i=2, either $j = n$ j=n or $j = i d - 1$ j=id-1.

And the same goes for any $2 \leq i \leq n$ 2 \le i \le n, there can only be two possible indices $j$ that can work.

$Proof :$ for $i = 2$ i=2, if we choose any index $j > i d$ j>id the count of chopped pairs is gonna be the same, so we choose the maximum one ( $j = n$ j=n), this also applies to any index $j < i d$ j<id so we choose $j = i d - 1$ j=id-1.

The same goes for any index $i > 2$ i > 2, for any index $j > i d, c_{j} = 0$ j>id,c_j=0 the count of chopped pairs is gonna be the same so we pick the maximum one and for any index $j < i d, c_{j} = 0$ j<id,c_j=0 also.

We pick the index $j$ that minimizes the count of chopped pairs.

Let's look at four types of scenarios for any values of $i d$ and $i$ :

Scenario $1$ : It's optimal to pick $j > i d$ j>id but there are no indices $j > i d$ j>id where $c_{j} = 0$ c_j=0, so we pick $j < i d$ j<id.

Scenario $2$ : It's optimal to pick $j < i d$ j<id but there are no indices $j < i d$ j<id where $c_{j} = 0$ c_j=0, so we pick $j > i d$ j>id.

Scenario $3$ : It's optimal to pick $j > i d$ j>id and there is at least one index $j > i d$ j>id where $c_{j} = 0$ c_j=0, so we pick the maximum one.

Scenario $4$ : It's optimal to pick $j < i d$ j<id and there is at least one index $j < i d$ j<id where $c_{j} = 0$ c_j=0, so we pick the maximum one.

Let's pick $i d$ where only scenarios $3$ and $4$ happen (no scenarios $1$ and $2$ ), it's easy to see that there is only one $i d$ that satisfies this conditions, let's call it $i d x$ .

We can construct $b_{i d x}$ b_{idx} and then find its count of chopped pairs (the count of chopped pairs after constructing the array $b_{i d x}$ b_{idx} is equal to the count of inversions).

Let's see what happens if we pick $i d = i d x + 1$ id=idx+1,the last $i$ where scenario $3$ happens with $i d = i d x$ id=idx is going to become scenario $1$ .

And the same for $i d = i d x - 1$ id=idx-1, the last $i$ where scenario $4$ happens with $i d = i d x$ id=idx is going to become scenario $2$ .

Every time we shift $i d$ to the right one or to the left one, exactly one element is going to change it's place relative to others.

If we shift $i d$ to the right by one, the element in index $i d + 1$ id+1 is moving to some other index $k < i d$ k<id, if we find $k$ we can easily update the count of inversions since the only affected indices are the ones in the range $(k + 1, i d)$ (k+1,id), and the same goes for shifting $i d$ to the left by one.

We can find $k$ for all elements while constructing $b_{i d x}$ b_{idx} and then using a fenwick tree, we can solve the range queries offline with a final complexity of $O (n . lo g (n))$ O(n.\log(n)).


#include<bits/stdc++.h>
#define ll long long
#define F first
#define S second
#define in insert
#define pb push_back
#define d3 ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
#define cans cout << ans << "\n";
#define yes cout << "YES" << "\n";
#define no cout << "NO" << "\n";
#define pll pair<ll,ll>
#define lin cout << "\n";
#define mid ((l+r)/2)
#define lc (2*x)
#define rc (2*x+1)
#define double long double
 
using namespace std;

mt19937 rnd(time(0));

const ll N = 1e6+9;

ll n,a[N],ch[N],qr[N];
ll b[N],l[N],r[N];
vector<pll> v1,v2;
vector<ll> v;
set<pll> s;

void upd(ll i)
{
    while(i<=n)
    {
        b[i]++;
        i+=i&(-i);
    }
}

ll ans(ll i)
{
    ll ans = 0;
    while(i)
    {
        ans+=b[i];
        i-=i&(-i);
    }
    return ans;
}

ll g(ll l , ll r)
{
    if(l>r)
        return 0;
    return ans(r)-ans(l-1);
}

void reset()
{
    for(int i = 1 ; n>=i ; i++)
        b[i]=0;
}

ll inv()
{
    ll i = n;
    for(auto it : v2)
        a[i--]=it.F;
    for(auto it : v1)
        a[i--]=it.F;
    ll ans = 0;
    reset();
    for(int i = 1 ; n>=i ; i++)
    {
        upd(a[i]);
        ans+=g(a[i]+1,n);
    }
    return ans;
}

void solve()
{
    v1.clear();
    v2.clear();
    cin >> n;
    for(int i = 1 ; n>=i ; i++)
        cin >> a[i];
    reset();
    upd(a[1]);
    ll id = 1;
    v1.pb({a[1],1});
    for(int i = 2 ; n>=i ; i++)
    {
        ll smaller = g(1,a[i]-1);
        ll bigger = g(a[i]+1,n);
        if(smaller<bigger)
            id++,upd(a[i]),v1.pb({a[i],i});
        else
            v2.pb({a[i],i});
    }
    ll chopped = inv();
    ch[id]=chopped;
    for(int i = v2.size()-1 ; i>=0 ; i--)
    {
        l[id + (v2.size()-i)] = id-(v2[i].S-i-2);
        r[id + (v2.size()-i)] = id;
    }
    for(int i = v1.size()-1 ; i>0 ; i--)
    {
        l[v1.size() - i] = v1.size()-i+1;
        r[v1.size() - i] = n-(v1[i].S-i-1);
    }
    l[id]=1;
    r[id]=0;
    for(int i = 1 ; n>=i ; i++)
        s.in({a[i],i});
    reset();
    ll p = -1;
    v.clear();
    while(!s.empty())
    {
        auto it = --s.end();
        ll idx = it->S;
        if(it->F!=p)
        {
            p=it->F;
            for(auto it : v)
                upd(it);
            v.clear();
        }
        v.pb(idx);
        if(idx<id)
            qr[idx]=g(1,idx-1)+g(l[idx],r[idx]);
        else
            qr[idx]=-g(l[idx],r[idx]);
        s.erase(it);
    }
    for(int i = 1 ; n>=i ; i++)
        s.in({a[i],i});
    reset();
    p = -1;
    v.clear();
    while(!s.empty())
    {
        auto it = s.begin();
        ll idx = it->S;
        if(it->F!=p)
        {
            p=it->F;
            for(auto it : v)
                upd(it);
            v.clear();
        }
        v.pb(idx);
        if(idx<id)
            qr[idx]-=g(1,idx-1)+g(l[idx],r[idx]);
        else
            qr[idx]-=-g(l[idx],r[idx]);
        s.erase(it);
    }
    for(int i = 1 ; id>i ; i++)
        ch[id-i]=ch[id-i+1]+qr[i];
    for(int i = id+1 ; n>=i ; i++)
        ch[i]=ch[i-1]+qr[i];
    for(int i = 1 ; n>=i ; i++)
        cout << ch[i] << " ";
    lin
}

int main()
{
    d3
    ll T = 1;
    cin >> T;
    while(T--)
        solve();
}