离散化

概念

当一个集合里，个数少，但是值的范围大，并且我们做题需要利用这些值为下标。比如我们总不可能开一个长度为10的9次方的数组。此时我们就需要离散化。 也就是将长度为10的5次方个数，且范围在10的9次方以内映射到一个连续的数组里。

具体步骤

int a[]={1,20,55,90,100000,2520000};

此时我们需要做的就是：

int b[]; b[0]=1; b[1]=20; b[2]=55; .....

这里存在俩个问题： 1，a中可能存在重复元素（需要去重） java去重方式：

//这里我之前试了hashset去重，但是会超时。这里建议先排序再在有序的情况下for循环去重 //注意，这里的list参数已经Collections.sort(list);排序了！！！ public static ArrayList<Integer> paichong(ArrayList<Integer> list) { ArrayList<Integer> linkedList = new ArrayList(); linkedList.add(list.get(0)); for (int i = 1; i < list.size(); i++) { if (list.get(i - 1) != list.get(i)) linkedList.add(list.get(i)); } return linkedList; }

2，如何快速算出，也就是55在b中的下标是多少（二分）

public static int find(int x){//快速找到x在映射的数组下标 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 r; }

模板题

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

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

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

输入格式 第一行包含两个整数n和m。

接下来 n 行，每行包含两个整数x和c。

再接下里 m 行，每行包含两个整数l和r。

输出格式 共m行，每行输出一个询问中所求的区间内数字和。

数据范围 −109≤x≤109, 1≤n,m≤105, −109≤l≤r≤109, −10000≤c≤10000 输入样例： 3 3 1 2 3 6 7 5 1 3 4 6 7 8 输出样例： 8 0 5

//package No1; import java.io.BufferedReader; import java.io.IOException; import java.io.InputStreamReader; import java.io.OutputStreamWriter; import java.io.PrintWriter; import java.io.StreamTokenizer; import java.util.ArrayList; import java.util.Collections; public class Main { public static void main(String[] args) throws IOException { StreamTokenizer in = new StreamTokenizer(new BufferedReader( new InputStreamReader(System.in))); PrintWriter out = new PrintWriter(new OutputStreamWriter(System.out)); in.nextToken(); int n = (int) in.nval; in.nextToken(); int m = (int) in.nval; long arr[] = new long[3 * 1000 * 100 + 10];// 存储值 ArrayList<operate> oper = new ArrayList();// 存储添加操作 ArrayList<query> que = new ArrayList();// 存储查询操作 ArrayList<Integer> alls = new ArrayList();// 存储所有要离散化的下标 for (int i = 0; i < n; i++) { in.nextToken(); int index = (int) in.nval; in.nextToken(); int val = (int) in.nval; oper.add(new operate(index, val)); alls.add(index); } for (int i = 0; i < m; i++) { in.nextToken(); int l = (int) in.nval; in.nextToken(); int r = (int) in.nval; que.add(new query(l, r)); alls.add(l); alls.add(r); } Collections.sort(alls);// 排序 alls = paichong(alls); for (operate t : oper) { arr[find(alls, t.index)] += t.val; } for (int i = 1; i < arr.length; i++) { arr[i] += arr[i - 1]; } // for (Integer t : alls) { // arr[find(alls, t)] += arr[find(alls, t) - 1]; // } for (query t : que) { out.println(arr[find(alls, t.r)] - arr[find(alls, t.l) - 1]); } out.flush(); } public static ArrayList<Integer> paichong(ArrayList<Integer> list) { ArrayList<Integer> linkedList = new ArrayList(); linkedList.add(list.get(0)); for (int i = 1; i < list.size(); i++) { if (list.get(i - 1) != list.get(i)) linkedList.add(list.get(i)); } return linkedList; } public static int find(ArrayList<Integer> alls, int x) {// 根据x找到arr的下标 int l = 0, r = alls.size() - 1; while (l < r) { int mid = (l + r) >> 1; if (alls.get(mid) >= x) r = mid; else l = mid + 1; } return r + 1; } } class query {// 查询 int l, r; public query(int l, int r) { this.l = l; this.r = r; } } class operate {// 操作的值 int index, val; public operate(int index, int val) { this.index = index; this.val = val; } }