fork download
copy 
  1. #include<bits/stdc++.h>
  2. using namespace std;
  3. int arr[100005];
  4. int BIT[1000005];
  5. void update(int ind,int val)
  6. {
  7. 	while(ind<=1000002)
  8. 	{
  9. 		BIT[ind]+=val;
  10. 		ind+=(ind&(-ind));
  11. 	}
  12. }
  13. int query(int ind)
  14. {
  15. 	int s=0;
  16. 	while(ind>0)
  17. 	{
  18. 		s+=BIT[ind];
  19. 		ind-=(ind&(-ind));
  20. 	}
  21. 	return s;
  22. }
  23. int main()
  24. {
  25. 	int t;
  26. 	scanf("%d",&t);
  27. 	while(t--)
  28. 	{
  29. 		memset(BIT,0,sizeof(BIT));
  30. 		int i,j;
  31. 		int n;
  32. 		scanf("%d",&n);
  33. 		for(i=1;i<=n;i++)
  34. 		scanf("%d",&arr[i]);
  35. 		long long answ=0;
  36. 		for(i=n;i>=1;i--)
  37. 		{
  38. 			answ+=query(arr[i]-1);
  39. 			update(arr[i],1);
  40. 		}
  41. 		for(i=1;i<=n;i++)
  42. 		{
  43. 			answ=answ-query(arr[i]-1)+query(1000002)-query(arr[i]);
  44. 			printf("%lld ",answ);
  45. 		}
  46. 		printf("\n");
  47. 	}
  48. }
Success #stdin #stdout 0s 7152KB
comments (?)
stdin
copy 
1
5
1 3 2 4 6
stdout
copy 
5 5 7 5 1
https://ideone.com/GJE2kC
1
5
1 3 2 4 6
language:
C++14 (gcc 8.3)
created:
6 years ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!