题解归档 - cf2227G

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

• 本地编号：cf2227G
• 本地来源：problems/cf2227G/idea.md
• 题目链接：https://codeforces.com/contest/2227/problem/G
• 原始标题：cf2227G - Drowning

思路

cf2227G - Drowning

pattern: invariant / alternating sum.

claim: an array of odd length is good iff its alternating sum c1-c2+c3-...+cm is positive. Even lengths cannot reduce to one element.

necessary: the operation replaces x,y,z with x-y+z, so it preserves the alternating sum of the whole array. The final single value is positive, hence the alternating sum must be positive.

sufficient: for length 3, positive alternating sum is exactly the operation condition. For longer positive arrays, there is always some adjacent triple with x-y+z>0; otherwise two consecutive failed inequalities imply a contradiction. Reducing such a triple preserves positivity and the same alternating sum, so induction applies.

counting: let P[i]=a1-a2+...+(-1)^{i+1}a_i. For odd-length subarray:

• if l is odd, need P[r] > P[l-1];
• if l is even, need P[r] < P[l-1].

Maintain Fenwick trees of previous prefix values by prefix-index parity.

check: recursive brute for random small arrays.

代码

来源：problems/cf2227G/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;
    }
};

int main(){
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int t;
    cin>>t;
    while(t--){
        int n;
        cin>>n;
        vector<ll>a(n+1),pref(n+1),vals;
        vals.push_back(0);
        for(int i=1;i<=n;i++){
            cin>>a[i];
            pref[i]=pref[i-1]+(i&1?a[i]:-a[i]);
            vals.push_back(pref[i]);
        }
        sort(vals.begin(),vals.end());
        vals.erase(unique(vals.begin(),vals.end()),vals.end());
        auto id=[&](ll x){
            return (int)(lower_bound(vals.begin(),vals.end(),x)-vals.begin())+1;
        };
        BIT even((int)vals.size()),odd((int)vals.size());
        even.add(id(0),1);
        ll ans=0;
        for(int r=1;r<=n;r++){
            int pos=id(pref[r]);
            if(r&1){
                ans+=even.sum(pos-1);
                odd.add(pos,1);
            }else{
                ans+=odd.sum((int)vals.size())-odd.sum(pos);
                even.add(pos,1);
            }
        }
        cout<<ans<<"\n";
    }
    return 0;
}