离散化

更像集中化

题：
    求一个无限长的轴的上，某段区间的和

离散化：把原来第k小的元素映射到下标为k的位置

尽量就是所有出现的点（包括查询），都进行离散化

注意点的总数

c++解法

/*
离散化：（我感觉更像是连续化doge）
    将原来稀疏的区间化为连续区间

本题是一段无限长的x轴，其中分布的点很分散，
这时候就可以将所有的点打包成一段区间，并将其中的缝隙去掉，
变成一个新的轴（从1开始，方便便后面的前缀和等操作），点是连续分布的

注意：我们离散的对象是x轴，变成一个新的轴（后面称为a轴了）

例：（将原来的(用到的)绝对坐标转化为了顺序坐标）
    点只分布x=-100,x=-20,x=10,x=60
    离散后a=1(映射x=-100),a=2(x=-20),a=3(10),a=4(60)

关键点：1.排序2.去重3.找原坐标所对应的离散化的点
*/
#include<bits/stdc++.h>
using namespace std;

const int N=3e5+10;//添加操作和查询操作一共的x坐标数量

int arr[N],sum[N];
typedef pair<int,int> pii;
vector<int> alls;//a轴，离散化后的结果，存的是映射到的x坐标
vector<pii> add,query;//添加操作和询问操作

int find(int x){//找原坐标对应的离散后坐标
    //return lower_bound(alls.begin(),alls.end(),x)-alls.begin()+1;//直接用slt


    //映射的x坐标是有序的，因此可以用二分
    //这里用左用右应该都行
    int l=0,r=alls.size()-1;
    while(l<r){
        int mid=(l+r)>>1;
        if(x<=alls[mid]){
            r=mid;
        }else{
            l=mid+1;
        }
    }

    return l+1;
    //这里要加1，因为vector默认从0开始存
    //加1后是为了方便前缀和的运算
}
int main(){
    int n,m;
    cin>>n>>m;
    for(int i=0;i<n;i++){
        int x,c;
        cin>>x>>c;
        add.push_back({x,c});
        alls.push_back(x);
    }
    for(int i=0;i<m;i++){
        int l,r;
        cin>>l>>r;
        query.push_back({l,r});
        alls.push_back(l);
        alls.push_back(r);
    }

    //排序
    sort(alls.begin(),alls.end());
    //去重
    alls.erase( unique(alls.begin(),alls.end()) , alls.end());
        //unique返回 第一个开始重复 的地址

    //在离散后的坐标中插入值
    for(auto t:add){
        //t表示遍历add中所有的值，相当于alls[i]
        int a=find(t.first);
        arr[a]+=t.second;
    }

    //前缀和
    for(int i=1;i<=alls.size();i++){
        sum[i]+=sum[i-1]+arr[i];
    }
    //询问前缀和
    for(auto t:query){
        int l=find(t.first),r=find(t.second);
        cout<<sum[r]-sum[l-1]<<endl;
    }
    return 0;

}

直接用pair<int, string> p={1, "world"}就行，其他用得不多

pair的初始化：(简单看看就行)

初始化方式	示例代码	特点
直接初始化	pair<int, string> p(1, "hello");	简洁，直接构造
列表初始化	pair<int, string> p{1, "world"},p1={1, "world"}	支持初始化列表（C++11+）
使用 make_pair	auto p = make_pair(2, "C++");	类型推导更简便
拷贝/移动初始化	pair<int, string> p2(p1);	利用现有对象进行构造
结构绑定（C++17+）	auto [k, v] = p;	解构绑定元素，代码更清晰

在二分那里使用stl：会比手写要慢

set转vector

//有序集合解法
    //这里有边界问题：最后就是连查询操作都要离散化
#include<bits/stdc++.h>
using namespace std;
#define PII pair<int,int>
#define VI vector<int>
#define x first
#define y second

