區間和——-離散化

假定有一個無限長的數軸，數軸上每個坐標上的數都是0。

現在，我們首先進行 n 次操作，每次操作將某一位置x上的數加c。

接下來，進行 m 次詢問，每個詢問包含兩個整數l和r，你需要求出在區間[l, r]之間的所有數的和。

輸入格式

第一行包含兩個整數n和m。

接下來 n 行，每行包含兩個整數x和c。

再接下里 m 行，每行包含兩個整數l和r。

輸出格式

共m行，每行輸出一個詢問中所求的區間內數字和。

數據範圍

−109≤x≤109−109≤x≤109,
1≤n,m≤1051≤n,m≤105,
−109≤l≤r≤109−109≤l≤r≤109,
−10000≤c≤10000−10000≤c≤10000

輸入樣例：

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

輸出樣例：

8
0
5

思路：

離散化的思路，因為我們的坐標有2e9這麼大的數值，而我們用到的只有3e5這麼點數值，對於這種類型的，我們就要想到離散化，將各個散開的點用映射到下標（1，2，3，4…….）上，這要如何做呢？我們首先要將輸入的數據進行保存，將出現的過的坐標存到數組中，用於映射，進行排序和去重，坐標對應數組的下標就是我們要的映射。然後就進行常規操作，前綴和求區間和。

詳細程式碼解析：

#include<iostream>
#include<vector>
#include<algorithm>
using namespace std;

typedef pair<int, int>  PII;
const int N = 300010;
int a[N], s[N];//儲存映射出來的下標保存的值和前綴和。
vector<PII> add, query;//保存數據。
vector<int> alls;//儲存所有用到的坐標值。

//二分查找，找出x在alls中的下標。
int find(int x) {
    int l = 0, r = alls.size() - 1, m;
    while (l < r) {
        m = l + r >> 1;
        if (alls[m] >= x) r = m;
        else l = m + 1;
    }

    return l + 1;
}

int main() {
    //保存輸入輸出的結果。處理輸入輸出
    int n, m, x, c, l, r;
    cin >> n >> m;

    for (int i = 0;i < n;i++) {
        cin >> x >> c;
        add.push_back({ x,c });
        alls.push_back(x);
    }

    for (int i = 0;i < m;i++) {
        cin >> l >> r;
        query.push_back({ l,r });
        alls.push_back(l), alls.push_back(r);
    }

    //去除重複的坐標值
    sort(alls.begin(), alls.end());
    //unique函數不停的把後面不重複的元素移到前面來，返回最後一個不重複元素的下標
    //erase函數，刪除操作。
    alls.erase(unique(alls.begin(), alls.end()), alls.end());

    //對映射的值進行處理
    for (auto item : add) a[find(item.first)] += item.second;

    //求前綴和
    for (int i = 1;i <= alls.size();i++) s[i] = a[i] + s[i - 1];

    //求區間和
    for (auto item : query)
        cout << s[find(item.second)] - s[find(item.first) - 1] << endl;

    return 0;
}

 

 

 
Tags:

VirMach 便宜 VPS

QNews

QNews