离散化模板

针对无重复元素的离散化

for(i = 1;i <= n; ++i) p[i].pos = i,in(p[i].v);
sort(p+1,p+n+1);
int id = 0;
for(i = 1;i <= n; ++i) {
    a[p[i].pos] = i;
}

$p[i].pos$为在原序列中的位置，$p[i].v$为要离散的值，$a$数组为离散后的值

针对有重复元素的离散化

for(i = 1;i <= n; ++i) p[i].pos = i,in(p[i].v);
sort(p+1,p+n+1);
int id = 0;
for(i = 1;i <= n; ++i) {
    if(p[i].v > p[i-1].v) ++id;
    a[p[i].pos] = id;
}