NC 14522 坐标离散化 + BIT

题意

传送门 NC 14522

题解

对于一个逆序对 $(a_i,a_j)$，共有 $i\times (n-j+1)$ 个子区间包含这个逆序对。参照 $BIT$ 求数组逆序对的思路，将每个点的权值赋为包含它的子区间左边界的数量，最后再乘以包含它的子区间右界的数量。考虑到数据范围较大，进行坐标离散化。

#include <bits/stdc++.h> using namespace std; #define maxn 1000005 typedef long long ll; int n, a[maxn], sa[maxn], ra[maxn]; ll bit[maxn]; bool cmp(const int &i, const int &j) { return a[i] < a[j]; } void compress(int n, int *x, int *sx, int *rx) { for (int i = 1; i <= n; i++) { rx[i] = i; } sort(rx + 1, rx + n + 1, cmp); sx[rx[1]] = 1; for (int i = 2; i <= n; i++) { int cur = rx[i], pre = rx[i - 1]; if (x[cur] == x[pre]) sx[cur] = sx[pre]; else sx[cur] = sx[pre] + 1; } } void add(int i, int x) { while (i <= n) { bit[i] += x; i += i & -i; } } ll sum(int i) { ll s = 0; while (i > 0) { s += bit[i]; i -= i & -i; } return s; } void write(__int128 n) { if (!n) putchar('0'); int i = 0, x[40]; while (n > 0) { x[i++] = n % 10; n /= 10; } while (i > 0) { putchar(x[--i] + '0'); } } int main() { scanf("%d", &n); for (int i = 1; i <= n; i++) { scanf("%d", a + i); } compress(n, a, sa, ra); __int128 res = 0; for (int i = 1; i <= n; i++) { res += (n - i + 1) * (sum(n) - sum(sa[i])); add(sa[i], i); } write(res); return 0; }