『离散化 discrete』

<更新提示>

<第一次更新>

<正文>

离散化(discrete)

离散化可以说是一个很基础的算法吧，但是有些时候还是很好用很有必要的算法。

离散化的排序的一个运用，具体地讲，离散化算法是将无穷大集合中的若干个元素映射到有限大小的集合中，以达到对算法进行时间，空间复杂度的优化的效果。

当然，使用离散化算法进行优化需要满足离散化只有的数值不会影响正确性，即数值的大小只和数值之间的相对大小有关，而和绝对大小没有必然的影响。

通俗地讲，我们可以这样理解离散化：对于一个数值很大的序列，我们需要做到

输入一个排名，输出排序后该排名的元素
输入一个序列中的数，输出排序后他的排名

这样，我们就相当于得到了原数列和离散后数列(即键与值)之间的互相映射关系，既可以从排名得到元素，又可以从元素得到排名。

怎么实现呢？对于第一个问题，直接排序就可以了，对于第二个问题，可以在排序后的序列中二分查找，时间复杂度\(O(nlog_2n)\)，下面给出离散化模板。

\(Code:\)

#include<bits/stdc++.h>

using namespace std;

const int N=1000000+20;

struct sequence

{

	int num,index;

}a[N];

int n,cnt,val[N],rank[N];//val[i]代表排名为i的元素，rank[i]代表第i个元素的排名

inline bool cmp1(sequence p1,sequence p2)

{

	return p1.num<p2.num;

}

inline bool cmp2(sequence p1,sequence p2)

{

	return p1.index<p2.index;

}

inline void input(void)

{

	scanf("%d",&n);

	for(int i=1;i<=n;i++)

	{

		scanf("%d",&a[i].num);

		a[i].index=i;

	}

}

inline void discrete(void)

{

	sort(a+1,a+n+1,cmp1);

	for(int i=1;i<=n;i++)

		val[i]=a[i].num;

	cnt=unique(val+1,val+n+1)-(val+1);//去重，cnt代表去重后的长度

	sort(a+1,a+n+1,cmp2);

	for(int i=1;i<=n;i++)

		rank[i]=lower_bound(val+1,val+cnt+1,a[i].num)-val;//二分查找找到排名

}

int main(void)

{

	input();

	discrete();

	for(int i=1;i<=cnt;i++)

		printf("val[%d]=%d\n",i,val[i]);

	for(int i=1;i<=n;i++)

		printf("rank[%d]=%d\n",i,rank[i]);

	return 0;

}

measurement(USACO)

Description

最初，农夫约翰的每头奶牛每天生产G加仑的牛奶(1≤G≤10^9)。由于随着时间的推移，奶牛的产奶量可能会发生变化，农夫约翰决定定期对奶牛的产奶量进行测量，并将其记录在日志中。

他的日志中的记录如下:

35 1234 -2

14 2345 +3

第一个条目表明：在第35天，1234号奶牛的产奶量比上次测量时降低了2加仑。

第二个条目表明：在第14天，2345号奶牛的产奶量比上次测量时增加了3加仑。

农夫约翰只有在任何一天内做最多一次测量的时间（即每天最多做一次测量，但可能不做）。不幸的是，约翰有点杂乱无章，他不一定按照时间顺序记下测量结果。为了保持奶牛的产奶动力，农夫约翰自豪地在谷仓的墙上展示了目前产奶量最高的奶牛的照片（如果有若干头奶牛的产奶量最高，他就会展示所有的图片）。

请求出约翰需要调整所展示的照片的次数。

请注意，农夫约翰有一大群奶牛。所以尽管日志中记录了一些奶牛改变了产奶量，但仍然还有很多奶牛的产奶量保持在G加仑。

Input Format

第一行是两个整数N和G，分别表示测量的次数和初始产奶量。

接下来N行，每行为一次测量。每行三个数：分别表示日期一（在整数1...10 ^ 6范围内），奶牛的编号（在整数1...10 ^ 9范围内），该奶牛的产奶量变化值（一个非负数）。无论如何，每头奶牛的产奶量永远保证在0...10 ^ 9范围内。

Output Format

请输出约翰总共调整所展示的照片的次数。

Sample Input

Sample Output

解析

