区间和-离散化初识

• 题目
• 思路
• • 去重模板
• 代码

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

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

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

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

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

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

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

数据范围
−10⁹≤x≤10⁹,
1 ≤ n, m ≤ 10⁵,
−10⁹ ≤ l ≤ r ≤10⁹,
−10000 ≤ c ≤ 10000
输入样例：

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

输出样例：

8
0
5

若暴力求解，0则会被处理多次，使用离散化解，将需要操作的下标合并为一个数组，除去没有被输入的下标空间，将会大大减少计算的时间复杂度。

 1、首先将所有输入需要操作的下标，题目中的x、l、r全部放入一个数组alls中，对alls中有重复的元素，需要进行去重，去重后得到所有需要被操作的下标（无重复），而根据题意很容易想到用前缀和来求解区间的和。

  以输入样例为例，需要处理的下标为：1、3、7、1、3、4、6、7、8（前三个为加入c的下标，后六个为询问区间的下标）。去重的操作C++使用unique()函数，配合sort,erase一起使用，以下为去重模板：

	vectoralls;
	
	//去重前先排序
	sort(alls.begin(), alls.end());
	
	alls.erase(unique(alls.begin(), alls.end()), alls.end());
	// unique将不重复元素前移，返回不重复元素的下一个位置，使用erase将多余的部分删除。

  去重后alls中的元素为{1, 3, 4, 6, 7, 8}。

 2、alls中的元素为源数组中需要修改的下标，将每一个下标在一个新的数组a[N]里一一对应，数组a[N]的下标为数组alls里元素的映射。前面提到前缀和，所以我们希望新的下标从1开始记录数据。

 例子中创建一个新的数组a[N](原无限大数组离散化后的数组)。alls中的每一个元素，表示的是在无限大数组中需要调用的下标，而数组a[N]的元素下标，则是原数组中需要调用的下标的映射。
 以alls中的元素为例，内部的元素{1, 3, 4, 6, 7, 8}，在a[N]中的下标分别为1, 2, 3, 4, 5, 6。因为之后要求a[N]数组的前缀和，所以下标从1开始。
 原题中在原数组下标为1, 3, 7处分别加了2, 6, 5；那么在离散化数组a[N]中a[1] = 2, a[2] = 6, a[5] = 5。题目中要查询的下标范围[1, 3],[4, 6],[7, 8]，在a[N]中下标为[1, 2],[3, 4],[5, 6]。只要求出a[N]的前缀和s[N]，一切问题都迎刃而解。

 3、那么怎么存储对应的下标x和要加入的值c，以及如何创建alls的映射a[N]就是解题的关键。
以下vector> add 来存储下标x 和 加上的数 c，vector> query 来存储访问区间 下标l 和 下标r

使用二分法来寻找离散化数组中的应该对应的下标。

 离散化数组a[N]的长度有多少？n个操作中会输入n个下标x，m个操作中会输入一个下标 l 和一个下标 r 共2m个下标，故有n + 2*m个下标，而1 ≤ n, m ≤ 10⁵,所以数组长度最多为3 * 10⁵。

#include
#include
#include
using namespace std;

typedef pair PII;
const int N = 300010;

vectoralls;
vector add, query;
int a[N], s[N];

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;       // r + 1是因为对应的下标从1开始
    
}

int main () {
    int n, m;
    cin >> n >> m;
    while (n --) {
        int x, c;
        cin >> x >> c;
        alls.push_back(x);
        add.push_back({x, c});
    }
    while (m--) {
        int l, r;
        cin >> l >> r;
        alls.push_back(l);
        alls.push_back(r);
        query.push_back({l ,r});
    }
    
    // 去除相同元素
    sort(alls.begin(), alls.end());
    alls.erase(unique(alls.begin(), alls.end()), alls.end());
    
    //处理插入
    
    for (auto item:add) {
        int x = find(item.first);
        a[x] += item.second;
    }
    
    //数组a的前缀和
    for (int i = 1; i <= alls.size(); i++) s[i] = s[i - 1] + a[i];
    
    //处理访问区间
    for (auto item:query) {
        int l = find(item.first), r = find(item.second);
        cout << s[r] - s[l - 1] << endl;
    }
    
    return 0;
}