【离散化, 前缀和】区间和「离散化经典应用」

题目

802. 区间和

---

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

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

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

输入格式

第一行包含两个整数 $n$ 和 $m$。

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

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

输出格式

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

数据范围

$-10^9 \le x \le 10^9$,
$1 \le n,m \le 10^5$,
$-10^9 \le l \le r \le 10^9$,
$-10000 \le c \le 10000$

输入样例：

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

输出样例：

8
0
5

解题

方法一：离散化 前缀和

思路

这题是离散化模板题：离散化模板。

因为坐标的范围是 $[-10^9, 10^9]$，而给出的坐标最多只有 $3 \times 10^5$ 个（操作最多给出 $10^5$ 个坐标，查询最多给出 $2 \times 10^5$ 个坐标），具体思路是：把所有坐标全部先读入，然后把这些坐标映射到一个较小的稠密区间(a)内，然后求出映射后序列的前缀和(s)，之后每次查询先通过二分查找找到左右端点映射后的索引，再通过前缀和快速求解即可。

代码

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

public class Main {
    static List<Integer> alls = new ArrayList<>();
    static int sz;
    
    public static void main(String[] args) throws IOException {
        StreamTokenizer in = new StreamTokenizer(new BufferedReader(new InputStreamReader(System.in)));
        in.nextToken();
        int n = (int) in.nval;
        in.nextToken();
        int m = (int) in.nval;
        List<int[]> adds = new ArrayList<>(), queries = new ArrayList<>();
        while (n-- > 0) {
            in.nextToken();
            int x = (int) in.nval;
            in.nextToken();
            int c = (int) in.nval;
            alls.add(x);
            adds.add(new int[]{x, c});
        }
        while (m-- > 0) {
            in.nextToken();
            int l = (int) in.nval;
            in.nextToken();
            int r = (int) in.nval;
            alls.add(l);
            alls.add(r);
            queries.add(new int[]{l, r});
        }
        Collections.sort(alls);
        unique();
        sz = alls.size();
        int[] a = new int[sz], s = new int[sz + 1];
        for (int[] add : adds) a[find(add[0])] += add[1];
        for (int i = 1; i <= sz; ++i) s[i] = s[i - 1] + a[i - 1];
        for (int[] query : queries) System.out.println(s[find(query[1]) + 1] - s[find(query[0])]);
    }
    
    static void unique() {
        int n = alls.size();
        int slow = 0;
        for (int fast = 0; fast < n; ++fast) {
            if (!alls.get(slow).equals(alls.get(fast))) alls.set(++slow, alls.get(fast));
        }
        alls = alls.subList(0, slow + 1);
    }
    
    static int find(int x) {
        int l = 0, r = sz - 1;
        while (l < r) {
            int mid = l + r >> 1;
            if (alls.get(mid) >= x) r = mid;
            else l = mid + 1;
        }
        return l;
    }
}

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

using namespace std;

typedef pair<int, int> PII;

const int N = 3e5 + 10;
int n, m, sz;
int a[N], s[N];
vector<int> alls;
vector<PII> adds, queries;

int find(int x) {
    int l = 0, r = sz - 1;
    while (l <= r) {
        int mid = l + r >> 1;
        if (alls[mid] == x) return mid;
        else if (alls[mid] > x) r = mid - 1;
        else l = mid + 1;
    }
    return -1;
}

int main() {
    scanf("%d%d", &n, &m);
    while (n--) {
        int x, c;
        scanf("%d%d", &x, &c);
        adds.push_back({x, c});
        alls.push_back(x);
    }
    while (m--) {
        int l, r;
        scanf("%d%d", &l, &r);
        queries.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());
    sz = alls.size();
    for (PII& add : adds) a[find(add.first)] += add.second;
    for (int i = 1; i <= sz; ++i) s[i] = s[i - 1] + a[i - 1];
    for (PII& query : queries) printf("%d\n", s[find(query.second) + 1] - s[find(query.first)]);
    
    return 0;
}