时间戳

首页 > 技术文章 > 【离散化】离散化

【离散化】离散化

yifusuyi 2018-09-06 15:57 原文

百度百科

definition

对于一些数量较少但是数值较大或出现负数但难以处理的数据，如果只需要考虑他们的大小关系，可以给他们重新赋值。一般的，对于\(n\)个数据，可以将他们重新赋值为\([1,n]\)之间的数字。这种方法叫做离散化。

Solution

先介绍三个\(STL\)。
\(unique\)：对于一个有序数列，将之去重。一般的，若长度为\(n\)的升序序列中有\(k\)个互不相同的元素，那么经过去重的数列前\(k\)个值是这\(k\)个值按照升序排序，剩下的位置为乱序。降序排列同理。\(unique\)的调用方法是\(unique(*begin(),*end())\)其中\(begin\)和\(end\)位置为序列首元素的迭代器以及序列尾元素的迭代器\(+1\).即区间左闭右开。\(unique\)函数是一个有返回值的函数，其返回值是去重后最后一个有序元素的迭代器\(+1\)。即返回一个左闭右开区间的右端点。
\(lower\)\(bound\):对于一个单调不下降数列，返回一个迭代器，迭代器的位置是第一个大于等于某个值的数。其调用方式是\(lower\)\(buond(*begin(),*end(),v)\)，其中\(v\)是键值。迭代器的位置就是大于等于v的第一个位置。
\(upper\)__\(bound\):调用方法等同理。不同的是此函数返回的是一个严格大于\(v\)值的最小位置。
不要问我为什么要现学这些东西因为我以前不怎么用STL
然后，使用一个temp数组记录原数组的值。对temp数组排序去重，那么原数组第i个位置的值就是temp去重后大于等于原数组原值的位置的值。好绕啊怎么办，还是看代码吧

int MU[maxn],temp[maxn];
qr(n);
for(rg int i=1;i<=n;++i) {
	qr(MU[i]);temp[i]=MU[i];
}
std::sort(temp+1,temp+1+n);
rg int cnt=std::unique(temp+1,temp+1+n)-temp-1;
for(rg int i=1;i<=n;++i) MU[i]=std::lower_bound(temp+1,temp+cnt+1,MU[i])-temp;

Example

P1774 最接近神的人

Description

小f遇到一扇门
小F发现门上有着n个数字。于是他认为打开这扇门的秘诀就是找到让这个序列变成不下降序列所需要的最小次数。但小FF不会……只好又找到了你，并答应事成之后与你三七分……

Input

第一行为一个整数n，表示序列长度
第二行为n个整数，表示序列A中每个元素。

Output

一个整数ans，即最少操作次数。

Sample Input

4
2 8 0 3

Sample Output

3

Hint

\(1~\leq~n~\leq~5~\times~10^5\);
\(-maxlongint~\leq~A_i~\leq~maxlongint\)。

Solution

根据火柴排队那道题的经验，我们可以得到每次交换相邻元素将一个乱序序列变成单调不下降的步数就是序列中逆序对数。于是使用树状数组求逆序对。因为下标不能为负，所以考虑离散化。

Code

#include<cstdio>
#include<algorithm>
#define rg register
#define ci const int
#define cl const long long int

typedef long long int ll;

namespace IO {
	char buf[90];
}

template<typename T>
inline void qr(T &x) {
	char ch=getchar(),lst=' ';
	while(ch>'9'||ch<'0') lst=ch,ch=getchar();
	while(ch>='0'&&ch<='9') x=(x<<1)+(x<<3)+(ch^48),ch=getchar();
	if(lst=='-') x=-x;
}

template<typename T>
inline void write(T x,const char aft,const bool pt) {
	if(x<0) x=-x,putchar('-');
	int top=0;
	do {
		IO::buf[++top]=x%10+'0';
		x/=10;
	} while(x);
	while(top) putchar(IO::buf[top--]);
	if(pt) putchar(aft);
}

template<typename T>
inline T mmax(const T a,const T b) {if(a>b) return a;return b;}
template<typename T>
inline T mmin(const T a,const T b) {if(a<b) return a;return b;}
template<typename T>
inline T mabs(const T a) {if(a<0) return -a;return a;}

template<typename T>
inline void mswap(T &a,T &b) {
	T temp=a;a=b;b=temp;
}

const int maxn = 500010;

int n;
int MU[maxn],temp[maxn],frog[maxn];
ll ans;

inline int lowbit(ci x) {return x&((~x)+1);}

int ask(int);
void add(int);

int main() {
	qr(n);
	for(rg int i=1;i<=n;++i) {
		qr(MU[i]);temp[i]=MU[i];
	}
	std::sort(temp+1,temp+1+n);
	rg int cnt=std::unique(temp+1,temp+1+n)-temp-1;
	for(rg int i=1;i<=n;++i) MU[i]=std::lower_bound(temp+1,temp+cnt+1,MU[i])-temp;
	for(rg int i=1;i<=n;++i) {
		ans+=ask(n)-ask(MU[i]);
		add(MU[i]);
	}
	write(ans,'\n',true);
	return 0;
}

int ask(int x) {
	int _ans=0;
	while(x) {
		_ans+=frog[x];
		x-=lowbit(x);
	}
	return _ans;
}

void add(int x) {
	while(x <= n) {
		++frog[x];
		x+=lowbit(x);
	}
}

Summary

\(lower\)\(bound\)：返回序列中第一个大于等于键值的数。
\(upper\)\(bound\)：返回序列中第一个严格大于键值的数。
区分并掌握

推荐阅读