fork download
copy 
  1. #include<bits/stdc++.h>
  2. #define FNAME "DAYSO"
  3. #define xd '\n'
  4. const int MAXN = (int)3e5 + 1;
  5. using namespace std;
  6.  
  7. void HuuThien() {
  8.     ios_base::sync_with_stdio(0);
  9.     cin.tie(0); cout.tie(0);
  10.     if(fopen(FNAME".inp", "r")) {
  11.         freopen(FNAME".inp", "r", stdin);
  12.         freopen(FNAME".out", "w", stdout);
  13.     }
  14. }
  15.  
  16. int n;
  17. vector<int> a;
  18. long long BIT[MAXN];
  19.  
  20. void PreBuild() {
  21.     vector<int> compress(a.begin() + 1, a.end());
  22.     sort(compress.begin(), compress.end());
  23.  
  24.     for(int i = 1; i <= n ; i++) {
  25.         a[i] = lower_bound(compress.begin(), compress.end(), a[i]) - compress.begin() + 1;
  26.     }
  27. }
  28.  
  29. struct BuildBig{
  30.     vector<long long> preLeft;
  31.     vector<long long> preRight;
  32.  
  33.     void Update(int pos, int val) {
  34.         while(pos <= n) {
  35.             BIT[pos] += val;
  36.             pos += (pos & -pos);
  37.         }
  38.     }
  39.  
  40.     long long getSum(int pos) {
  41.         long long ans = 0;
  42.             while(pos >= 1) {
  43.                 ans += BIT[pos];
  44.                 pos -= (pos & -pos);
  45.             }
  46.  
  47.             return ans;
  48.         }
  49.  
  50.     long long GetBig() {
  51.         preLeft.assign(n + 1, 0);
  52.         preRight.assign(n + 1, 0);
  53.  
  54.         for(int i = 1; i <= n ; i++) {
  55.             preLeft[i] = getSum(a[i]);
  56.             Update(a[i], 1);
  57.         }
  58.  
  59.         memset(BIT, 0, sizeof(BIT));
  60.  
  61.         for(int i = n; i >= 1; i--) {
  62.             preRight[i] = getSum(a[i]);
  63.             Update(a[i], 1);
  64.         }
  65.  
  66.  
  67.         long long ans = 0;
  68.         for(int i = 1; i <= n ; i++) {
  69.             ans += 1ll * preLeft[i] * preRight[i];
  70.         }
  71.  
  72.         return ans;
  73.     }
  74. };
  75.  
  76. struct BuildSmall{
  77.     vector<long long> preLeft;
  78.     vector<long long> preRight;
  79.  
  80.     void Update(int pos, int val) {
  81.         while(pos <= n) {
  82.             BIT[pos] += val;
  83.             pos += (pos & -pos);
  84.         }
  85.     }
  86.  
  87.     long long getSum(int pos) {
  88.         long long ans = 0;
  89.         while(pos >= 1) {
  90.             ans += BIT[pos];
  91.             pos -= (pos & -pos);
  92.         }
  93.  
  94.         return ans;
  95.     }
  96.  
  97.     long long GetSmall() {
  98.         preLeft.assign(n + 1, 0);
  99.         preRight.assign(n + 1, 0);
  100.  
  101.         memset(BIT, 0, sizeof(BIT));
  102.         for(int i = 1; i <= n ; i++) {
  103.             preLeft[i] = getSum(n) - getSum(a[i] - 1);
  104.             Update(a[i], 1);
  105.         }
  106.  
  107.         memset(BIT, 0, sizeof(BIT));
  108.  
  109.         for(int i = n; i >= 1; i--) {
  110.             preRight[i] = getSum(n) - getSum(a[i] - 1);
  111.             Update(a[i], 1);
  112.         }
  113.  
  114.         long long ans = 0;
  115.         for(int i = 1; i <= n ; i++) {
  116.             ans += 1ll * preLeft[i] * preRight[i];
  117.         }
  118.  
  119.         return ans;
  120.     }
  121. };
  122.  
  123. void Init() {
  124.     cin >> n;
  125.     a.assign(n + 1, 0);
  126.  
  127.     for(int i = 1; i <= n ; i++) {
  128.         cin >> a[i];
  129.     }
  130. }
  131.  
  132. void Solve() {
  133.     PreBuild();
  134.     long long res = 0;
  135.  
  136.     BuildBig B;
  137.     BuildSmall S;
  138.  
  139.     res += B.GetBig();
  140.     res += S.GetSmall();
  141.  
  142.     vector<int> cnt(n + 1, 0);
  143.  
  144.     for(int i = 1; i <= n ; i++) cnt[a[i]]++;
  145.     for(int i = 1; i <= n ; i++) res -= 1ll * cnt[i] * (cnt[i] - 1) * (cnt[i] - 2) / 6;
  146.     cout << res;
  147. }
  148.  
  149. signed main() {
  150.     HuuThien();
  151.     Init();
  152.     Solve();
  153. }
  154.  
Success #stdin #stdout 0.01s 6048KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Standard output is empty
https://ideone.com/uHUhbM
language:
C++ (gcc 8.3)
created:
3 hours 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!