离散化
干嘛用的不多说。
你不会去问度娘吗
板板
经常忘又懒得找。遂写一模板暂存。
//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:感觉没人会为了离散化而单独写一个树状数组吧…
没有回复内容