Triplets

                            Solution in C :

In   C++ :






#include <assert.h>
#include <ctype.h>
#include <math.h>
#include <stdio.h>
#include <stdlib.h>
#include <string.h>

#include <algorithm>
#include <bitset>
#include <deque>
#include <fstream>
#include <iostream>
#include <list>
#include <map>
#include <numeric>
#include <queue>
#include <set>
#include <stack>
#include <string>
#include <utility>
#include <vector>

using namespace std;

typedef long long int lli;
typedef pair<int, int> pii;

int gInt () {
    int i;
    scanf("%d", &i);
    return i;
}

lli gLong () {
    lli i;
    scanf("%lld", &i);
    return i;
}

double gDouble () {
    double i;
    scanf("%lf", &i);
    return i;
}

void quit () {
    fflush(stdout);
    exit(0);
}

int n;
int nums[100005];
lli bitree[100005], bidtree[100005], finals[100005];
map <int, int> numtoind;
set <int> sorted;

lli getfreq (lli * tree, int ind) {
    int curBit = 0, sum = 0;
    while (ind) {
        if (ind & (1 << curBit)) {
            sum += tree[ind];
            ind -= (1 << curBit);
        }
        curBit ++;
    }
    return sum;
}

void chgfreq (lli * tree, int ind, lli chg) {
    int curBit = 0;
    while (ind <= n) {
        if (ind & (1 << curBit)) {
            tree[ind] += chg;
            ind += (1 << curBit);
        }
        curBit ++;
    }
}

lli getpos (lli * tree, int ind) {
    return getfreq(tree, ind) - getfreq(tree, ind - 1);
}

int main (int argc, char ** argv) {
    n = gInt();
    for (int i = 0; i < n; i ++)
        sorted.insert(nums[i] = gInt());
    set <int> :: iterator it = sorted.begin();
    for (int i = 0; it != sorted.end(); i ++, it ++)
        numtoind[*it] = i + 1;
    for (int i = 0; i < n; i ++) {
        int curind = numtoind[nums[i]];
        if (!getpos(bitree, curind))
            chgfreq(bitree, curind, 1LL);
        lli newfreq = getfreq(bitree, curind - 1);
        chgfreq(bidtree, curind, newfreq - getpos(bidtree, curind));
        finals[curind] = getfreq(bidtree, curind - 1);
    }
    lli ans = 0LL;
    for (int i = 0; i <= sorted.size(); i ++)
        ans += finals[i];
    printf("%lld\n", ans);
    quit();
}








In   Java  :







import java.io.*;
import java.util.*;

public class Solution {


private StringTokenizer st;
private BufferedReader in;
private PrintWriter out;

static class Fenwik {
long[] f;

Fenwik(int n) {
f = new long[n];
}

void add(int i, long v) {
while (i < f.length) {
f[i] += v;
i = (i | (i + 1));
}
}

long get(int i) {
long ret = 0;
while (i >= 0) {
ret += f[i];
i = (i & (i + 1)) - 1;
}
return ret;
}
}

public void solve() throws IOException {
int n = nextInt();
int[] a = new int[n];
for (int i = 0; i < n; ++i) {
a[i] = nextInt();
}
int[] b = a.clone();
Arrays.sort(b);
HashMap<Integer, Integer> map = new HashMap<Integer, Integer>();
for (int i : b) {
if (!map.containsKey(i)) map.put(i, map.size());
}
Fenwik c1 = new Fenwik(map.size());
Fenwik c2 = new Fenwik(map.size());
long[] last1 = new long[map.size()];
long[] last2 = new long[map.size()];
Arrays.fill(last1, -1);
long ans = 0;
for (int i = 0; i < n; ++i) {
int x = map.get(a[i]);
if (last1[x] == -1) {
c1.add(x, 1);
c2.add(x, last1[x] = c1.get(x - 1));
ans += last2[x] = c2.get(x - 1);
} else {
c2.add(x, c1.get(x - 1) - last1[x]);
ans += c2.get(x - 1) - last2[x];
}
}
out.println(ans);
}

public void run() throws IOException {
in = new BufferedReader(new InputStreamReader(System.in));
out = new PrintWriter(System.out);
eat("");

solve();

out.close();
}

void eat(String s) {
st = new StringTokenizer(s);
}

String next() throws IOException {
while (!st.hasMoreTokens()) {
String line = in.readLine();
if (line == null) {
return null;
}
eat(line);
}
return st.nextToken();
}

int nextInt() throws IOException {
return Integer.parseInt(next());
}

long nextLong() throws IOException {
return Long.parseLong(next());
}

double nextDouble() throws IOException {
return Double.parseDouble(next());
}

public static void main(String[] args) throws 
IOException {
Locale.setDefault(Locale.US);
new Solution().run();
}

}






In   C   :









