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