备战蓝桥杯，用JAVA刷洛谷算法题单：【算法2-1】前缀和、差分与离散化

参考

【算法2-1】前缀和、差分与离散化 - 题单 - 洛谷 | 计算机科学教育新生态 (luogu.com.cn)

• P8218 【深进1.例1】求区间和
• P1719 最大加权矩形
• P1314 [NOIP2011 提高组] 聪明的质监员
• P2367 语文成绩
• P3397 地毯
• P1496 火烧赤壁
• P1955 [NOI2015] 程序自动分析
• P1884 [USACO12FEB] Overplanting S
• P2004 领地选择
• P3017 [USACO11MAR] Brownie Slicing G
• P3406 海底高铁
• P1083 [NOIP2012 提高组] 借教室
• P2882 [USACO07MAR] Face The Right Way G
• P4552 [Poetize6] IncDec Sequence
• P3029 [USACO11NOV] Cow Lineup S
• P1904 天际线
• P4375 [USACO18OPEN] Out of Sorts G
• P5937 [CEOI1999] Parity Game

前缀和

前缀和：一般用于解决求区间和的问题。

P8218 【深进1.例1】求区间和

前缀和：用一个数组表示前i个数的和

• 下标:		0 1 2 3 4  5
  1

• 如数组a:	0 1 5 2 4  7
  1

• 则数组b:	0 1 6 8 12 19
  1

• [l,r]的和=b[r]-b[l-1]
  1

递推公式：b[i] = b[i-1]+a[i]

区间和：[l,r]= b[r]-b[l-1]

详细可见题解如下图

一次AC

package _2_1;

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.PrintWriter;
import java.io.StreamTokenizer;

public class P8218 {
	private static StreamTokenizer in;
	private static PrintWriter out;

	public static void main(String[] args) throws IOException {
		in = new StreamTokenizer(new BufferedReader(new InputStreamReader(System.in)));
		out = new PrintWriter(System.out);

		int n = nextInt();
		int[] nums = new int[n + 1];
		// algo 前缀和：用一个数组表示前i个数的和
		/*
		 * 	下标:		0 1 2 3 4  5
		 *  如数组a:	0 1 5 2 4  7
		 *  则数组b:	0 1 6 8 12 19
		 *  [l,r]的和=b[r]-b[l-1]
		 */
		
		int[] sums = new int[n + 1];
		for (int i = 1; i <= n; i++) {
			nums[i] = nextInt();
			sums[i] = sums[i - 1] + nums[i];
		}
		int m = nextInt();
		while (m-- > 0) {
			int l = nextInt();
			int r = nextInt();
			out.println(sums[r]-sums[l-1]);
		}

		out.flush();
		out.close();
	}

