RT，树状数组思博题，类似于UVa1428
不过数据只有5e4，分块水水就过了
码量还要大一些……
我到底图个啥
#include <bits/stdc++.h> using namespace std; const int MAXN = 50100; const int INF = 0x3f3f3f3f; typedef pair<int, int> pii; #define X first #define Y second template <typename T> inline void read(T &x) { int c = getchar(); bool fg = false; for (x = 0; !isdigit(c); c = getchar()) { if (c == '-') { fg = true; } } for (; isdigit(c); c = getchar()) { x = x * 10 + c - '0'; } if (fg) { x = -x; } } int n, a[MAXN], L[MAXN], R[MAXN]; long long ans; int b[MAXN], belong[MAXN], cnt[MAXN / 10], len, tot; pii ref[MAXN]; int calc_small(int pos) { int x = pos / len + 1; int sml = 0, lim = (x - 1) * len; for(int i = 1; i < x; i++) sml += cnt[i]; for(int i = lim; i < pos; i++) sml += b[i]; return sml; } int calc_Big(int pos) { int x = pos / len + 1; int Big = 0, lim = min(x * len - 1, n); for(int i = 1 + x; i <= tot; i++) Big += cnt[i]; for(int i = pos + 1; i <= lim; i++) Big += b[i]; return Big; } signed main() { read(n); for(int i = 1; i <= n; i++) read(a[i]), ref[i].X = a[i], ref[i].Y = i; sort(ref + 1, ref + n + 1); for(int i = 1; i <= n; i++) { if(ref[i].X != ref[i - 1].X || i == 1) a[ref[i].Y] = i; else a[ref[i].Y] = a[ref[i - 1].Y]; } len = (int) ceil(sqrt(n)); tot = n / len + 1; for(int i = 1; i <= n; i++) { belong[i] = a[i] / len + 1; cnt[belong[i]] ++; L[i] = calc_small(a[i]); b[a[i]] ++; } memset(b, 0, sizeof(b)), memset(cnt, 0, sizeof(cnt)); for(int i = n; i; i--) { cnt[belong[i]] ++; R[i] = calc_Big(a[i]); b[a[i]] ++; } for(int i = 2; i < n; i++) ans += (long long) L[i] * R[i]; printf("%lld\n", ans); return 0; }
