Watan And Dominoes Solved( number of numbers < than ith element )

Watan And Dominoes

All submissions for this problem are available.

Watan likes the game of Dominoes where a series of rectangular wooden pieces are placed on a line, hitting the right piece makes the rest of the pieces fall. In original version of the game, all the pieces are identical. But unfortunately the pieces that Watan has, have different heights. So, whether the pieces will fall or not becomes more difficult to predict. Watan is good at mathematics. He devised his own formula to predict the outcome. In his formula, he requires to find for each pieces, how many pieces appearing before it are smaller than it. This part is tedious and he doesn't want to spend a lot of time on it. So he comes to you to write a program to find this for him.

Input

The first line of the input contains a single integer T denoting the number of test cases. Each test case T has two lines. First line contains a single integer N denoting number of pieces present. Next line contains N space separated integers A_i denoting height of each piece.

Output

For each test case, output N space separated integers B_i where B_i is the number of elements A_j (1<=j<=i-1) which are less than A_i.

Constraints

• 1 <= T <= 1000
• 1 <= A_i <= 10^6
• 1 <= N <= 10^6

Sample Cases

Input
1
5
1 2 3 4 5

Output
0 1 2 3 4

------------------------------------------------------------------editorial----------------------------------------------------------------

  start processing from the first element to last update any number , and query  from 0 to till the number

-----------------------------------------------------------------------code-------------------------------------------------------------------------

#include<bits/stdc++.h>

using namespace std;

typedef int  lli;

int v[1000010];

lli seg[10000000];

int ans[10000000];

void update(int idx,int start,int end,int ups,int upe,lli val)

 {

  if(start>end || upe<start || ups>end) return ;

  else if(start==end && start==ups)

   {

   seg[idx]+=val;

   return ;

 }

 int mid=(start+end)/2;

 

 update(2*idx,start,mid,ups,ups,val);

 update(2*idx+1,mid+1,end,ups,upe,val);

 seg[idx]=seg[2*idx]+seg[2*idx+1];

 

 }

 lli  qry(int idx,int start,int end,int qs,int qe)

 {

  if(start>end || qe<start || qs>end) return 0;

 

  else if(start>=qs && end<=qe)

   {

   

   return seg[idx];

 }

 int mid=(start+end)/2;

lli q1= qry(2*idx,start,mid,qs,qe);

lli q2= qry(2*idx+1,mid+1,end,qs,qe);

  return (q1+q2);

  

 }

int main()

 {

  int t;

  cin>>t;

  while(t--)

   {

    memset(seg,0,sizeof seg);

   int n;

  cin>>n;

  int val=0;

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

    {

  int a; 

  scanf("%d",&v[i]);

  val=max(val,v[i]);

   }

   

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

  {

       int num=v[i];

       int count =qry(1,0,val,0,num-1);

       ans[i]=count;

       update(1,0,val,num,num,1);

  }

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

  printf("%d ",ans[i]);

   printf("\n");

    }

 }