	public static int nextInt() throws IOException {
		in.nextToken();
		return (int) in.nval;
	}
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48

P1719 最大加权矩形

二维前缀和：

递推公式：b[i][j] = b[i-1][j]+b[i][j-1]-b[i-1][j-1]+a[i][j]

看上图，每个格子表示b[i][j]，那么求得当前b（从11到ij这一部分的和）可以无非就是上一行的b（表示绿蓝这个部分的和）+左一列的b（表示绿黄这一部分的和）-重叠的左上角b（表示绿色这一部分的和）+当前值（a[i][j]）

得到这个递推公式之后，如果要知道以b[x][y]为左上角和b[i][j]为右下角的矩阵的区间和（想象上图11是xy），只需要减去这个有颜色框的上面部分和左面部分，再加上重复剪掉的部分，如下图所示

区间和：[x,y]~[i,j]=b[i][j]-b[x-1][j]-b[i][y-1]+b[x-1][y-1]

区间和：[x1,y1]~[x2,y2]=b[x2][y2]-b[x1-1][y2]-b[x2][y1-1]+b[x1-1][y1-1]

这里求区间和就要用四重循环咯（所以这道题n不大），注意ij不能xy小，从xy开始遍历，而不是+1，否则就成右下角开始了，少了同一行同一列的遍历。

package _2_1;

import java.util.Scanner;

public class P1719 {
	public static void main(String[] args) {
		Scanner scanner = new Scanner(System.in);

		int n = scanner.nextInt();
		int[][] nums = new int[n + 1][n + 1];

		// algo 前缀和：二维
		// 设b[i][j] 表示以11为左上角，ij为右下角点的这个矩形的所有元素的和
		// 我们可以画图来看就能得到如下的公式
		// 递推公式 b[i][j] = b[i-1][j]+b[i][j-1]-b[i-1][j-1]+a[i][j]
		// 区间和xy,ij b[i][j]-b[x-1][j]-b[i][y-1]+b[x-1][y-1]

		int[][] sum = new int[n + 1][n + 1];
		for (int i = 1; i <= n; i++) {
			for (int j = 1; j <= n; j++) {
				nums[i][j] = scanner.nextInt();
				sum[i][j] = sum[i - 1][j] + sum[i][j - 1] - sum[i - 1][j - 1] + nums[i][j];
			}
		}

		int max = Integer.MIN_VALUE;
		for (int x = 1; x <= n; x++) {
			for (int y = 1; y <= n; y++) {
				// 设定ij分别比xy大(当然同一行同一列是满足的，所以从xy开始遍历，而不是+1，要不然就是右下角开始了，少了一行一列)
				for (int i = x; i <= n; i++) {
					for (int j = y; j <= n; j++) {
						max = Math.max(max, sum[i][j] - sum[x - 1][j] - sum[i][y - 1] + sum[x - 1][y - 1]);
					}
				}
			}
		}

		System.out.println(max);

		scanner.close();
	}
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43

差分

差分：就是当前的值和前一个值得差值。通常差分用于得到多次对连续区间修改值操作后的结果值（区间修改+单点求值，树状数组也可以做）

P2367 语文成绩

递推公式：b[i] = a[i]-a[i-1]

修改区间：b[l]+k,b[r+1]-k

还原数组：a[i] = b[i]+a[i-1]，就是递推公式移相

package _2_1;

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.StreamTokenizer;

public class P2367 {
	private static StreamTokenizer in;

	public static void main(String[] args) throws IOException {
		in = new StreamTokenizer(new BufferedReader(new InputStreamReader(System.in)));
		int n = nextInt();
		int p = nextInt();
		int[] nums = new int[n + 1];
		int[] diffs = new int[n + 1];
		for (int i = 1; i <= n; i++) {
			nums[i] = nextInt();
			// algo 差分
			/*
			 * 问题：一个连续区间，加上同一个数 解决：差分数组b[i] = a[i]-a[i-1] 对于区间[l,r]对差分进行修改：b[l]+k,b[r+1]-k
			 * 还原数组 a[i] = b[i]+a[i-1]
			 * 
			 */
			// 1、计算差分
			diffs[i] = nums[i] - nums[i - 1];
		}
		while (p-- > 0) {
			int x = nextInt();
			int y = nextInt();
			int z = nextInt();
			// 2、修改区间的首末差分值
			diffs[x] += z;
			if (y + 1 <= n)
				diffs[y + 1] -= z;
		}
		// 3、还原数组
		int min = Integer.MAX_VALUE;
		for (int i = 1; i <= n; i++) {
			nums[i] = diffs[i] + nums[i - 1];
			min = Math.min(min, nums[i]);
		}

		System.out.println(min);
	}

	public static int nextInt() throws IOException {
		in.nextToken();
		return (int) in.nval;
	}
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52

P1083 [NOIP2012 提高组] 借教室

二分+差分

package luogu;

import java.util.Arrays;
import java.util.Scanner;

public class P1083 {
	private static int[] starts;
	private static int[] ends;
	private static int[] nums;
	private static int[] diffs;
	private static int[] tempNums;
	private static int[] availableNums;
	private static int n;
	private static int m;

