侧边栏壁纸
博主头像
GabrielxD

列車は必ず次の駅へ。では舞台は?私たちは?

  • 累计撰写 471 篇文章
  • 累计创建 108 个标签
  • 累计收到 9 条评论

目 录CONTENT

文章目录

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

GabrielxD
2022-10-27 / 0 评论 / 0 点赞 / 27 阅读 / 964 字 / 正在检测是否收录...

题目

802. 区间和


假定有一个无限长的数轴,数轴上每个坐标上的数都是 00

现在,我们首先进行 nn 次操作,每次操作将某一位置 xx 上的数加 cc

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

输入格式

第一行包含两个整数 nnmm

接下来 nn 行,每行包含两个整数 xxcc

再接下来 mm 行,每行包含两个整数 llrr

输出格式

mm 行,每行输出一个询问中所求的区间内数字和。

数据范围

109x109-10^9 \le x \le 10^9,
1n,m1051 \le n,m \le 10^5,
109lr109-10^9 \le l \le r \le 10^9,
10000c10000-10000 \le c \le 10000

输入样例:

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

输出样例:

8
0
5

解题

方法一:离散化 前缀和

思路

这题是离散化模板题:离散化模板

因为坐标的范围是 [109,109][-10^9, 10^9],而给出的坐标最多只有 3×1053 \times 10^5 个(操作最多给出 10510^5 个坐标,查询最多给出 2×1052 \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;
}
0

评论区