fork download
  1. #include<bits/stdc++.h>
  2.  
  3. using namespace std;
  4. typedef long long ll;
  5. typedef pair<int , int> pi;
  6. typedef pair<double , int > dpi;
  7. typedef pair<long long , long long> pll;
  8. typedef vector<int> vi;
  9. typedef vector<ll> vll;
  10. typedef vector<pi> vpi;
  11. typedef unsigned long long ull;
  12. #define MP make_pair
  13. #define mem(a , v) memset(a , v , sizeof(a))
  14. #define all(v) ((v).begin()), ((v).end())
  15. #define sc(a) scanf("%d",&a)
  16. #define scl(a) scanf("%lld",&a)
  17. #define scd(a) scanf("%lf" , &a)
  18. #define sch(a) scanf("%c" , &a)
  19. #define blank printf("\n")
  20. #define pla printf("plapla\n")
  21. #define pb push_back
  22. #define INF 1e9
  23. #define EPS 1e-9
  24. vector<int> months = { 0, 31, 28, 31, 30, 31, 30, 31, 31, 30, 31, 30, 31 };
  25. const int MAX = 1e6+55;
  26. const int inf = 1e9+77;
  27. const int MOD = 1e9+7;
  28. const double PI = acos(-1.0);
  29. const double eps = 1e-7;
  30.  
  31. int n;
  32. pi a[MAX];
  33. int tree[4*MAX];
  34. int _left[MAX] , _right[MAX];
  35.  
  36. void update(int p , int st , int en , int loc){
  37. if(st > loc || en < loc)
  38. return;
  39. if(st == en){
  40. tree[p] = 1;
  41. return;
  42. }
  43. int md = (st+en)>>1;
  44. update(p * 2 ,st , md , loc);
  45. update(p * 2 + 1 , md + 1 ,en , loc);
  46. tree[p] = tree[p*2] + tree[p*2+1];
  47. }
  48.  
  49. int qwr(int p , int st , int en , int l , int r){
  50. if(st > r || en < l)
  51. return 0;
  52. if(st >= l && en <= r)
  53. return tree[p];
  54. int md = (st+en)>>1;
  55. return qwr(p * 2 , st , md , l , r) + qwr(p * 2 + 1 , md + 1 , en , l , r);
  56. }
  57.  
  58. int main(){
  59. //freopen("output.txt" , "w" , stdout);
  60. //freopen("input.txt" , "r" , stdin);
  61.  
  62. sc(n);
  63. for(int i = 0 ; i < n ; ++i){
  64. sc(a[i].first);
  65. a[i].second = i;
  66. }
  67. sort(a , a + n);
  68. _right[0] = 0;
  69. update(1 , 0 , n - 1 , a[0].second);
  70. for(int i = 1 ; i < n ; ++i){
  71. if(a[i].second < n - 1)
  72. _right[i] = qwr(1 , 0 , n - 1 , a[i].second + 1 , n - 1);
  73. else
  74. _right[i] = 0;
  75. update(1 , 0 , n - 1 , a[i].second);
  76. }
  77.  
  78. mem(tree , 0);
  79. reverse(a , a + n);
  80. _left[0] = 0;
  81. update(1 , 0 , n - 1 , a[0].second);
  82. for(int i = 1 ; i < n ; ++i){
  83. if(a[i].second){
  84. _left[i] = qwr(1 , 0 , n - 1 , 0 , a[i].second - 1);
  85. }
  86. else
  87. _left[i] = 0;
  88. update(1 , 0 , n - 1 , a[i].second);
  89. }
  90. reverse(_left , _left + n);
  91.  
  92. ll res = 0;
  93. for(int i = 1 ; i < n ; ++i){
  94. res += (ll)_left[i] * (ll)_right[i];
  95. }
  96. printf("%I64d" , res);
  97.  
  98.  
  99.  
  100. return 0;
  101. }
  102.  
Success #stdin #stdout 0s 46488KB
stdin
Standard input is empty
stdout
                                                               0