题解 CF1268C 【K Integers】

皎月半洒花

2019-12-25 09:20:27

Solution

然而似乎另一篇题解是两只 $\log$ 的,这个地方说一种一个 $\log$ 的做法:善用 $\rm BIT$ . 发现似乎最终 $1\sim k$ 肯定会被合并到一起,所以把代价分为两个部分,求逆序对的 $\&$ 合并的。考虑合并的代价。发现对于每个大于 $k$ 的位置,要么把它向前移,要么把它向后移,所以答案就是 $\min(s_i,k-s_i)$,其中 $s_i$ 表示 $i-$前缀 中 $\leq k$ 的数的个数。 于是就得到一个 $n^2$ 的做法。但考虑其实 $\min(s_i,k-s_i)$ 这东西某个临界点的左右分别单调,所以考虑二分出这个中间点,然后直接拿等差数列求和公式做。 那么显然这东西只需要求一个中位数即可。而 $\rm BIT$ 本身支持二分,所以用树状数组可以做到小常数的 $n\log n$,比线段树不知道要快到哪里去了.jpg ```cpp LL ans1, ans2 ; int N, base[MAXN], pos[MAXN] ; struct BIT{ LL _bit[MAXN] ; void ins(int x, int v){ for ( ; x <= N ; x += (x & -x)) _bit[x] += v ; } LL ask(int x){ LL res = 0 ; for ( ; x ; x -= (x & -x)) res += _bit[x] ; return res ; } int find_k(int k){ int res = 0 ; for (int j = 20 ; j >= 0 ; -- j) if ((res | 1 << j) <= N) if (_bit[res | (1 << j)] <= k) res |= (1 << j), k -= _bit[res] ; return res ; } }A, B ; int main(){ cin >> N ; int i, j ; for (int i = 1 ; i <= N ; ++ i) scanf("%d", &base[i]), pos[base[i]] = i ; for (int i = 1 ; i <= N ; ++ i){ A.ins(pos[i], 1), B.ins(pos[i], pos[i]) ; ans1 += i - A.ask(pos[i]), j = A.find_k(i / 2) + 1 ; int median1 = i >> 1, median2 = i - 1 - median1 ; ans2 = 1ll * median1 * j - B.ask(j - 1) - (1ll * median1 * (median1 + 1) >> 1) ; ans2 += B.ask(N) - B.ask(j) - 1ll * median2 * j - (1ll * median2 * (median2 + 1) >> 1) ; printf("%lld\n", ans1 + ans2), ans2 = 0 ; } } ```