	public static void main(String[] args) {
		Scanner scanner = new Scanner(System.in);
		n = scanner.nextInt();
		m = scanner.nextInt();
		availableNums = new int[n + 5];
		tempNums = new int[n + 5];
		diffs = new int[n + 5];
		nums = new int[m + 5];
		starts = new int[m + 5];
		ends = new int[m + 5];
//		初始化原数组
		for (int i = 1; i <= n; i++) {
			availableNums[i] = scanner.nextInt();
		}
//		记录需求
		for (int i = 1; i <= m; i++) {
			nums[i] = scanner.nextInt();
			starts[i] = scanner.nextInt();
			ends[i] = scanner.nextInt();
		}
//		注意题目要求还要找出需要修改的订单，所以需要根据元数据判断有没有不够租界的，
//		如果每改一次差分就要算一次元数据，则差分无意义
//		如果算完全部差分再算元数据，则找不出需要修改的订单
//		所以使用二分，分区间来算这一部分的临时差分和临时元数据，并判断够不够数量
		int left = 0;
		int right = m + 1;
//		如何找边界值？看极端值m=1，则符合判断0+1<2，m=1进行一次判断，
//		如果符合要求则left=mid，继续往后判断
//		最终如果left==订单数，表示判断到了最后都没问题，还要判断一次m，
//		否则在中间有问题时，right表示出问题的地方
		while (left + 1 < right) {
			int mid = left + (right - left) / 2;
			if (check(mid))
				left = mid;
			else
				right = mid;
		}
		if (left == m) {
			if (check(m)) {
				System.out.println(0);
			}
		} else {
			System.out.println(-1);
			System.out.println(right);
		}
		scanner.close();
	}

//	判断区间内是否够租界
//	注意练习题目，这里的区间能使中间某一个部分（因为天数要连续的算下来），所以区间始终是从1开始
	public static boolean check(int mid) {
//		初始化差分数组和临时结果数据
		Arrays.fill(diffs, 0);
		Arrays.fill(tempNums, 0);
//		计算区间差分
		for (int i = 1; i <= mid; i++) {
			diffs[starts[i]] += nums[i];
			diffs[ends[i] + 1] -= nums[i];
		}
//		还原结果数据，判断是否足够数量
		for (int i = 1; i <= n; i++) {
			tempNums[i] = tempNums[i - 1] + diffs[i];
//			tempsNums表示满足当前要求所需的数量，如果大于可租借数，则表示该区间内有需要修改的订单
			if (tempNums[i] > availableNums[i]) {
				return false;
			}
		}
		return true;
	}
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86

P3397 地毯

二维差分

递推公式： b[i][j]=a[i][j]-a[i-1][j]-a[i][j-1]+a[i-1][j-1]

修改区间：[x,y]~[i,j] b[x][y]+=k,b[x][j+1]-=k,b[i+1][y]-=k,b[i+1][j+1]+=k

修改区间：[x1,y1]~[x2,y2] b[x1][y1]+=k,b[x1][y2+1]-=k,b[x2+1][y1]-=k,b[x2+1][y2+1]+=k

还原数组： a[i][j]=a[i-1][j]a[i][j-1]-a[i-1][j-1]+b[i][j]，就是递推公式移相

第一反应：啊好长，前缀和可以用图像记比较形象，这个有点抽象，但这俩怎么这么像呢？看下面

二维差分 - 知乎 (zhihu.com)

里面提到一点：原矩阵是差分矩阵的前缀和。我敲确实啊！那来比对一下两者的递推公式

• 一维前缀和递推公式：b[i] = b[i-1]+a[i]

• 一维差分递推公式：b[i] = a[i]-a[i-1]

不就是前缀和的a变成了差分的b吗！二维也是如此。

• 二维前缀和递推公式：b[i][j] = b[i-1][j]+b[i][j-1]-b[i-1][j-1]+a[i][j]
• 二维差分递推公式： b[i][j] = a[i][j]-a[i-1][j]-a[i][j-1]+a[i-1][j-1]

那就舒服了，记个前缀和的不就行了，前缀和有图像好记（快去看我画的图）

至于修改区间的推导（我懒）看参考吧。

package _2_1;

import java.util.Scanner;

public class P3397 {
	public static void main(String[] args) {
		Scanner scanner = new Scanner(System.in);
		int n = scanner.nextInt();
		int m = scanner.nextInt();

		int[][] nums = new int[n + 1][n + 1];
		int[][] diffs = new int[n + 1][n + 1];
		// algo 差分：二维
		// b[i][j]=a[i][j]-a[i-1][j]-a[i][j-1]+a[i-1][j-1]
		// 修改区间：[x1,y1]~[x2,y2]
		// b[x1][y1]+=k,b[x1][y2+1]-=k,b[x2+1][y1]-=k,b[x2+1][y2+1]+=k
		// 1、这题差分初始都是0不用计算
		while (m-- > 0) {
			// xy表示左上角，ij表示右下角
			int x1 = scanner.nextInt();
			int y1 = scanner.nextInt();
			int x2 = scanner.nextInt();
			int y2 = scanner.nextInt();
			// 2、修改差分
			diffs[x1][y1] += 1;
			if (y2 + 1 <= n)
				diffs[x1][y2 + 1] -= 1;
			if (x2 + 1 <= n)
				diffs[x2 + 1][y1] -= 1;
			if (y2 + 1 <= n && x2 + 1 <= n)
				diffs[x2 + 1][y2 + 1] += 1;
		}
		// 3、还原数组
		for (int i = 1; i <= n; i++) {
			for (int j = 1; j <= n; j++) {
				nums[i][j] = diffs[i][j] + nums[i - 1][j] + nums[i][j - 1] - nums[i - 1][j - 1];
				System.out.printf("%d ", nums[i][j]);
			}
			System.out.println();
		}
		scanner.close();
	}
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44

哦吼！MLE，只过了20的。对于100%的数据，有n*,*m≤1000，不应该啊？换成一个数组也一样，没解决不是很懂捏/(ㄒoㄒ)/~~。

离散化

P1496 火烧赤壁

这题一看连续区间修改值->差分，然后前缀和还原结果数组。但是注意数据规模

ab对应的是数组下标，直接顶到边界了，但是n的大小并不是很大。所以这题的数据是那种需要开大数组，但是存的有效数据有比较少的，需要使用离散化。

算法——离散化 java实现_java离散化-CSDN博客

八、基础算法——离散化算法_java离散化-CSDN博客

离散化 - Cattle_Horse - 博客园 (cnblogs.com)

算法笔记：离散化的两种实现方式 - 知乎 (zhihu.com)

思想就是把离散的有效值的下标，映射到另一个数组（这个数组不用很大，开到多少个有效值的最大值就行）

然后把原数组存值改为存离散数组的下标，这样找原数组的值就改成找对于离散数组（一般离散数组都要去重+排序），找的话就是二分的找

所以可以看到题解的大佬都是用两个数组来把区间[l,r]值映射到起点数组（存l）和终点数组（存r），这两个映射数组只需要开n的最大值，并且使用int类型（见lr的取值范围）。

将起点和终点按照从小到大的顺序排序，对答案不会产生影响！所以起点数组和终点数组可以分开排序，然后再遍历加上差值。但是注意9-2+11-5还要减去中间重复的部分，所以如果后一个的起点在前一个的终点之前，那就表明有重复的部分（这里注意最后一条线段就不用判断后一个了）

package _2_1;

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.StreamTokenizer;
import java.util.Arrays;

public class P1496 {
	private static StreamTokenizer in;

