# Triplets

### Problem Statement :

```There is an integer array d which does not contain more than two elements of the same value. How many distinct ascending triples (d[i],< d[j] < d[k] , i < j < k ) are present?

Input format

The first line contains an integer, N, denoting the number of elements in the array. This is followed by a single line, containing N  space-separated integers. Please note that there are no leading spaces before the first number, and there are no trailing spaces after the last number.

Output format:

A single integer that denotes the number of distinct ascending triplets present in the array.

Constraints:

N  <= 10^5

Every element of the array is present at most twice.
Every element of the array is a 32-bit non-negative integer.```

### Solution :

```                            ```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 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) {
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 {
out = new PrintWriter(System.out);
eat("");

solve();

out.close();
}

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

String next() throws IOException {
while (!st.hasMoreTokens()) {
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 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)
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)
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

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

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:
# 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)

# print(less_than(6, tree_1))

```

## Castle on the Grid

You are given a square grid with some cells open (.) and some blocked (X). Your playing piece can move along any row or column until it reaches the edge of the grid or a blocked cell. Given a grid, a start and a goal, determine the minmum number of moves to get to the goal. Function Description Complete the minimumMoves function in the editor. minimumMoves has the following parameter(s):

## Down to Zero II

You are given Q queries. Each query consists of a single number N. You can perform any of the 2 operations N on in each move: 1: If we take 2 integers a and b where , N = a * b , then we can change N = max( a, b ) 2: Decrease the value of N by 1. Determine the minimum number of moves required to reduce the value of N to 0. Input Format The first line contains the integer Q.

## Truck Tour

Suppose there is a circle. There are N petrol pumps on that circle. Petrol pumps are numbered 0 to (N-1) (both inclusive). You have two pieces of information corresponding to each of the petrol pump: (1) the amount of petrol that particular petrol pump will give, and (2) the distance from that petrol pump to the next petrol pump. Initially, you have a tank of infinite capacity carrying no petr

## Queries with Fixed Length

Consider an -integer sequence, . We perform a query on by using an integer, , to calculate the result of the following expression: In other words, if we let , then you need to calculate . Given and queries, return a list of answers to each query. Example The first query uses all of the subarrays of length : . The maxima of the subarrays are . The minimum of these is . The secon

## QHEAP1

This question is designed to help you get a better understanding of basic heap operations. You will be given queries of types: " 1 v " - Add an element to the heap. " 2 v " - Delete the element from the heap. "3" - Print the minimum of all the elements in the heap. NOTE: It is guaranteed that the element to be deleted will be there in the heap. Also, at any instant, only distinct element