const int N=4e5+10;
int arr[N],sum[N];
set<int> tmp;
vector<int> alls;
vector<PII> query;//查询
vector<PII> add;//操作
int n,m;
int find(int x){
    // return distance(alls.begin(),alls.lower_bound(x))+1;
    return lower_bound(alls.begin(),alls.end(),x)-alls.begin()+1;
        //这里其实用转换为容器的那个更方便，这里主要像用下set
}
int main(){
    cin>>n>>m;
    for(int i=0;i<n;++i){
        int x,c;cin>>x>>c;
        tmp.insert(x);
        add.push_back({x,c});
    }
    for(int i=0;i<m;++i){
        int l,r;cin>>l>>r;
        tmp.insert(l);
        tmp.insert(r);
        query.push_back({l,r});
    }
    alls=vector<int>(tmp.begin(),tmp.end());//转换成容器
    for(auto& o:add){
        int k=find(o.x);
        arr[k]+=o.y;
    }
    for(int i=1;i<=alls.size();++i){
        sum[i]=sum[i-1]+arr[i];
    }
    for(auto& q:query){
        int l=find(q.x),r=find(q.y);
        cout<<sum[r]-sum[l-1]<<endl;
    }

    return 0;
}

java版

多看看这个

    static Set<Integer> tmp=new TreeSet<>();
    static Integer[] alls;
    static int find(int x) {
        return Arrays.binarySearch(alls, x)+1;//这里已经避免了边界问题了
    }

        //自动排序并去重
            //变成数组
        alls=tmp.toArray(new Integer[0]);//转换成Integer[]

完整代码：

// package 基础算法;

import java.io.*;
import java.util.*;




public class Main{
    static final int N=(int)3.5e5+10;
    static int n,m;
    static Set<Integer> tmp=new TreeSet<>();
    static List<Map.Entry<Integer,Integer>> add=new ArrayList<Map.Entry<Integer,Integer>>(),query=new ArrayList<Map.Entry<Integer,Integer>>();
        //这里其实是Pair，不想定义一个新的类了
    static Integer[] alls;
    static int[] arr=new int[N],sum=new int[N];
    static int find(int x) {
        return Arrays.binarySearch(alls, x)+1;//这里已经避免了边界问题了
    }
    public static void main(String[] args) throws Exception {
        BufferedReader br=new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw=new BufferedWriter(new OutputStreamWriter(System.out));
        String[] ss;

        ss=br.readLine().split(" ");
        n=Integer.parseInt(ss[0]);m=Integer.parseInt(ss[1]);
        for(int i=0;i<n;++i) {
            ss=br.readLine().split(" ");
            int x=Integer.parseInt(ss[0]),c=Integer.parseInt(ss[1]);
            add.add(Map.entry(x,c));
            tmp.add(x);
        }
        for(int i=0;i<m;++i) {
            ss=br.readLine().split(" ");
            int l=Integer.parseInt(ss[0]),r=Integer.parseInt(ss[1]);
            query.add(Map.entry(l,r));
            tmp.add(l);
            tmp.add(r);
        }
        //自动排序并去重
            //变成数组
        alls=tmp.toArray(new Integer[0]);//转换成Integer[]
        for(Map.Entry<Integer, Integer> a:add) {
            int k=find(a.getKey()),c=a.getValue();
            arr[k]+=c;
        }
        //求前缀和
        for(int i=1;i<=alls.length;++i) {
            sum[i]=sum[i-1]+arr[i];
        }
        //查询
        for(Map.Entry<Integer, Integer> q:query) {
            int l=find(q.getKey()),r=find(q.getValue());
            System.out.println(sum[r]-sum[l-1]);
        }
        bw.flush();
    }
}

需要注意的是，为了避免返回Object类型的数组，可以传递一个指定类型的数组作为参数，如果数组大小不够，则会创建一个新数组。

==最后变为数组时new Integer[0]，万千别忘了==

        Set<Integer> tmp=new TreeSet<>();
        tmp.add(2);
        tmp.add(2);
        tmp.add(2);
        tmp.add(1);
        tmp.add(3);
        Integer[] alls=new ArrayList<Integer>(tmp).toArray(new Integer[0]);
        System.out.println(Arrays.toString(alls));