【逆序对】【树状数组+离散化】CF220E Little Elephant and Inversions

目录

题目链接

题意:

给定长度为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;
}
上一篇:srv.exe蠕虫病毒~


下一篇:数字式PID控制的应用总结