avatar

离散化

离散化

离散化的两个核心问题:

  1. 数组中可能有重复元素 – 去重
  2. 快速映射,算出a[] 离散化的值

模板

vector<int> alls; // 存储所有待离散化的值
sort(alls.begin(), alls.end()); // 将所有值排序
//alls.erase(unique(alls.begin(), alls.end()), alls.end()); // 去掉重复元素



//去重
public static int unique(List<Integer> list) {
int j = 0;
for (int i = 0; i < list.size(); i++) {
if (i == 0 || list.get(i) != list.get(i - 1)) {
list.set(j++, list.get(i));
}
}
return j;
}



// 二分求出x对应的离散化的值
int find(int x) // 找到第一个大于等于x的位置
{
int l = 0, r = alls.size() - 1;
while (l < r)
{
int mid = l + r >> 1;
if (alls[mid] >= x) r = mid;
else l = mid + 1;
}
return r + 1; // 映射到1, 2, ...n
}

题目

AcWing

  • 802 区间和

802

描述

假定有一个无限长的数轴,数轴上每个坐标上的数都是0。

现在,我们首先进行 n 次操作,每次操作将某一位置x上的数加c。

接下来,进行 m 次询问,每个询问包含两个整数l和r,你需要求出在区间[l, r]之间的所有数的和。

解答
import java.util.*;

public class Main {
public static void main (String[] args) {
Scanner sc = new Scanner(System.in);
int n = sc.nextInt(); //n次操作
int m = sc.nextInt(); //m次询问
int N = 300010; //因为需要将所有x,l,r存在数组中,这样就是n + 2m <= 300000
int[] a = new int[N]; //从1开始,需要通过x找到离散量,然后+1,
int[] s = new int[N]; //前缀和来做,所以需要从1开始记录a

List<Integer> alls = new ArrayList<>(); //将所有的使用到的数存在alls中,比如x,l,r
//但其中会有先后顺序的差别,以及重复,所以需要排序和去重
List<Pairs> add = new ArrayList<>(); //用来存n次操作
List<Pairs> query = new ArrayList<>(); //用来存m次询问

for (int i = 0; i < n; i++) {
int x = sc.nextInt();
int c = sc.nextInt();
add.add(new Pairs(x, c));
alls.add(x); //存入alls中,为后续操作做准备
}

for (int i = 0; i < m; i++) {
int l = sc.nextInt();
int r = sc.nextInt();
query.add(new Pairs(l, r));
alls.add(l);
alls.add(r);
}
//到此为止,alls中存好了所有会被用到的数轴上的点,可以进行离散化操作
// 1. 排序 2. 去重
Collections.sort(alls);
int unique = unique(alls);
alls = alls.subList(0, unique); //将去重后的List保存下来,或者此处也可以将unique作为最后一个数,用r作为二分

for (Pairs item:add) {
int index = find(item.first, alls);
a[index] += item.second;
}

//求前缀和
for (int i = 1; i <= alls.size(); i++) s[i] = s[i - 1] + a[i];

for (Pairs item:query) {
int l = find(item.first, alls);
int r = find(item.second, alls);
System.out.println(s[r] - s[l - 1]);
}
}

//去重
static int unique(List<Integer> list) {
int j = 0;
for (int i = 0; i < list.size(); i++) {
if (i == 0 || list.get(i) != list.get(i - 1)) {
list.set(j, list.get(i));
j++;
}
}
return j;
}

static int find(int x, List<Integer> list) {
int l = 0;
int r = list.size();
while (l < r) {
int mid = l + r >> 1;
if (list.get(mid) >= x) {
r = mid;
} else {
l = mid + 1;
}
}
return l + 1; //因为要考虑到前缀和
}
}

class Pairs {
int first;
int second;
public Pairs(int first, int second) {
this.first = first;
this.second = second;
}
}

Others

人无完人,何况是小白Chen我呢,文章难免会出现一些错误,若是读者们发现错误,可以评论或者联系我,Chen会尽力改正,给大家更优秀的博文。

文章作者: Chen
文章链接: https://vccyb.gitee.io/myblog/2020/03/22/Algorithm/articleM-9/
版权声明: 本博客所有文章除特别声明外,均采用 CC BY-NC-SA 4.0 许可协议。转载请注明来自 东川
打赏
  • 微信
    微信
  • 支付寶
    支付寶

评论