[每日一题] [NC14522] 珂朵莉的数列

题目大意：
给定一个数组，有N*(N+1)/2个子序列，这些子序列总共有多少个逆序对？

对于没个arr[i] > arr[j], i < j，在总个数的贡献是(i + 1) * (N - j)。所以基本就跟算逆序对个数这个问题是一样的，无非就是在merge的时候不是算个数的总和而是算(N - j)的总和。这里我偷懒，直接用sort进行了merge时的排序，照说应该用inplace_merge或者是手写一个merge之类的。所以我的时间复杂度是O(nlog^2(n))，应该是O(nlog(n))就可以了。

然后WA了无数次，只好看看大神们的题解，原来是爆long long，所以换成了__int128就果断AC了。

//#pragma GCC optimize(2)
#include <bits/stdc++.h>
typedef __int128 ll;
inline ll kuaidu() {
  ll k = 0;
  char f = 1;
  char c = getchar();
  for (; !isdigit(c); c = getchar())
    if (c == '-') f = -1;
  for (; isdigit(c); c = getchar()) k = k * 10 + c - '0';
  return k * f;
}
char KX[100];
inline void kuaixie(ll x) { if (x == 0) return (void) (putchar('0')); ll tmp = x > 0 ? x : -x; if (x < 0) putchar('-'); int cnt = 0; while (tmp > 0) { KX[cnt++] = tmp % 10 + '0'; tmp /= 10; } while (cnt > 0) putchar(KX[--cnt]); cout<<endl; }

int N;
#define MAXN 10000005
ll a[MAXN];
int idx[MAXN];
ll ans = 0;
void helper(int l, int r) {
  if (l >= r) return;
  int m = LMID(l, r);
  helper(l, m);
  helper(m + 1, r);
  // Merge two indices.
  // For each i, want to know the sum of N - idx[j], s.t. a[idx[j]] < a[idx[i]].
  int j = m + 1;
  ll sm = 0;
  FOR(i,l,m){
    while (j <= r && a[idx[j]] < a[idx[i]]) {
      sm += N - idx[j];
      ++j;
    }
    ans += ll(idx[i] + 1) * sm;
  }
  sort(idx + l, idx + r + 1, [](int i, int j) {return a[i] < a[j];});
}
void doit() {
  ll rtn = 0;
  REP(i, N) {
    idx[i] = i;
  }
  ans = 0;
  helper(0, N - 1);
  kuaixie(ans);
}
int main(int argc, char* argv[]) {
  N = kuaidu();
  REP(i, N) {
    a[i] = kuaidu();
  }
  doit();
  return 0;
}