LA 4329: Ping Pong

ACM-ICPC Live Archive 4329: Ping Pong

My Problem Version

Given N (3 ≤ N ≤ 20000) distinct numbers, a₁ , a₂ ,  a₃ ... a_N, each not more than 100000, how many ways can we select a pair of three numbers, a_x , a_y , and a_z , such that a_x< a_y < a_z  and x < y < z?
Note: x=1, y=2, z=3 is different from x=2, y=1, z=3.

The Algorithm

We can take a hint from "... how many ways can we select ..." that this would involve prefix sums. Since we are asked to select the way to make 3 things, we would need to make 3 prefix sum arrays... unless we try to consider the problem from a_y 's point of view: the amount of ways to select a number to "its" left and smaller times the number of ways to select a number to "its" right and bigger is the amount of ways to create a pair where "it" is  a_y. We do this for every possible value of y.
Wait a minute... smaller and to its left ... larger and to its right ... isn't this inversion pairs? We can use a BIT to solve this, keeping track of the amount of numbers to an index's left that is smaller than its value and the amount of numbers to its right that is smaller than its value.
Then, we can calculate the total by using (left-hand smaller amount) times (inversion of right hand smaller amount).
But, we forgot about the note! It can quite as well be that z and x are switched. So, we also add (inversion of left-hand smaller amount) times (right hand smaller amount).

My Code

#include <algorithm>

#include <cstdio>

#include <cstring>

#define MX 20005

using namespace std;

using ll = long long int;

ll BIT[MX], RR[MX], LL[MX], inp[MX], inp2[MX];

int comp[MX], n;

inline int lsb(int i){ return i&(-i); }

ll getsum(int ind)

{

ll tot=0;

while(ind>0)

{

tot += BIT[ind];

ind -= lsb(ind);

}

return tot;

}

void update(int ind)

{

while(ind<=n)

{

BIT[ind]++;

ind += lsb(ind);

}

}

ll genfb()

{

for(int i=1;i<=n;i++)

{

LL[i] = getsum(comp[i]);

update(comp[i]);

}

memset(BIT,0,sizeof BIT);

for(int i=n;i>0;i--)

{

RR[i] = getsum(comp[i]);

update(comp[i]);

}

ll tot = 0;

for(int i=1;i<=n;i++)

{

tot += LL[i]*(n-i-RR[i]);

tot += (i-LL[i]-1)*RR[i];

}

return tot;

}

int main()

{

int tcs; scanf("%d", &tcs);

for(int tcn=0;tcn<tcs;tcn++)

{

scanf("%d",&n);

memset(BIT,0,sizeof BIT);

memset(RR,0,sizeof RR);

memset(LL,0,sizeof LL);

memset(inp,0,sizeof inp);

memset(inp2,0,sizeof inp2);

memset(comp,0,sizeof comp);

for(int i=0;i<n;i++)

{

scanf("%lld",&inp[i]);

inp2[i] = inp[i];

}

sort(inp2,inp2+n);

for(int i=1;i<=n;i++)

comp[i] = lower_bound(inp2,inp2+n,inp[i-1])-inp2+1;

printf("%lld\n",genfb());

}

}