侧边栏壁纸
博主头像
CoderKui

坐中静,舍中得,事上练

  • 累计撰写 51 篇文章
  • 累计创建 69 个标签
  • 累计收到 1 条评论

目 录CONTENT

文章目录

离散化

CoderKui
2021-12-06 / 0 评论 / 0 点赞 / 223 阅读 / 723 字 / 正在检测是否收录...

离散化

一组值域较大的数,但个数较少,将它们映射到自然数上

例如:a.length < 1e5, 0 <= a[i] <= 1e9

​ a[] : 1, 3, 1000, 800000, 2500000000

​ 映射:0, 1, 2, 3, 4

  1. a中可能存在重复元素
  2. 如何算出a[i]离散化后的值

离散化是在不改变数据相对大小的条件下,对数据进行相应的缩小,它可以有效的降低时间复杂度

经典例子:

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

现在,我们首先进行 nn 次操作,每次操作将某一位置 xx 上的数加 cc。

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

输入格式

第一行包含两个整数 nn 和 mm。

接下来 nn 行,每行包含两个整数 xx 和 cc。

再接下来 mm 行,每行包含两个整数 ll 和 rr。

输出格式

共 mm 行,每行输出一个询问中所求的区间内数字和。

数据范围

−109≤x≤109−109≤x≤109,
1≤n,m≤1051≤n,m≤105,
−109≤l≤r≤109−109≤l≤r≤109,
−10000≤c≤10000−10000≤c≤10000

输入样例:

3 3
1 2
3 6
7 5
1 3
4 6
7 8

输出样例:

8
0
5
import java.util.*;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        int m = sc.nextInt();
        int N = 300010;
        int[] a = new int[N];
        int[] s = new int[N];
        List<Integer> alls = new ArrayList<>(); //存放所有使用过的数
        List<Pairs> add = new ArrayList<>();  //存放操作
        List<Pairs> query = new ArrayList<>(); //存放询问
        for(int i = 0; i < n; ++i) {
            int x = sc.nextInt();
            int c = sc.nextInt();
            add.add(new Pairs(x, c));
            alls.add(x);
        }
        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中的点进行离散化操作
        Collections.sort(alls);
        int end = unique(alls);
        alls = alls.subList(0, end);
        for(Pairs item : add) {
            int idx = find(item.first, alls);
            a[idx] += 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);
            int res = s[r] - s[l - 1];
            System.out.println(res);
        }
    }  
    
    // 去重
    public static int unique(List<Integer> list) {
        int idx = 0;
        for(int i = 0; i < list.size(); ++i) {
            if(i == 0 || list.get(i) != list.get(i - 1)) {
                list.set(idx++, list.get(i));
            }
        }
        return idx;
    }
    
    // 离散化下标
    public static int find(int x, List<Integer> list) {
        int l = 0, r = list.size() - 1;
        while(l < r) {
            int mid = l + r >> 1;
            if(list.get(mid) >= x) {
                r = mid;
            } else {
                l = mid + 1;
            }
        }
        return l + 1;
    }
}

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

评论区