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

目录

【逆序对】【树状数组+离散化】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;
}

推荐这些文章:

树状数组+离散化求逆序对

#include<cstdio>
#include<algorithm>
typedef long long LL;

int n,tot0,a[500005],b[500005];

LL ans;

struct BIT{
int c[500005];
inline int lowbit(int x){r...

树状数组 单点修改 区间查询必备

单调修改区间查询
楼兰图腾https://www.acwing.com/problem/content/243/
看看某个点的高度 他的左边和右边的点有多少个点比他高的
tr[i]为i下标点的高度 每次查询完add对某个高度 +1
就可以完成看看左边的操作
看左边的高度 从1~n 看右边的高度 从n~1
#include <ios...

树状数组的几个基本应用(更新ing)

一、求逆序对
最好能加入离散化,离散化的方式值得学习,开一个结构体,保存输入序,之后再按值大小排序,最后按输入序赋值1-n。

#include<bits/stdc++.h>
#define ll long long
#define rep(i,x,n) for(int i=x;i<=n;i++)
using name...

HH的项链 (莫队+树状数组+线段树) 代码练习

基础莫队算法
按照每个块排序 相当于优化了暴力#include <iostream>#include <cstring>#include <algorithm>#include <cmath>
using namespace std;
const int N=50010,M=2e5+10,...

蓝桥杯 第五讲 树状数组和线段树 2D/3D差分

一、树状数组 下标从1开始
操作 O(logn)

单点修改: 给某个位置上的数加上一个数
区间查询:求某一个前缀和

离线做法:不支持修改
在线做法:支持修改
原理

层数的确定:x的二进制表示中末尾有几个0
c[x] = (x-lowbit(x),x]的和
lowbit(x):返回x的二进制表达式中最低位的1所对应的值
lowbit...

经典树状数组/线段树思想学习——[SDOI2009]HH的项链/NOI.ac#44. color

HH的项链
#include<cstdio>
#include<vector>

inline void input(int &x){
int ans=0,f=1;
char c=getchar();
while(c>'9'||c<'0'){
if(c=='-')f=-1;
c=...

2022年天梯赛-全国总决赛 L3-2 关于深度优先搜索和逆序对的题应该不会很难吧这件事 (30 分)

2022天梯赛L3-2

前情提要
一个\([1,2,3,4,5,...,n]\)的全排列逆序对和顺序对数目相同
例如:\([1,2,3]\)
他的全排列方案有:
[1,2,3] 逆序对 0 顺序对 3
[1,3,2] 逆序对 1 顺序对 2
[2,1,3] 逆序对 2 顺序对 1
[2,3,1] 逆序对 2 顺序对 1
[3,1,2]...

Nowcoder little w and Discretization 主席树/线段树+树状数组/分块莫队

题目大意
给定一个序列,求区间中大于mex的数有多少
\(n \leq 3 \times 10^5\)
思路一 主席树
考虑区间mex,本题中不考虑0,区间mex的取值范围为\([a_i,a_i + 1]\)。
首先考虑区间mex求法,记\(end_i\)表示合并后第\(i\)个数的最后出现位置,对于一个区间\([l,r]\),合并后就...

AcWing 242. 一个简单的整数问题

题目传送门
#include <bits/stdc++.h>

using namespace std;
typedef long long LL;
const int N = 100010;

int n, m;
int a[N];

//注意下这里与标准模板的不同,因为求和可能会超过int上限,需要开long long
...

树状数组的应用 逆序对

1 #include<bits/stdc++.h>
2 using namespace std;
3 int n;
4 int a[1000000],b[1000000],dis[1000000];
5 int lowbit(int x)
6 {
7 return x&(-x);
8 }
...

文章标题:【逆序对】【树状数组+离散化】CF220E Little Elephant and Inversions
文章链接:https://www.dianjilingqu.com/51445.html
本文章来源于网络,版权归原作者所有,如果本站文章侵犯了您的权益,请联系我们删除,联系邮箱:saisai#email.cn,感谢支持理解。
THE END
< <上一篇
下一篇>>