题意:
给定长度为n的序列A,取两个断点l和r,求由A[1],A[2],...,A[l],A[r],A[r+1],..A[n]组成的新序列B且其逆序对不大于k对的个数。
思路:
-
宏观上:对于一个一对选择l和r,r向后推会使得逆序对个数保持不变或者减少,但必然不会带来增加。于是对一对恰好满足条件的l和r来说,它本身及其可以引出来的答案数为n-r+1。
-
微观上:
-
对于l
其所形成的个数为区间
[1,l-1]
中大于A[l]
的个数和区间[r,n]
中小于A[l]
的个数。 -
对于r
其所形成的个数为区间
[1,l]
中大于A[r]的个数和区间[r-1,n]
中小于A[r]
的个数。 -
因而,若是减小l或者扩大r,就要减去这部分的贡献;若是增大l或者减小r,就要加上这部分的贡献。
-
同时,如果l和r碰到一起了,要让r进行加一
-
且r不能够回头跑,因为往回跑,必然会使得逆序对增加(l也会增大且已经是卡在临界条件上)。
-
-
如果要枚举每一对l和r,将至少是一个\(O(n^{2})\)的算法,且内部还要夹带树状数组的复杂度。
-
可以采取尺取法(双指针法)动态地移动l和r,动态地修改答案。
-
由于数值达到
1e18
,所以要对数据离散化,不能直接存入数组(空间不够)。
#include<bits/stdc++.h>
#define ll long long
using namespace std;
const int N = 1E5+500;
int n,k,A[N],B[N];
struct tr_array{
int tot;
static const int maxn = 1e5+500;
int arr[maxn];
int inline lowbit(int x)
{
return (-x)&x;
}
void inline add(int x,int num)
{
tot += num;
for(;x<=maxn;x+=lowbit(x)) arr[x] += num;
}
int inline ask(int x)
{
int res = 0;
for(;x;x-=lowbit(x)) res += arr[x];
return res;
}
}tr_l,tr_r;
int main()
{
ios::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);
cin>>n>>k;
for(int i=1;i<=n;i++)
cin>>A[i],B[i] = A[i];
//离散化
sort(B+1,B+n+1);
int tot = unique(B+1,B+n+1)-(B+1);
for(int i=1;i<=n;i++) A[i] = lower_bound(B+1,B+tot+1,A[i])-B;
//预处理r
ll cur = 0;
for(int i=n;i>=1;i--)
{
cur += tr_r.ask(A[i]-1);
tr_r.add(A[i],1);
}
int l = 1, r = 1;
ll ans = 0;
while(l<n&&r<=n)
{
//l部分
cur += tr_r.ask(A[l]-1);
cur += (tr_l.tot-tr_l.ask(A[l]));
tr_l.add(A[l],1);
while(l==r||cur>k)
{
cur -= (tr_l.tot-tr_l.ask(A[r]));
cur -= tr_r.ask(A[r]-1);
tr_r.add(A[r],-1);
r++;
if(r==n+1) break;
}
ans += (n-r+1);
l++;
}
cout<<ans;
return 0;
}