AtCoder ABC 452 F 中文题面（Interval Inversion Count）
题目名称
区间逆序对计数
问题描述
给定一个正整数 \(N\)，以及一个由 \(1,2,\dots,N\) 组成的排列 \(P=(P_1,P_2,\dots,P_N)\)。
再给定一个非负整数 \(K\)。
请你求出满足以下两个条件的整数对 ((l,r)) 的个数：
- \(1 \le l \le r \le N\)（即 \([l,r]\) 是原序列的一个连续子区间）
- 子区间 \(P_l,P_{l+1},\dots,P_r\) 中，逆序对的数量恰好等于 \(K\)
定义
- 逆序对：在区间 \([l,r]\) 中，满足 \(i<j\) 且 \(P_i>P_j\) 的数对 \((i,j)\) 称为一个逆序对。
- 记 \(\text{inv}(l,r)\) 为区间 \([l,r]\) 的逆序对总数。
输入格式
N K
P_1 P_2 ... P_N
- 第一行：两个整数 \(N,K\), \((1 \le N \le 5 \times 10^5\) ,\(0 \le K \le \frac{N(N-1)}{2}\)）
- 第二行：\(N\) 个整数，表示排列 \(P\) $ (1 \le P_i \le N$，所有 \(P_i\) 互不相同）
输出格式
输出一个整数，表示满足条件的 \((l,r)\) 的个数。
样例输入1
7 3
1 4 3 2 5 6 7
样例输出1
8
样例解释
满足条件的区间为：
([1,4],[1,5],[1,6],[1,7],[2,4],[2,5],[2,6],[2,7])，共 8 个。
数据范围
- \(1 \le N \le 5 \times 10^5\)
- \(0 \le K \le \frac{N(N-1)}{2}\)
- \(P\) 是 \(1\) 到 \(N\) 的排列
思考过程
- 问题：逆序对个数为k的子区间个数。
- 思考：固定左端点 l，r in [l,n] , g[r] 右端点为r的逆序对个数，g[r] 函数具有单调性。
- 序列[1,4,3,2,5,6,7], 若 k=3，l=1， 满足条件的区间 [1,4],[1,5],[1,6],[1,7].
若 k=3, l=2, 满足条件的区间 [2,4],[2,5],[2,6],[2,7] - 对于左端点l，满足条件的右端点r，不止一个。
- 问题转化为：函数F(k) 表示 逆序对数量<=k的区间的个数。满足条件的右端点有且仅有1个。 Ans=F(k)-F(k-1) 对于左端点l，存在一个 r，满足[,r]逆序对的数量>k ,则[l,r-1]一定满足逆序对的数量<=k, cnt[l]=(r-1)-(l-1)=r-l
- 动态维护： 增加一个右端点r，贡献值为正数， j in [l,r-1]中， p[j]>p[r]的个数。转化为 ：Qry(n)-Qry(p[r])
删除一个做端点l，贡献值为负数， j in [l+1,r]中， p[j]<p[l]的个数。Qry(p[l]-1)
题目要点
- 核心：统计恰好含 \(K\) 个逆序对的连续子区间数量
- 关键转化：直接求“恰好 \(K\)"" 困难，常用方法是
\[ \text{答案} = F(K) - F(K-1)
\]
其中 \(F(m)\) 表示逆序对数量 \(\le m\) 的子区间总数
3. 高效解法：双指针（尺取法）+ 树状数组，时间复杂度 \(O(N\log N)\)，适配 \(N=5e5\) 的数据规模
#include <bits/stdc++.h>
#define LL long long
using namespace std;
const int MaxN=500005;
int n,p[MaxN],c[MaxN];
LL k;
void Add(int x,int v){for (;x<=n;x+=x&-x) c[x]+=v;
}
int Qry(int x) {int s=0;for (;x>0;x-=x&-x) s+=c[x];return s;
}LL CNT(LL m) {if (m<0) return 0; //经典错误，m==0，不是return 0;LL sum=0;LL s=0;memset(c, 0, sizeof(c));int r=0;for (int l=1;l<=n;l++) {while (r<n && s<=m) {r++; s+=Qry(n)-Qry(p[r]);Add(p[r],1);}if (s>m) sum+=r-l; else sum+=n-l+1;Add(p[l],-1);s-=Qry(p[l]-1);}return sum;
}
int main() {scanf("%d%lld",&n,&k);for (int i=1;i<=n;i++) scanf("%d",&p[i]);LL Ans=CNT(k)-CNT(k-1);cout<<Ans<<endl;return 0;
}