这道题就是一道离散化的简单运用，要把牛的编号离散化一下，那么就是一道单点修改，最值查询的线段树模板了，线段树可以参见『线段树 Segment Tree』。

\(Code:\)

#include<bits/stdc++.h>

using namespace std;

inline void read(int &k)

{

	int x=0,w=0;char ch;

	while(!isdigit(ch))w|=ch=='-',ch=getchar();

	while(isdigit(ch))x=(x<<1)+(x<<3)+(ch^48),ch=getchar();

	k=(w?-x:x);return;

}

const int N=100000+20;

struct SegmentTree

{

	int l,r,Max,same;

	#define l(x) tree[x].l

	#define r(x) tree[x].r

	#define Max(x) tree[x].Max

	#define same(x) tree[x].same

}tree[N*4];

struct cow

{

	int day,index,delta;

}a[N];

int n,g,num[N],rank[N],cnt,ans,lastval,lastnum,lastindex;

inline bool cmp1(cow p1,cow p2)

{

	return p1.index<p2.index;

}

inline bool cmp2(cow p1,cow p2)

{

	return p1.day<p2.day;

}

inline void build(int p,int l,int r)

{

	l(p)=l,r(p)=r;

	if(l==r)

	{

		Max(p)=g;

		same(p)=1;

		return;

	}

	int mid=(l+r)/2;

	build(p*2,l,mid);

	build(p*2+1,mid+1,r);

	if(Max(p*2)==Max(p*2+1))

	{

		Max(p)=Max(p*2);

		same(p)=same(p*2)+same(p*2+1);

	}

	else

	{

		if(Max(p*2)>Max(p*2+1))

		{

			Max(p)=Max(p*2);

			same(p)=same(p*2);

		}

		else if(Max(p*2)<Max(p*2+1))

		{

			Max(p)=Max(p*2+1);

			same(p)=same(p*2+1);

		}

	}

}

inline void modify(int p,int x,int v)

{

	if(l(p)==r(p))

	{

		Max(p)+=v;

		same(p)=1;

		return;

	}

	int mid=(l(p)+r(p))/2;

	if(x<=mid)modify(p*2,x,v);

	if(x>mid)modify(p*2+1,x,v);

	if(Max(p*2)==Max(p*2+1))

	{

		Max(p)=Max(p*2);

		same(p)=same(p*2)+same(p*2+1);

	}

	else

	{

		if(Max(p*2)>Max(p*2+1))

		{

			Max(p)=Max(p*2);

			same(p)=same(p*2);

		}

		else if(Max(p*2)<Max(p*2+1))

		{

			Max(p)=Max(p*2+1);

			same(p)=same(p*2+1);

		}

	}

}

inline int query(int p)

{

	if(l(p)==r(p))

		return p;

	int mid=(l(p)+r(p))/2;

	if(Max(p*2)>Max(p*2+1))

		query(p*2);

	else query(p*2+1);

}

inline void input(void)

{

	read(n);read(g);

	for(int i=1;i<=n;i++)

	{

		read(a[i].day);

		read(a[i].index);

		read(a[i].delta);

	}

}

inline void init(void)

{

	sort(a+1,a+n+1,cmp1);

	for(int i=1;i<=n;i++)

		num[i]=a[i].index;

	cnt=unique(num+1,num+n+1)-(num+1);

	sort(a+1,a+n+1,cmp2);

	for(int i=1;i<=n;i++)

	{

		rank[i]=lower_bound(num+1,num+cnt+1,a[i].index)-num;

	}

	build(1,1,cnt);

}

inline void solve(void)

{

	lastval=g;lastnum=cnt;lastindex=1;

	for(int i=1;i<=n;i++)

	{

		modify(1,rank[i],a[i].delta);

		if(Max(1)!=lastval||same(1)!=lastnum)

		{

			if(lastnum==1&&same(1)==1&&query(1)==lastindex)

				ans--;

			lastval=Max(1);

			lastnum=same(1);

			lastindex=query(1);

			ans++;

		}

	}

}

int main(void)

{

	freopen("measurement.in","r",stdin);

	freopen("measurement.out","w",stdout);

	input();

	init();

	solve();

	printf("%d\n",ans);

	return 0;

}

<后记>

巴特西

『离散化 discrete』