/* Enter your code here. Read input from STDIN. Print output to STDOUT */
#include<stdio.h>
#include<stdlib.h>
#define ll long long int
typedef struct _dInfo
{
unsigned int val;
int idx,sortedIdx,firstOcc,l,r,lastOcc;
}dInfo;
dInfo a[100005];
int tree[100005];
int compare(const void *a,const void *b)
{
dInfo *x1=(dInfo*)a;dInfo *x2=(dInfo*)b;
if((*x1).val<(*x2).val)return -1;
else if((*x1).val==(*x2).val && 
(*x1).idx<(*x2).idx)return -1;
return 1;
}
int compare1(const void *a,const void *b)
{
dInfo *x1=(dInfo*)a;dInfo *x2=(dInfo*)b;
if((*x1).idx<(*x2).idx)return -1;
return 1;
}
void update(int idx,int val,int maxIdx)
{
while(idx<=maxIdx)
{
tree[idx]+=val;
idx+=(idx & -idx);
}
}
int read(int idx)
{
int sum=0;
while(idx>0)
{
sum+=tree[idx];
idx-=(idx & -idx);
}
return sum;
}
int main()
{
int n,i,maxIdx;
ll triplets;
scanf("%d",&n);
for(i=0;i<n;i++)
{
scanf("%u",&a[i].val);
a[i].idx=i;
}
qsort(a,n,sizeof(dInfo),&compare);
a[0].sortedIdx=1;
a[0].firstOcc=1;
for(i=1;i<n;i++)
{
a[i].sortedIdx=(a[i].val==a[i-1].val)?
a[i-1].sortedIdx:a[i-1].sortedIdx+1;
a[i].firstOcc=(a[i].val==a[i-1].val)?0:1;
}
a[n-1].lastOcc=1;
for(i=n-2;i>=0;i--)
{
a[i].lastOcc=(a[i].val==a[i+1].val)?0:1;
}
maxIdx=a[n-1].sortedIdx;
qsort(a,n,sizeof(dInfo),&compare1);

for(i=0;i<=maxIdx;i++)
tree[i]=0;
for(i=0;i<n;i++)
{

if(a[i].sortedIdx!=1)
a[i].l=read(a[i].sortedIdx-1);
else
a[i].l=0;
if(a[i].firstOcc)
{
update(a[i].sortedIdx,1,maxIdx);

}
}
for(i=0;i<=maxIdx;i++)
tree[i]=0;
for(i=0;i<n;i++)
a[i].sortedIdx=maxIdx+1-a[i].sortedIdx;
for(i=n-1;i>=0;i--)
{
if(a[i].sortedIdx!=1)
a[i].r=read(a[i].sortedIdx-1);
else
a[i].r=0;
if(a[i].lastOcc)
update(a[i].sortedIdx,1,maxIdx);
}
qsort(a,n,sizeof(dInfo),&compare);


for(i=0,triplets=0;i<n;i++)
{
triplets=triplets+(ll)a[i].l*(ll)a[i].r;
if(a[i].val==a[i-1].val)
triplets=triplets-(ll)a[i-1].l*(ll)a[i].r;
}
printf("%lld\n",triplets);
return 0;
}








In   Python3  ;






root = 1
last_level = 262144
tree_1 = [0 for i in range(last_level*2 + 1)]
tree_2 = [0 for i in range(last_level*2 + 1)]
tri = [0 for i in range(100048)]

#zle jest, tzn kod a nie ogolnie
def less_than(x, tab):
	index = root
	sum = 0
	c_level = last_level
	while(index < x+last_level):

		if x <  c_level // 2:
			index *= 2
		else:
			index *= 2
			sum += tab[index]
			index += 1
			x -= (c_level//2)
		# print(x)
		# print(c_level)

		c_level //= 2


	return sum

def add_elem_1(x):
	tree = tree_1
	index = x + last_level
	tree[index] = 1
	index //=2

	while index > 0:
		tree[index] = tree[2*index] + tree[2*index + 1]
		index //=2

def add_elem_2(x):
	tree = tree_2
	index = x + last_level
	tree[index] = less_than(x, tree_1)
	index //=2

	while index > 0:
		tree[index] = tree[2*index] + tree[2*index + 1]
		index //=2

n = int(input())
n_l = input()
input_array = [int(x) for x in n_l.split()]

for i in input_array:
	add_elem_1(i)
	add_elem_2(i)
	# print(less_than(i, tree_2))
	# print(less_than(100, tree_1), less_than(100,tree_2))
	tri[i] = less_than(i, tree_2)

sum = 0
for i in tri:
	sum += i
print(sum)

# add_elem_1(0)
# add_elem_1(1)
# add_elem_1(3)
# add_elem_1(4)
# add_elem_1(6)
# print(less_than(6, tree_1))


# add_elem(434,2, tree_1)