题解 CF1268C 【K Integers】
皎月半洒花
2019-12-25 09:20:27
然而似乎另一篇题解是两只 $\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 ;
}
}
```