How to Quickly Calculate the Total Absolute

for (int i = 0; i < n; ++i) {
    total += 1LL * a[i] * (2 * i - n + 1);
}

Differences Over All Pairs (Without Brute Force!)

Hey everyone!

While solving a problem recently, I found a really useful trick for calculating the sum of absolute differences between all pairs in a sorted array.

Say you have a sorted array like:

a = [1, 3, 6]

You want to compute:

|1 - 3| + |1 - 6| + |3 - 6| = 2 + 5 + 3 = 10

Just loop through the array once and compute this. Much faster than brute force!

Why This Works (Simple Explanation)

Let’s understand this in plain English — no complex math needed!

Each number in the array: - Will be subtracted from numbers after it. - Will subtract numbers before it.

So every number is: - Subtracted from n - 1 - i elements after it. - Added to i elements before it.

This means the net effect of a[i] is: ~~~~~ a[i] * (i — (n — 1 — i)) = a[i] * (2i — n + 1) ~~~~~

You just loop through the array and apply that for each element.

Example

Let’s try with a = [1, 3, 6]:

You just loop through the array and apply that for each element.

Example

Let’s try with a = [1, 3, 6]: ~~~~~ i = 0 → 1 * (20 — 3 + 1) = 1 * (-2) = -2 i = 1 → 3 * (21 — 3 + 1) = 3 * 0 = 0 i = 2 → 6 * (2*2 — 3 + 1) = 6 * 2 = 12

Sum = -2 + 0 + 12 = 10 ~~~~~

sort(a.begin(), a.end());
long long total = 0;
for (int i = 0; i < n; ++i) {
    total += 1LL * a[i] * (2 * i - n + 1);
}

How to use pairs on priority queue and custom function

Here in this blog i will take help you to how to implement priority queue on pairs using custom comparators, You will have difficult finding this on internet as it took a lot of effort to find the correct working code which works for -std=++14 compiler of g++.

typedef pair<int, int> pd;

struct myComp {
    bool operator()(
        pair<int, int> &a,
        pair<int, int> &b)
    {
        if(a.first < b.first){
            return true;
        }else if(a.first > b.first){
            return false;
        }else{
            return a.second > b.second;
        }
        return true;
    }
};

void solve(){
    // int q;
    // cin>>q;

    priority_queue<pd, vector<pd>, myComp> p1;

    int n;
    cin>>n;
    for(int i=0;i<n;i++){
        int t1;
        cin>>t1;
        p1.push({t1,i+1});
    }

    while(p1.size() > 0){
        pair<int,int> p2;
        p2 = p1.top();
        p1.pop();
        cout<<p2.first<<" "<<p2.second<<"\n";
    }

This works as you can make changes in the myComp and use it as you want over the pairs Source — https://www.geeksforgeeks.org/priority-queue-of-pairs-in-c-with-ordering-by-first-and-second-element/

Geeks for Geeks

If you want to use lower bound or upper bound on vector of pairs then you may thing something of like this

lower_bound(vp.begin(),vp.end(),5);

But this is a wrong syntax as you need to pass a pair in the third argrument.

Now if use want to search from the first value of vector of pairs or use lower bound only on the first element and vice versa so :

In lower bound you may be saerching for the first element not less than the given value the following are the code for using lower bound

In lower bound

upper_bound(vp.begin(),vp.end(),make_pair(4,numeric_limits::max()) );

In upper bound

lower_bound(vp.begin(),vp.end(),make_pair(4,numeric_limits::min()) );

Ans vice versa if you want to use lower bound on the second value

this is my post upvote will be appriciated