习题解答 | 一维差分与等差数列差分
一，航班预订统计
这里有 n 个航班，它们分别从 1 到 n 进行编号。
有一份航班预订表 bookings ，表中第 i 条预订记录 bookings[i] = [firsti, lasti, seatsi] 意味着在从 firsti 到 lasti （包含 firsti 和 lasti ）的 每个航班 上预订了 seatsi 个座位。
请你返回一个长度为 n 的数组 answer，里面的元素是每个航班预定的座位总数。
示例 1：
输入：bookings = [[1,2,10],[2,3,20],[2,5,25]], n = 5 输出：[10,55,45,25,25] 解释： 航班编号 1 2 3 4 5 预订记录 1 ： 10 10 预订记录 2 ： 20 20 预订记录 3 ： 25 25 25 25 总座位数： 10 55 45 25 25 因此，answer = [10,55,45,25,25]
示例 2：
输入：bookings = [[1,2,10],[2,2,15]], n = 2 输出：[10,25] 解释： 航班编号 1 2 预订记录 1 ： 10 10 预订记录 2 ： 15 总座位数： 10 25 因此，answer = [10,25]
提示：
1 <= n <= 2 * 1041 <= bookings.length <= 2 * 104bookings[i].length == 31 <= firsti <= lasti <= n1 <= seatsi <= 104
import java.util.Arrays;
public class Main{
/*
* 这里有 n 个航班，它们分别从 1 到 n 进行编号。
有一份航班预订表 bookings ，表中第 i 条预订记录 bookings[i] = [firsti, lasti, seatsi] 意味着在从 firsti 到 lasti （包含 firsti 和 lasti ）的 每个航班 上预订了 seatsi 个座位。
请你返回一个长度为 n 的数组 answer，里面的元素是每个航班预定的座位总数。
*
* */
public void diff(int[] diff,int l,int r,int c) {
diff[l] += c;
diff[r+1] -=c;
}
public int[] corpFlightBookings(int[][] bookings, int n) {
int[] arr = new int[n];
int[] diff = new int[n+2];
for (int[] book : bookings) {
diff(diff,book[0],book[1],book[2]);
}
for(int i = 1;i < diff.length;i++) {
diff[i] += diff[i-1];
}
arr = Arrays.copyOfRange(diff, 1, n+1);
return arr;
}
}二，三步必杀
N个柱子排成一排，一开始每个柱子损伤度为0。
接下来勇仪会进行M次攻击，每次攻击可以用4个参数l,r,s,e来描述：
表示这次攻击作用范围为第l个到第r个之间所有的柱子(包含l,r)，对第一个柱子的伤害为s，对最后一个柱子的伤害为e。
攻击产生的伤害值是一个等差数列。若l=1,r=5,s=2,e=10，则对第1~5个柱子分别产生2,4,6,8,10的伤害。
鬼族们需要的是所有攻击完成之后每个柱子的损伤度。
输入格式
第一行2个整数N,M，用空格隔开，下同。
接下来M行，每行4个整数l,r,s,e，含义见题目描述。
数据保证对每个柱子产生的每次伤害值都是整数。
输出格式
由于输出数据可能过大无法全部输出，为了确保你真的能维护所有柱子的损伤度，只要输出它们的异或和与最大值即可。
（异或和就是所有数字按位异或起来的值）
（异或运算符在c++里为^）
输入输出样例
输入 #1复制
5 2 1 5 2 10 2 4 1 1
输出 #1复制
3 10
输入 #2复制
6 2 1 5 2 10 2 4 1 1
输出 #2复制
3 10
说明/提示
样例解释：
样例1：
第一次攻击产生的伤害:2 4 6 8 10
第二次攻击产生的伤害:0 1 1 1 0
所有攻击结束后每个柱子的损伤程度:2 5 7 9 10。
输出异或和与最大值，就是3 10。
样例2：
没有打到第六根柱子，答案不变
数据范围：
本题满分为100分，下面是4个子任务。(x/y)表示(得分/测试点数量)
妖精级(18/3):1⩽n,m⩽1000。这种工作即使像妖精一样玩玩闹闹也能完成吧？
河童级(10/1):s=e,这可以代替我工作吗？
天狗级(20/4):1⩽n⩽105,1⩽m⩽105。小打小闹不再可行了呢。
鬼神级(52/2):没有特殊限制。要真正开始思考了。
以上四部分数据不相交。
对于全部的数据:1⩽n⩽107,1⩽m⩽3×105，1⩽l<r⩽n.
所有输入输出数据以及柱子受损伤程度始终在[0,9×1018]范围内。
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
import java.io.PrintWriter;
import java.io.StreamTokenizer;
public class Main{
public static void set(long[] diff,int l,int r,int a,int b,int d) {
diff[l] += a;
diff[l+1] += d-a;
diff[r+1] -= b+d;
diff[r+2] += b;
}
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StreamTokenizer in = new StreamTokenizer(br);
PrintWriter out = new PrintWriter(new OutputStreamWriter(System.out));
while(in.nextToken() != StreamTokenizer.TT_EOF) {
int n = (int)in.nval;
in.nextToken();
int m = (int)in.nval;
long[] diff = new long[n+3];
for(int i = 0;i < m;i++) {
in.nextToken(); int l = (int)in.nval;
in.nextToken(); int r = (int)in.nval;
in.nextToken(); int a = (int)in.nval;
in.nextToken(); int b = (int)in.nval;
set(diff,l,r,a,b,(b-a)/(r-l));
}
for(int i =1;i < diff.length;i++) {
diff[i] += diff[i-1];
}
for(int i =1;i < diff.length;i++) {
diff[i] += diff[i-1];
}
long max = 0;
long eo = 0;
for(int i=1;i <= n;i++) {
max = Math.max(max, diff[i]);
eo ^= diff[i];
}
out.println(eo + " " + max);
}
out.flush();
out.close();
br.close();
}
}三，Lycanthropy
我们把山顶上的湖泊看作一条长度为 m 的直线，一开始水深都在水平线上，我们视作此时的水深为 '0'
接下来，在一瞬间，小正方形的"朋友"们跳起并扎入水中，导致在入水点的水降低而远离入水点的水升高，注意两个 "朋友" 可能在同一地点入水。
小正方形的每个朋友有一个体积数值 v，当体积为 v 的一个朋友跳入水中，我们设入水点为 i，将会导致 i−v+1 到 i 的水位依次降低 1,2,⋯,v
同样地，第 i 到 i+v−1 的水位会依次降低 v,v−1,⋯,1.
相对应地，i−v 的水位不变， i−v−1 到 i−2∗v 水位依次增加 1,2,⋯,v， i−2∗v 到 i−3∗v+1 水位依次增加 v,v−1,⋯,1
同样，i+v 水位不变，i+v+1 到 i+2∗v 水位增加 1,2,⋯,v，i+2∗v 到 i+3∗v−1 水位依次增加 v,v−1,⋯,1
现在小正方形想要穿过这个湖，他想要知道在这 n 个"朋友"跳入水中后湖上每个节点的水位，你能帮帮它吗？
输入格式
第一行为两个整数 n,m，表示"朋友"的数目与湖泊的宽度。
接下来 n 行，一行两个整数 v,x，表示第 i+1 个朋友的体积与入水点。
输出格式
一行 m 个整数，第 i 个整数表示 i 号位的水深。
输入输出样例
输入 #1复制
1 10 1 5
输出 #1复制
0 0 1 0 -1 0 1 0 0 0
输入 #2复制
2 10 2 6 3 1
输出 #2复制
-2 0 0 0 0 0 2 2 2 2
说明/提示
对于 30% 的数据，n<=50,m<=500
对于 70% 的数据，n<=105,m<=105
对于 100% 的数据，n<=106,m<=106,1<=v<=10000,1<=x<=m
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
import java.io.PrintWriter;
import java.io.StreamTokenizer;
public class Main{
public static int MAXN = 1000001;
public static int OFFSET = 30001;
public static int[] arr = new int[OFFSET + MAXN + OFFSET];
public static int n, m;
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StreamTokenizer in = new StreamTokenizer(br);
PrintWriter out = new PrintWriter(new OutputStreamWriter(System.out));
while (in.nextToken() != StreamTokenizer.TT_EOF) {
n = (int) in.nval;
in.nextToken();
m = (int) in.nval;
for (int i = 0, v, x; i < n; i++) {
in.nextToken(); v = (int) in.nval;
in.nextToken(); x = (int) in.nval;
fall(v, x);
}
build();
int start = OFFSET + 1;
out.print(arr[start++]);
for (int i = 2; i <= m; i++) {
out.print(" " + arr[start++]);
}
out.println();
}
out.flush();
out.close();
br.close();
}
public static void fall(int v, int x) {
set(x - 3 * v + 1, x - 2 * v, 1, v, 1);
set(x - 2 * v + 1, x, v - 1, -v, -1);
set(x + 1, x + 2 * v, -v + 1, v, 1);
set(x + 2 * v + 1, x + 3 * v - 1, v - 1, 1, -1);
}
public static void set(int l, int r, int s, int e, int d) {
arr[l + OFFSET] += s;
arr[l + 1 + OFFSET] += d - s;
arr[r + 1 + OFFSET] -= d + e;
arr[r + 2 + OFFSET] += e;
}
public static void build() {
for (int i = 1; i <= m + OFFSET; i++) {
arr[i] += arr[i - 1];
}
for (int i = 1; i <= m + OFFSET; i++) {
arr[i] += arr[i - 1];
}
}
}