一、基础算法8：离散化模板题+算法模板（区间和）

我会带着你远行 2023-10-09 18:59 34阅读 0赞

#### 文章目录 ####

*  离散化介绍
 *  算法模板
 *   *  离散化题目模板
 *  模板题
 *   *  区间和
     *   *  原题链接
         *  题目
         *  题解
         *   *  思路
     *  unique原理补充介绍

## 离散化介绍 ##

![在这里插入图片描述][68d32b766a984cfd907367139b779ee4.png]  
![在这里插入图片描述][aa844b976b144e24bd70cc61672dae1d.png]  
![在这里插入图片描述][804c0b98b28042d59f661877ea8cc2e7.png]  
![在这里插入图片描述][bc58bbbbd2194484868ffc5098b32728.png]

## 算法模板 ##

### 离散化题目模板 ###

vector<int> alls; // 存储所有待离散化的值
    sort(alls.begin(), alls.end()); // 将所有值排序
    alls.erase(unique(alls.begin(), alls.end()), alls.end());   // 去掉重复元素
    
    // 二分求出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
    }

## 模板题 ##

### 区间和 ###

#### 原题链接 ####

[https://www.acwing.com/problem/content/804/][https_www.acwing.com_problem_content_804]

#### 题目 ####

802 . 区间和  
假定有一个无限长的数轴，数轴上每个坐标上的数都是 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

#### 题解 ####

##### 思路 #####

进行 n次操作，每次操作将某一位置 x上的数加 c  
m次询问，每个询问包含两个整数 l和 r  
因此会涉及到n+2m个下标，而1≤n,m≤10^5,所以N开3e5+10  
会用到的下标都会被保存到alls数组，这样就可以把这些数对应的下标离散化映射到自然数1,2,3,…下标  
![在这里插入图片描述][bca9c23577644c919f10b268ffb81714.png]

使用二分查找函数find（x）（x为原来的下标）即可查找到映射后在alls数组中对应的下标  
然后使用前缀和处理来解决查询问题

#include <iostream>
    #include <vector>
    #include <algorithm>
    using namespace std;
    
    const int N = 3e5 + 10;
    
    typedef pair<int,int> PII;
    
    int a[N],s[N]; //s[i]为a[i]的前缀和数组
    
    vector<int> alls; //存的是原下标！ 
    vector<PII> add,query;
    int n,m;
    //二分查找 
    int find(int x){
         //查找x对应在alls数组中的下标 
    	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表示从1开始映射，不+1表示从0开始映射 
    }
    int main(){
        
    	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());//去重
    	
    	// 处理插入
    	for(auto item : add){
        
    		int x = find(item.first); //x即为原下标在alls数组中对应的下标。也即为离散化后映射的下标(1,2,3,...) 
    		a[x]+=item.second;
    		
    	} 
    	
    	// 预处理前缀和
    	for(int i=1;i<=alls.size();i++){
        
    		s[i] = s[i-1]+a[i];
    	} 
    	
    	// 处理询问
    	for(int i=0;i<m;i++){
        
    		int l = find(query[i].first);
    		int r = find(query[i].second);
    		cout<<s[r] - s[l-1]<<endl;
    	}
    }

### unique原理补充介绍 ###

![在这里插入图片描述][05c475fe803e4b84a781c6bbb4ed7910.png]  
![在这里插入图片描述][f1754503b5ad4c7c9b218328440c99da.png]

[68d32b766a984cfd907367139b779ee4.png]: https://img-blog.csdnimg.cn/68d32b766a984cfd907367139b779ee4.png
[aa844b976b144e24bd70cc61672dae1d.png]: https://img-blog.csdnimg.cn/aa844b976b144e24bd70cc61672dae1d.png
[804c0b98b28042d59f661877ea8cc2e7.png]: https://img-blog.csdnimg.cn/804c0b98b28042d59f661877ea8cc2e7.png
[bc58bbbbd2194484868ffc5098b32728.png]: https://img-blog.csdnimg.cn/bc58bbbbd2194484868ffc5098b32728.png
[https_www.acwing.com_problem_content_804]: https://www.acwing.com/problem/content/804/
[bca9c23577644c919f10b268ffb81714.png]: https://img-blog.csdnimg.cn/bca9c23577644c919f10b268ffb81714.png
[05c475fe803e4b84a781c6bbb4ed7910.png]: https://img-blog.csdnimg.cn/05c475fe803e4b84a781c6bbb4ed7910.png
[f1754503b5ad4c7c9b218328440c99da.png]: https://img-blog.csdnimg.cn/f1754503b5ad4c7c9b218328440c99da.png