	public static void main(String[] args) throws IOException {
		in = new StreamTokenizer(new BufferedReader(new InputStreamReader(System.in)));
		int n = nextInt();
		// algo 离散化：把稀疏的下标映射到一个小数组当中
		int[] l = new int[n];
		int[] r = new int[n];
		for (int i = 0; i < n; i++) {
			l[i] = nextInt();
			r[i] = nextInt();
		}
		// 这里如果数组开固定最大值的化，sort会把无效的值也排序，可以指定排序长度
		Arrays.sort(l);
		Arrays.sort(r);
		// algo 排序：Array数组指定范围排序
//		Arrays.sort(l, 0, n);
		int cnt = 0;
		for (int i = 0; i < n; i++) {
			// 左闭右开，所以不用+1
			cnt += r[i] - l[i];
			// 最后区间没有后面的区间了，所以不需要判断是否有重复
			if (i != n - 1) {
				// 如果后面的区间和前面的有重复，就要减去重复的部分
				if (l[i + 1] < r[i]) {
					cnt -= r[i] - l[i + 1];
				}
			}
		}
		System.out.println(cnt);
	}

	public static void fun() throws IOException {
		int n = nextInt();
		// 差分，但是数组开太大不行
		int[] diffs = new int[Integer.MAX_VALUE];
		int min = Integer.MAX_VALUE, max = Integer.MIN_VALUE;
		while (n-- > 0) {
			// 左闭右开
			int a = nextInt();
			int b = nextInt();
			diffs[a] += 1;
			diffs[b] -= 1;
			min = Math.min(min, a);
			max = Math.max(max, b - 1);
		}
		int cnt = 0;
		for (int i = min; i <= max; i++) {
			diffs[i] = diffs[i] += diffs[i - 1];
			if (diffs[i] > 0) {
				cnt++;
			}
		}
		System.out.println(cnt);
	}

