题解 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

    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 ;
        }
    }