1.使用二维数组存储x c l r
import java.util.ArrayList;
import java.util.Collections;
import java.util.List;
import java.util.Scanner;
/**
* no.802
* 区间和
*/
public class Main {
public static int N = 300010;
public static List<Integer> alls = new ArrayList<>();
public static void main(String[] args) {
Scanner in = new Scanner(System.in);
int[] a = new int[N]; //映射后的数组
int[] s = new int[N]; //a[i]的前缀和
int n = in.nextInt();
int m = in.nextInt();
int[][] aLine = new int[n + 1][2];
int[][] bLine = new int[m + 1][2];
for (int i = 1; i <=n; i++){
int x = in.nextInt();
int c = in.nextInt();
aLine[i][0] = x;
aLine[i][1] = c;
alls.add(x);
}
for (int i = 1; i <= m; i++){
int l = in.nextInt();
int r = in.nextInt();
bLine[i][0] = l;
bLine[i][1] = r;
alls.add(l);
alls.add(r);
}//读入操作完成
Collections.sort(alls);
// unique(alls); // 其实去不去重,对题目都没有影响,本质上等价于find()函数找到的 是最左边的数值。
//处理之后进行映射操作
for (int i = 1; i <= n; i++){
a[find(aLine[i][0], alls)] += aLine[i][1];
}
for (int i = 1; i <= alls.size(); i++){
s[i] = s[i - 1] + a[i];
}
//查询操作
for (int i = 1; i <=m; i++){
int l = find(bLine[i][0], alls);
int r = find(bLine[i][1], alls);
System.out.println(s[r] - s[l - 1]);
}
}
public static int find(int x, List<Integer> alls){
int l = 0;
int r = alls.size() - 1;
while (l < r){
int mid = l + r >> 1;
if (alls.get(mid) >= x) r = mid;
else l = mid + 1;
}
return l + 1;
}
public static void unique(List<Integer> alls){
for (int i = 1; i < alls.size(); i++){
while (alls.get(i) == alls.get(i - 1)){
alls.remove(i);
}
}
}
}
// 用数组存储x c l r时,就需要时刻注意下标是否正确,下标是否越界
Y总模板
import java.util.ArrayList;
import java.util.Collections;
import java.util.List;
import java.util.Scanner;
/**
* no.802
* 区间和
*/
public class Main {
public static int N = 300010;
public static void main(String[] args) {
Scanner in = new Scanner(System.in);
int n = in.nextInt();
int m = in.nextInt();
List<Integer> alls = new ArrayList<>();
List<Item> xc = new ArrayList<>();
List<Item> lr = new ArrayList<>();
int[] a = new int[N], s = new int[N];
for (int i = 0; i < n; i++){
int x = in.nextInt();
int c = in.nextInt();
xc.add(new Item(x, c));
alls.add(x);
}
for (int i = 0; i < m; i++){
int l = in.nextInt();
int r = in.nextInt();
lr.add(new Item(l, r));
alls.add(l);
alls.add(r);
} // 读入完成
Collections.sort(alls);
// unique(alls);
// 处理后开始映射
for (Item item : xc){
int i = find(item.first, alls);
a[i] += item.second;
}
for (int i = 1; i <= alls.size(); i++){
s[i] += s[i - 1] + a[i];
}
for (Item item : lr){
int l = find(item.first, alls);
int r = find(item.second, alls);
System.out.println(s[r] - s[l - 1]);
}
}
public static int find(int x, List<Integer> alls){
int l = 0;
int r = alls.size() - 1;
while (l < r){
int mid = l + r >> 1;
if (alls.get(mid) >= x) r = mid;
else l = mid + 1;
}
return l + 1;
}
public static void unique(List<Integer> alls){
for (int i = 1; i < alls.size() - 1; i++){ // 从第二个数开始,排序后的第一个数肯定不是重复的
while (alls.get(i) == alls.get(i - 1)){
alls.remove(i);
}
}
}
public static class Item{
int first;
int second;
public Item(int first, int second) {
this.first = first;
this.second = second;
}
}
}
// 用数组做,就会需要时刻注意下标是否正确,下标是否越界
其实这个题目的话不去重的话也是可以的~ 毕竟这个find函数使用 l+r >> 1的模板的话,找到的都是最左边的那个端点,这样一来,无论是+c操作,还是找到l,r左右端点的操作,其实都是作用在相同数的最左边的端点上,就比如:假如有n个数值都是 x (无论是l,r,x)那最后映射到的位置都是 a[i] , a[i + 1], … a[i + x -1],但是find函数找到的都是a[i] 也就是说其他的那些值都为0,所以前缀和依然可以求出区间和。试一下代码,去掉去重这部分,也是能通过的