题解归档 - cf220E

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

• 本地编号：cf220E
• 本地来源：problems/cf220E/idea.md
• 题目链接：https://codeforces.com/contest/220/problem/E
• 原始标题：220E Little Elephant and Inversions

思路

220E Little Elephant and Inversions

题意

给定长度 (n) 的数组 (a) 与上限 (k)。统计满足 (1\le l<r\le n) 的数对 ((l,r))，使得

[
b = a_1,\ldots,a_l,a_r,a_{r+1},\ldots,a_n
]

的逆序对数 (\le k)。

(n\le 10^5)，(k\le 10^{18})。

关键转化

(b) 等价于把原数组删掉中间段 (a_{l+1},\ldots,a_{r-1}) 后，把后缀 (a_r,\ldots,a_n) 接到前缀 (a_1,\ldots,a_l) 后面：

[
b = a[1..l] \;+\; a[r..n]
]

（不是「前缀 + 单独一个 (a_r) + 更短后缀」的重复拼接。）

思路

双指针 + 两个树状数组（对应当前前缀 (F=a[1..l]) 与后缀 (G=a[r..n]) 的频次）。

• 初始 (l=n-1,\,r=n)：(F) 含 (a[1..n-1])，(G) 含 (a[n])，(cur) 为 (F) 与 (G) 拼接后的逆序对数。

• 固定 (r) 从 (n) 降到 (2)：

  1. 保证 (l<r)（必要时从 (F) 末尾删元素并更新 (cur)）。
  2. 若 (cur>k)，继续缩小 (l)（删 (a[l])）。
  3. 答案加上当前 (l)（此时所有 (l'\in[1,l]) 均合法，因 (cur) 随 (l) 增大而单调不降）。
  4. (r\leftarrow r-1)：把 (a[r-1]) 插入 (G) 前端，用 BIT 更新 (cur)。

删 (F) 中 (a[l])：

[
cur \mathrel{-}= (l-\text{sumF}(a_l)) + \text{sumG}(a_l-1)
]

扩展 (G) 加入 (a_{r-1})：

[
cur \mathrel{+=} (l-\text{sumF}(a_{r-1})) + \text{sumG}(a_{r-1}-1)
]

坐标压缩后 (O(n\log n))。

模板

双 BIT 维护子数组频次与跨段逆序对增量，见 lib/数据结构(树状数组).cpp。

代码

来源：problems/cf220E/solution.cpp

/* Author: likely
 * Time: 2026-06-08 05:08:56
**/
#include<bits/stdc++.h>
#define ll long long
using namespace std;
const ll maxn=100005;
ll s[maxn+5],p[maxn+5],h1[maxn+5],h2[maxn+5],n,m,k,cur,ans,l,r;
void add1(ll x,ll v){
    while(x<=m){
        h1[x]+=v;
        x+=x&(-x);
    }
}
void add2(ll x,ll v){
    while(x<=m){
        h2[x]+=v;
        x+=x&(-x);
    }
}
ll sum1(ll x){
    ll zc=0;
    while(x>0){
        zc+=h1[x];
        x-=x&(-x);
    }
    return zc;
}
ll sum2(ll x){
    ll zc=0;
    while(x>0){
        zc+=h2[x];
        x-=x&(-x);
    }
    return zc;
}
void reml(){
    cur-=l-sum1(s[l])+sum2(s[l]-1);
    add1(s[l],-1);
    l--;
}
int main(){
    ll i,j,zc;
    cin>>n>>k;
    for(i=1;i<=n;i++){
        cin>>s[i];
        p[i]=s[i];
    }
    sort(p+1,p+n+1);
    m=unique(p+1,p+n+1)-p-1;
    for(i=1;i<=n;i++) s[i]=lower_bound(p+1,p+n+1,s[i])-p;
    l=n-1;
    cur=0;
    for(i=1;i<n;i++){
        cur+=i-1-sum1(s[i]);
        add1(s[i],1);
    }
    add2(s[n],1);
    for(i=1;i<n;i++) cur+=sum2(s[i]-1);
    for(r=n;r>1;r--){
        while(l>=r) reml();
        while(cur>k and l>0) reml();
        ans+=l;
        if(r>2){
            while(l>=r-1) reml();
            cur+=l-sum1(s[r-1])+sum2(s[r-1]-1);
            add2(s[r-1],1);
        }
    }
    cout<<ans<<endl;
    return 0;
}