	public static int nextInt() throws IOException {
		in.nextToken();
		return (int) in.nval;
	}
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71

P1955 [NOI2015] 程序自动分析

并查集+离散化的题，确实让我更理解离散化了。

要把握把原值改成离散化后数组的下标这一思想的转换（虽然实践起来会有点抽象），然后有几个固定步骤

• 离散化数组，类型要考虑原值下标的最大范围，大小要考虑有效值数量的范围。
• 离散化数组要排序+去重
• 把原值改成对应离散化数组的下标（这样对原数组来说，需要的下标范围不久缩短到离散化数组的下标长度了吗，实现了缩短）
• 以后所有的操作都任然是对原值操作（虽然实际上是对离散化数组下标的操作，但是你要加上这一层转换那就抽象了）
• 最后要获得真正的原值，就拿现有原值取离散化数组取（不过一般需要离散化的题都不会要求最后获取原值的，所以离散化适合那种重点在于对值的操作，而不是值本身）

有几个RE，懒得改了

package _2_1;

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.StreamTokenizer;
import java.util.Arrays;

public class P1955 {
	private static StreamTokenizer in;
	private static int[] f;
	// 离散化数组
	private static long[] nums;
	// 存操作的数组
	private static Op[] ops;
	private static int t;
	private static int n;

	public static void main(String[] args) throws IOException {
		in = new StreamTokenizer(new BufferedReader(new InputStreamReader(System.in)));
		in.nextToken();

		t = (int) in.nval;
		while (t-- > 0) {
			boolean flag = true;
			in.nextToken();
			n = (int) in.nval;
			ops = new Op[n];
			nums = new long[n * 2];

			int index = -1;
			int opNum;
			long x1, x2;
			// 1、读入操作
			for (int i = 0; i < n; i++) {
				in.nextToken();
				x1 = (long) in.nval;
				in.nextToken();
				x2 = (long) in.nval;
				in.nextToken();
				opNum = (int) in.nval;
				ops[i] = new Op(x1, x2, opNum == 1 ? true : false);
				nums[++index] = ops[i].x1;
				nums[++index] = ops[i].x2;
			}

			// 2.1、对离散化数组排序、去重
			Arrays.sort(nums);
			// algo 数组去重：这里nums大小会变化
			nums = Arrays.stream(nums).distinct().toArray();
			// 2.2、把原数组的值改为对应离散化数组的下标
			for (int i = 0; i < n; i++) {
				ops[i].x1 = getIndex(ops[i].x1);
				ops[i].x2 = getIndex(ops[i].x2);
			}

			// 3、把操作1放在前面
			Arrays.sort(ops, (p, q) -> {
				// >0表示交换,把false放到后面
				return p.opNum == false ? 1 : -1;
			});

			// 4.1 并查集初始化
			startF();
			// 开始操作
			for (int i = 0; i < n; i++) {
				// 这里就需要离散化了，因为数组下标只能是int，而x1x2都是long范围
				// 注意此时所有的原值都用离散化后的下标表示，下标！！！，不用考虑原值
				if (ops[i].opNum == true) {
					// 4.2、并查集并入，相等的放在同一个集合中(所以要先执行1操作)
					f[find((int) ops[i].x1)] = find((int) ops[i].x2);
				} else {
					// 5、然后开始遍历不相等的约束条件，如果发现x1x2在同一个集合中（即表示两者约束相等），那么就矛盾
					if (find((int) ops[i].x1) == find((int) ops[i].x2)) {
						System.out.println("NO");
						flag = false;
						break;
					}
				}
			}
			if (flag) {
				System.out.println("YES");
			}
		}
	}

//	并查集初始化
	public static void startF() {
		int len = nums.length;
		f = new int[len];
		for (int i = 0; i < len; i++) {
			f[i] = i;
		}
	}

//	获取值对应的离散化数组的下标
	public static int getIndex(long x) {
		int len = nums.length;
		int l = 0, r = len - 1;
		while (l <= r) {
			int m = l + (r - l) / 2;
			if (nums[m] == x) {
				return m;
			} else if (nums[m] > x) {
				r = m - 1;
			} else {
				l = m + 1;
			}
		}
		return -1;
	}

//	并查集找祖先
	public static int find(int x) {
		if (f[x] != x) {
			f[x] = find(f[x]);
		}
		return f[x];
	}
}

// 存输入三元组
class Op {
	long x1;
	long x2;
	// 1=true
	boolean opNum;

	public Op(long x1, long x2, boolean opNum) {
		super();
		this.x1 = x1;
		this.x2 = x2;
		this.opNum = opNum;
	}

}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137