关于离散化+小Trick

离散化

干嘛用的不多说。

你不会去问度娘吗

板板

经常忘又懒得找。遂写一模板暂存。

//a为原数组,b为a的副本
void version1(){
	sort(b+1,b+1+n);
	int siz=unique(b+1,b+1+n)-b-1;

	for(int i=1,k;i<=n;i++)
		a[i]=lower_bound(b+1,b+1+siz,a[i])-b;
}


unordered_map<int,int> mp;
void version2(){
	int cnt=0;

	for(int i=1;i<=n;i++){
		if(mp.find(a[i])==mp.end())
			mp[a[i]]=++cnt;
		
		a[i]=mp[a[i]];
	}
}

Trick

直接离散化会导致本不连续的值连续,有两种解决方法。

法一:

离散化的时候把每个值+1放到离散化数组里,这样原本不连续的数离散化后也不连续。

法二:

这种方法常数会小一些。

记录一下离散化数组中每个数是否和前一个数一样,如果离散化用的数组叫做 \(lsh\),令 \(dif_i=[lsh_i=lsh_{i-1}]\) ,求出 \(dif\) 的前缀和 \(blo_i\),那么 \(blo_i\) 相同的数就是在一个连续块里的。

\(f_i=[blo_{a_i}=blo_{a_{i-1}}]\)(也就是这一位是否和前一位在一个连续块里),再用一个树状数组维护 \(f\) 的前缀和,就可以快速查询一个区间内的所有值是否都在同一个连续块里。

内心OS:感觉没人会为了离散化而单独写一个树状数组吧…

请登录后发表评论

    没有回复内容