离散化笔记_代码007(未授权)

本文介绍: 大，但是我问他是因为键有序所以导致哈希表映射后相对顺序不变吗，它又说不是，然后就是一堆我看不懂的谜语，一直复读复读复读，啊啊啊啊啊啊啊好痛苦啊啊啊啊啊啊。其实由上述过程和代码我们可以发现，我们用数组来缩小数域的思路与哈希表不谋而合，所以说我们可以用哈希表来存我们的操作数的序列号，这样的话能将二分的。是较小的，而数据的编号很大，所以就可能出现我们映射的范围出现问题，例如一个区间。，真的很烦啊，想不出来为什么，等我以后深入一下。，也就是说，我们将零散的数域变得紧凑。，这个时候我们有个尴尬的问题，我们的。

题目链接：AcWing 802. 区间和

区间和

#include &lt;iostream&gt;
#include &lt;cstring&gt;
#include <algorithm&gt;
#include <vector&gt;

using namespace std;

typedef pair<int, int&gt; pii; 	 // 定义一个pair类型的别名PII，用于存储一对整数

int n, m; 	 // n和 m 分别表示插入操作和查询操作的数量
const int N = 300010; 	// 定义一个常量N，作为数组的大小
int a[N], s[N]; 	 	// a数组用于存储每个位置的数值，s数组用于存储前缀和

vector<int&gt; alls; 	 		// alls向量用于存储所有出现过的数
vector<pii&gt; add, query;		// add向量用于存储所有的插入操作，query向量用于存储所有的查询操作

int l, r;  	// l和r用于存储查询操作的左右边界
int x, c;  	// x和c用于存储插入操作的数和次数

int find(int x) 	 // find函数用于在alls向量中找到x的位置
{
    int l = 0, r = alls.size() - 1;
    
    while(l < r){
        int mid = (l + r) &gt;&gt; 1;
        if(alls[mid] >= x) r = mid;
        else l = mid + 1;
    }
    
    return r + 1;
}

int main()
{
    cin >> n >> m;  	// 输入插入操作和查询操作的数量
    while (n -- ){
        cin >> x >> c;
        add.push_back({x, c});
        
        alls.push_back(x); 	 // 将x加入到alls向量中
    }
    
    while (m -- ){
        cin >> l >> r;
        query.push_back({l, r});
        
        alls.push_back(l);  	// 将l和r加入到alls向量中
        alls.push_back(r);
    }
    
    // 去重
    sort(alls.begin(), alls.end());  	// 对alls向量进行排序
    alls.erase(unique(alls.begin(), alls.end()), alls.end());  // 删除alls向量中的重复元素
    
    // 找加入元素的位置并初始化加入数组
    for(auto item : add){
        int x = find(item.first);
        a[x] += item.second;
    }
    
    // 前缀和
    for(int i = 1; i <= alls.size(); ++i) s[i] += s[i - 1] + a[i];
    
    // 询问
    for(auto item : query){
        l = find(item.first), r = find(item.second);
        printf("%dn", s[r] - s[l - 1]);
    }
}

#include <iostream>
#include <cstring>
#include <algorithm>
#include <vector>

using namespace std;

typedef pair<int, int> pii;

int n, m;
const int N = 300010;
int a[N], s[N];
vector<int> alls;
vector<pii> add, query;
int l, r;
int x, c;

int find(int 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;
}



int main()
{
    cin >> n >> m;
    while (n -- ){
        cin >> x >> c;
        add.push_back({x, c});
        
        alls.push_back(x);
    }
    
    while (m -- ){
        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());
    
    unordered_map<int, int> indx;
    for(int i = 1; i <= alls.size(); ++i) indx[alls[i - 1]] = i;
    
    // 找加入元素的位置并初始化加入数组
    for(auto item : add){
        int x = indx[item.first];
        a[x] += item.second;
    }
    
    // 前缀和
    for(int i = 1; i <= alls.size(); ++i) s[i] += s[i - 1] + a[i];
    
    // 询问
    for(auto item : query){
        l = indx[item.first], r = indx[item.second];
        printf("%dn", s[r] - s[l - 1]);
    }
}

这个代码是我从评论区抄的，位置：https://www.acwing.com/solution/content/13511/，往下翻评论区有个哈希表代码

但是我怎么都看不懂他哈希表的赋值操作

for(int i = 1; i <= alls.size(); ++i) indx[alls[i - 1]] = i;

艹！！！！！！！！！为什么！！！！！！！！！
问bing，他跟我说因为是我在之前对alls[]数组排序去重了，所以区间[l, r]肯定不会映射出错，r映射完肯定比l大，但是我问他是因为键有序所以导致哈希表映射后相对顺序不变吗，它又说不是，然后就是一堆我看不懂的谜语，一直复读复读复读，啊啊啊啊啊啊啊好痛苦啊啊啊啊啊啊