题目描述
假定有一个无限长的数轴,数轴上每个坐标上的数都是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
观众老爷们,如果本思路对您有帮助,求关注一波~~~
思路
本题是利用离散化的方式,计算区间[1, r]前缀和
举例
3 3 (3个添加操作add(x, c)坐标x上添加c, 3个查询操作,查询[1, r]区间的前缀和)
1 2 (坐标1 添加数2)
3 6 (坐标3 添加数6)
7 5 (坐标7 添加数5)
1 3 (坐标1 坐标3)
4 6 (坐标4 坐标6)
7 8 (坐标7 坐标8)
1.记录所有的坐标位置,并添加到数组中
all = [1, 3, 4, 1, 3, 4, 6, 4, 7]
2.all排序+去重
排序: all = [1, 1, 3, 3, 4, 4, 4, 6, 7]
去重:all = [1, 3, 4, 6, 7]
模板
```
public static void unique(int[] a){
int j = 0;
for(int i = 0; i < size; i ++){
if(i == 0 || a[i] != a[i - 1]){
a[j ++] = a[i];
}
}
size = j; //更新a数组的大小
}
```
3.利用all坐标数组中的离散后的信息,处理离散数据
all = [1, 3, 4, 6, 7] a = [0, 0, 0, 0, 0, 0]
1 2 (坐标1 添加数2)
二分查找,1在all坐标数组中的离散化位置为0 + 1 = 1,a[1] = 0 + 2 = 2
3 6 (坐标3 添加数6)
二分查找,3在all坐标数组中的离散化位置为1 + 1 = 2,a[2] = 0 + 6 = 6
7 5 (坐标7 添加数5)
二分查找,7在all坐标数组中的离散化位置为4 + 1 = 5,a[5] = 0 + 5 = 5
最 终 a = [0, 2, 6, 0, 0, 5]
前缀和 s = [0, 2, 8, 8, 8, 13]
1 3 (坐标1 坐标3)
二分查找,1在all坐标数组中的离散化位置为0 + 1 = 1
3在all坐标数组中的离散化位置为1 + 1 = 2
区间[1, 3] = s[2] - s[0] = 8
4 6 (坐标4 坐标6)
二分查找,4在all坐标数组中的离散化位置为2 + 1 = 3
6在all坐标数组中的离散化位置为3 + 1 = 4
区间[4, 6] = s[4] - s[2] = 0
7 8 (坐标7 坐标8)
二分查找,7在all坐标数组中的离散化位置为4 + 1 = 5
8在all坐标数组中的离散化位置为5 + 1 = 6
区间[1, 3] = s[6] - s[4] = 5
结束,结果为8 0 5
java
import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
import java.io.IOException;
public class Main{
static int n, m;
static int N = 300010; //n + 2m
static int[] alls = new int[N]; //记录离散化的坐标映射值
static int size = 0; //记录alls中的元素个数
static int[] a = new int[N], s = new int[N]; //a存储坐标上(利用离散化的坐标)记录下的值 s记录前缀和
static int[][] add = new int[N][2], query = new int[N][2];
public static void main(String[] args) throws IOException{
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
String[] str = br.readLine().split(" ");
n = Integer.parseInt(str[0]);
m = Integer.parseInt(str[1]);
int oldN = n;
int oldM = m;
int i = 0; //记录x, c
String[] str2;
while(oldN -- != 0){
str2 = br.readLine().split(" ");
int x = Integer.parseInt(str2[0]);
int c = Integer.parseInt(str2[1]);
alls[size ++] = x;
add[i][0] = x;
add[i][1] = c;
i++;
}
String[] str3;
i = 0;
while(oldM -- != 0){
str3 = br.readLine().split(" ");
int l = Integer.parseInt(str3[0]);
int r = Integer.parseInt(str3[1]);
alls[size ++] = l;
alls[size ++] = r;
query[i][0] = l;
query[i][1] = r;
i ++;
}
//排序, 去重
quickSort(alls, 0, size - 1);
unique(alls);
//处理输入
for(i = 0; i < n; i ++){
int x = find(add[i][0]);//离散化后的坐标值
a[x] += add[i][1];
}
//预处离散化的前缀和
for(i = 1; i <= size; i ++) {
s[i] = s[i - 1] + a[i];
}
//处理查询
for(i = 0; i < m; i ++){
int l = find(query[i][0]);
int r = find(query[i][1]);
int res = s[r] - s[l - 1];
bw.write(res + " ");
bw.write("\n");
}
bw.flush();
br.close();
bw.close();
}
public static int find(int x){
int l = 0, r = size - 1;
while(l < r){
int mid = l + r >> 1;
if(alls[mid] >= x) r = mid;
else l = mid + 1;
}
return r + 1; //方便计算前缀和 s
}
//排序 -> 快排
public static void quickSort(int[] a, int l, int r){
if(l >= r) return;
int x = a[l + r >> 1], i = l - 1, j = r + 1;
while(i < j){
do i ++; while(a[i] < x);
do j --; while(a[j] > x);
if(i < j){
int tmp = a[i];
a[i] = a[j];
a[j] = tmp;
}
}
quickSort(a, l, j);
quickSort(a, j + 1, r);
}
//去重
public static void unique(int[] a){
int j = 0;
for(int i = 0; i < size; i ++){
if(i == 0 || a[i] != a[i - 1]){
a[j ++] = a[i];
}
}
size = j; //更新a数组的大小
}
}
python
N = 300010 #n + 2m
alls = list()
a = [0] * N
s = [0] * N
add = [[0] * 2 for i in range(N)]
query = [[0] * 2 for i in range(N)]
size = 0 #统计alls中的坐标个数
def quickSort(a, l, r):
if(l >= r):
return
x, i, j = a[l + r >> 1], l - 1, r + 1
while(i < j):
while(True):
i += 1
if(a[i] >= x): break
while(True):
j -= 1
if(a[j] <= x): break
if(i < j):
tmp = a[i]
a[i] = a[j]
a[j] = tmp
quickSort(a, l, j)
quickSort(a, j + 1, r)
def unique(a):
global size
i, j = 0, 0
while(i < size):
if(i == 0 or a[i] != a[i - 1]):
a[j] = a[i]
j += 1
i += 1
size = j
def find(x):
global alls
l, r = 0, size - 1
while(l < r):
mid = l + r >> 1
if(alls[mid] >= x): r = mid
else: l = mid + 1
return r + 1
def main():
global alls, a, s, add, query, size
n, m = list(map(int, input().split()))
oldn, oldm = n, m
i = 0
while(oldn):
x, c = list(map(int, input().split()))
alls.append(x)
add[i][0] = x
add[i][1] = c
i += 1
oldn -= 1
i = 0
while(oldm):
l, r = list(map(int, input().split()))
alls.append(l)
alls.append(r)
query[i][0] = l
query[i][1] = r
i += 1
oldm -= 1
size = len(alls)
#排序 和 去重
quickSort(alls, 0, size - 1)
unique(alls)
alls = alls[:size]
for i in range(n):
x = add[i][0]
c = add[i][1]
index = find(x)
a[index] += c
for i in range(size):
s[i + 1] = s[i] + a[i + 1]
for i in range(m):
l = find(query[i][0]);
r = find(query[i][1]);
print(s[r] - s[l - 1])
main()
c++
#include <iostream>
#include <cstring>
#include <algorithm>
using namespace std;
typedef pair<int, int> PII;
const int N = 300010;
int n, m;
int a[N], s[N];
vector<int> alls; // 统计所有坐标
vector<PII> add, query; // add 坐标x上加上C, query查看区间上的和
// alls中保存了所有的坐标信息(排序好的坐标)
// 将排序好坐标数组上0,1, 2, 3坐标,利用二分查找快速找到
int find(int x)
{
int l = -1, r = alls.size();
while(l + 1 != r)
{
int mid = l + r >> 1;
if(alls[mid] < x) l = mid;
else r = mid;
}
//返回>=x的第一个,为了方便前缀和计算,加1
return r + 1; // 0,1,2,3,4...变成1,2,3,4,5...
}
vector<int>::iterator unique(vector<int> &a)
{
int j = 0;
for (int i = 0; i < a.size(); i ++ )
{
if(i==0 || a[i]!=a[i - 1]) a[j ++] = a[i];
}
return a.begin() + j;
}
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);
}
//对alls中的所有坐标都进行排序和去重
sort(alls.begin(), alls.end());
//unique(alls.begin(), alls.end()) 去重,并返回排序好后最后一个元素的地址
//erase(start, end) 擦除数组中的(l, r)区间的元素
alls.erase(unique(alls.begin(), alls.end()), alls.end());
for(auto item : add)
{
int x = find(item.first); //查找要插入位置对应的离散化后的坐标
a[x] += item.second; //在相应坐标下插入元素
}
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;
}
}
对不起, 从这里就没有看懂了,为什么把坐标和增加的数字放在一个数组里面?
1.记录所有的坐标位置,并添加到数组中
all = [1, 3, 4, 1, 3, 4, 6, 4, 7]
好久没上线了,这个是未来方便后面操作使用
针不戳
思路中的alls数组有错误