变量设置
Node { // 节点类 用于add 和 query 集合的存储
int first;
int second;
}
// 存储所有的下标 x l r
List<Integer> alls; // List排序 用于存储所有下标 包括x l r (int) 需要进行离散化操作
Set<Integer> set; // set用于去重后 复制给alls集合
// 存储题目所给数据
List<Node> add; // 集合存储 插入操作node(x c)
List<Node> query; // 集合存储 询问node (区间l r)
// 前缀和相关数组
int a[]; // 离散化后的add要添加的数值c
int s[]; // s存储 a的前缀和
样例分析
图片来源于网络
操作思路
1.分别存储相关数据, set自动去重复制给 alls 这个List集合排序
alls = new ArrayList<>(set); // set自动去重, 复制到list
Collections.sort(alls); // list排序 从小到大
2.找到 add
插入操作的 x(下标) 在 排序后的 alls
集合 中的位置
- 并将要添加的数据 加入到 a数组中
for(Node node : add) {
int x = find(node.first);
a[x] += node.second; // 注意: 赋值要加, 可能多次添加
}
- 使用 二分法 查询 x 在
alls
集合中的位置, 减小时间复杂度
static int find(int x) {
int l = 0, r = alls.size() - 1;
while(l < r) {
int mid = (l + r) / 2;
if(alls.get(mid) >= x)
r = mid;
else
l = mid + 1;
}
return r + 1;
}
3.根据生成的 a 数组 构造前缀和数组 s
for(int i = 1; i <= alls.size(); i++)
s[i] = s[i - 1] + a[i];
4.遍历 query
询问的集合, 获取 l r
, 计算 s 输出结果
for(Node node : query) {
int l = find(node.first);
int r = find(node.second);
System.out.println(s[r] - s[l - 1]);
}
Java代码
import java.util.*;
public class Main {
static int n, m;
static List<Node> add, query; // 集合分别存储 操作 询问
static List<Integer> alls; // 存储去重后的 x l r
static Set<Integer> set; // set去重 用于存储所有下标 包括x l r
// a存储 离散化后的add要添加的数值c s存储 a的前缀和
static int a[], s[];
// 二分法 查找x(下标) 在alls集合中的位置
static int find(int x) {
int l = 0, r = alls.size() - 1;
while(l < r) {
int mid = (l + r) / 2;
if(alls.get(mid) >= x)
r = mid;
else
l = mid + 1;
}
return r + 1;
}
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
n = sc.nextInt();
m = sc.nextInt();
// 初始化
add = new ArrayList<>();
query = new ArrayList<>();
set = new HashSet<>();
for(int i = 1; i <= n; i++) {
int x = sc.nextInt();
int c = sc.nextInt();
add.add(new Node(x, c));
set.add(x);
}
for(int i = 1; i <= m; i++) {
int l = sc.nextInt();
int r = sc.nextInt();
query.add(new Node(l, r));
set.add(l);
set.add(r);
}
// 1. 去重
alls = new ArrayList<>(set); // set自动去重, 复制到list
Collections.sort(alls); // list排序 从小到大
a = new int[n + 2*m + 10];
s = new int[n + 2*m + 10];
// 2. 二分 找到add中下标x在alls 的位置
for(Node node : add) {
int x = find(node.first);
a[x] += node.second; // 注意: 赋值要加, 可能多次添加
}
// 3. 初始化a的前缀和
for(int i = 1; i <= alls.size(); i++)
s[i] = s[i - 1] + a[i];
// 4. 遍历查找区间 输出结果
for(Node node : query) {
int l = find(node.first);
int r = find(node.second);
System.out.println(s[r] - s[l - 1]);
}
}
}
// 节点类
class Node {
int first;
int second;
public Node(int first, int second) {
super();
this.first = first;
this.second = second;
}
}