题解归档 - cf2227F

本文由 cf-code 本地题解库自动归档；公开内容以本地 AC/验证版本为准。

• 本地编号：cf2227F
• 本地来源：problems/cf2227F/idea.md
• 题目链接：https://codeforces.com/contest/2227/problem/F
• 原始标题：cf2227F - It Just Keeps Going Sideways

思路

cf2227F - It Just Keeps Going Sideways

pattern: pair contribution over rows.

claim: at a fixed height, the total distance moved equals the number of (cube, empty) pairs in that row where the cube is left of the empty cell. Summing heights, pair (i, j) with i < j contributes max(0, a_i - a_j).

base: compute sum_{i<j} max(0, a_i-a_j) with Fenwick counts and sums over heights.

single decrease: lowering a_p=x by one changes only pairs involving p.

• As the left endpoint, pairs (p, j) lose 1 for every j>p with a_j < x.
• As the right endpoint, pairs (i, p) gain 1 for every i<p with a_i >= x.

So the best optional operation adds max(0, left_ge_x - right_lt_x) over all positions.

check: brute row simulation on random small arrays.

代码

来源：problems/cf2227F/solution.cpp

/* Author: likely
 * Time: 2026-06-27
**/
#include<bits/stdc++.h>
#define ll long long
using namespace std;

struct BIT{
    int n;
    vector<ll> bit;
    BIT(int n=0){init(n);}
    void init(int n_){
        n=n_;
        bit.assign(n+1,0);
    }
    void add(int idx,ll val){
        for(;idx<=n;idx+=idx&-idx) bit[idx]+=val;
    }
    ll sum(int idx) const{
        ll res=0;
        for(;idx>0;idx-=idx&-idx) res+=bit[idx];
        return res;
    }
    ll range_sum(int l,int r) const{
        if(l>r) return 0;
        return sum(r)-sum(l-1);
    }
};

int main(){
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int t;
    cin>>t;
    while(t--){
        int n;
        cin>>n;
        vector<int>a(n+1);
        for(int i=1;i<=n;i++) cin>>a[i];
        BIT cnt(n),sumv(n);
        ll base=0;
        for(int i=1;i<=n;i++){
            ll cg=cnt.range_sum(a[i]+1,n);
            ll sg=sumv.range_sum(a[i]+1,n);
            base+=sg-cg*a[i];
            cnt.add(a[i],1);
            sumv.add(a[i],a[i]);
        }
        BIT left(n),right(n);
        for(int i=1;i<=n;i++) right.add(a[i],1);
        ll left_total=0,best_delta=0;
        for(int i=1;i<=n;i++){
            int x=a[i];
            right.add(x,-1);
            ll gain=left_total-left.sum(x-1);
            ll loss=right.sum(x-1);
            best_delta=max(best_delta,gain-loss);
            left.add(x,1);
            left_total++;
        }
        cout<<base+best_delta<<"\n";
    }
    return 0;
}