藍橋杯之差分題型

一維差分

問題描述

給定一個長度為?nn?的序列?aa。

再給定?mm?組操作，每次操作給定?33?個正整數?l,r,dl,r,d，表示對?al～ral～r??中的所有數增加?dd。

最終輸出操作結束后的序列?aa。

Update：由于評測機過快，n,mn,m?于 2024-12-09 從?105105?加強至?2×1052×105，杜絕暴力通過本題。?

輸入格式

第一行輸入兩個正整數?n,mn,m。（1≤n,m≤2×1051≤n,m≤2×105）

第二行輸入?nn?個正整數?aiai?。（1≤i≤n,1≤ai≤1041≤i≤n,1≤ai?≤104）。

接下來?mm?行，每行輸入?33?個正整數?l,r,dl,r,d。（1≤l≤r≤n,?104≤d≤1041≤l≤r≤n,?104≤d≤104）。

輸出格式

輸出?nn?個整數，表示操作結束后的序列?aa。

樣例輸入

6 3
1 2 2 1 2 1
1 3 1
3 5 1
1 6 1

樣例輸出

3 4 5 3 4 2

思路解析

1.?輸入數據

讀取數組的長度 n 和操作的次數 m。
創建兩個數組：
- a：存儲原始數組的值。
- sum：差分數組，用于記錄每個位置的變化。

2.?構建差分數組

遍歷數組 a，計算差分數組 sum：
sum[i]=a[i]?a[i?1]
- 解釋：
  - 差分數組 sum 的每個位置存儲了當前元素與前一個元素的差值。
  - 通過差分數組，可以高效地對區間進行加法操作。

3.?處理區間加法操作

對于每次操作，指定區間 [l,r] 和值 tmp：
- 在差分數組 sum 中：
  - sum[l] += \text{tmp}：表示從位置 l 開始的區間增加 tmp。
  - sum[r+1] -= \text{tmp}：表示在位置 r+1 之后的區間減去 tmp，以抵消前面的增加操作。
- 注意：如果 r+1 超出數組范圍，則不需要減去 tmp。

4.?恢復原始數組

遍歷差分數組 sum，恢復更新后的數組 a：
a[i]=a[i?1]+sum[i]
- 解釋：
  - 通過累加差分數組的值，可以恢復每個位置的最終值。

5.?輸出結果

輸出更新后的數組 a

?代碼實現

import java.util.Scanner;public class Main {public static void main(String[] args) {Scanner scan = new Scanner(System.in);// 讀取數組長度和操作次數int n = scan.nextInt();int m = scan.nextInt();// 創建數組存儲原始數組和差分數組int[] a = new int[n + 1];int[] sum = new int[n + 1];// 輸入數組并構建差分數組for (int i = 1; i <= n; i++) {a[i] = scan.nextInt();sum[i] = a[i] - a[i - 1];}// 處理區間加法操作for (int i = 1; i <= m; i++) {int l = scan.nextInt();int r = scan.nextInt();int tmp = scan.nextInt();// 對區間 [l, r] 進行更新sum[l] += tmp;if (r + 1 <= n) {sum[r + 1] -= tmp;}}// 恢復更新后的數組for (int i = 1; i <= n; i++) {a[i] = a[i - 1] + sum[i];System.out.print(a[i] + " ");}scan.close();}
}

總結

核心思路：
- 利用差分數組高效地處理區間加法操作。
- 通過差分數組的累加恢復最終的數組。
關鍵步驟：
- 構建差分數組：
  sum[i]=a[i]?a[i?1]
- 處理區間加法：
  sum[l]+=tmpsum[r+1]?=tmp(如果?r+1≤n)
- 恢復數組：
  a[i]=a[i?1]+sum[i]
優點：
- 時間復雜度：每次區間加法操作的時間復雜度為 O(1)，恢復數組的時間復雜度為 O(n)。
- 空間復雜度：額外空間復雜度為 O(n)。

二維差分

問題描述

給定一個?n×mn×m?大小的矩陣?AA。

給定?qq?組操作，每次操作為給定?55?個正整數?x1,y1,x2,y2,dx1?,y1?,x2?,y2?,d，Ax1,y1Ax1?,y1???是子矩陣左上角端點，Ax2,y2Ax2?,y2???是子矩陣右下角端點，你需要給其中每個元素都增加?dd。

輸出操作結束后的矩陣?AA。

輸入格式

第一行輸入?33?個正整數?n,m,qn,m,q。（1≤n,m≤103,1≤q≤1051≤n,m≤103,1≤q≤105）

接下來?nn?行每行輸入?mm?個整數，表示?Ai,jAi,j?。(?103≤Ai,j≤103,1≤i≤n,1≤j≤m)(?103≤Ai,j?≤103,1≤i≤n,1≤j≤m)

接下來?qq?行，每行輸入?55?個正整數?x1,y1,x2,y2,dx1?,y1?,x2?,y2?,d。(1≤x1≤x2≤n,1≤y1≤y2≤m,?103≤d≤103)(1≤x1?≤x2?≤n,1≤y1?≤y2?≤m,?103≤d≤103)

輸出格式

輸出?nn?行?mm?個整數，表示操作結束后的矩陣?AA。

樣例輸入

樣例輸出

2 3 4 1
4 3 4 1
2 2 2 2

思路解析

1.?輸入數據

讀取矩陣的行數 n 和列數 m，以及操作的次數 q。
創建兩個二維數組：
- a：存儲原始矩陣的值。
- sum：差分數組，用于記錄每個位置的變化。

2.?構建差分數組

遍歷矩陣 a，計算差分數組 sum：
sum[i][j]=a[i][j]?a[i?1][j]?a[i][j?1]+a[i?1][j?1]
- 解釋：
  - 差分數組 sum 的每個位置存儲了當前元素與相鄰元素的差值。
  - 通過差分數組，可以高效地對區間進行加法操作。

3.?處理區間加法操作

對于每次操作，指定區間 [x1,y1] 到 [x2,y2] 和值 tmp：
- 在差分數組 sum 中：
  - sum[x1][y1] += \text{tmp}：表示從位置 [x1,y1] 開始的區間增加 tmp。
  - sum[x2+1][y1] -= \text{tmp}：表示在位置 [x2+1,y1] 之后的區間減去 tmp，以抵消前面的增加操作。
  - sum[x1][y2+1] -= \text{tmp}：表示在位置 [x1,y2+1] 之后的區間減去 tmp，以抵消前面的增加操作。
  - sum[x2+1][y2+1] += \text{tmp}：表示在位置 [x2+1,y2+1] 之后的區間加上 tmp，以抵消前面的減法操作。
- 注意：如果某個位置超出矩陣范圍，則不需要進行操作。

4.?恢復原始矩陣

遍歷差分數組 sum，恢復更新后的矩陣 a：
a[i][j]=a[i?1][j]+a[i][j?1]?a[i?1][j?1]+sum[i][j]
- 解釋：
  - 通過累加差分數組的值，可以恢復每個位置的最終值。

5.?輸出結果

輸出更新后的矩陣 a。

代碼實現

import java.util.*;public class Main {static final int N = 1000 + 10;static int[][] a = new int[N][N];static int[][] sum = new int[N][N];// 差分操作函數public static void f(int x1, int y1, int x2, int y2, int tmp) {sum[x1][y1] += tmp;sum[x2 + 1][y1] -= tmp;sum[x1][y2 + 1] -= tmp;sum[x2 + 1][y2 + 1] += tmp;}public static void main(String[] args) {Scanner sc = new Scanner(System.in);// 讀取矩陣的行數、列數和操作次數int n = sc.nextInt();int m = sc.nextInt();int q = sc.nextInt();// 輸入矩陣并構建差分數組for (int i = 1; i <= n; i++) {for (int j = 1; j <= m; j++) {a[i][j] = sc.nextInt();sum[i][j] = a[i][j] - a[i - 1][j] - a[i][j - 1] + a[i - 1][j - 1];}}// 處理區間加法操作while (q-- > 0) {int x1 = sc.nextInt();int y1 = sc.nextInt();int x2 = sc.nextInt();int y2 = sc.nextInt();int tmp = sc.nextInt();f(x1, y1, x2, y2, tmp);}// 恢復矩陣并輸出結果for (int i = 1; i <= n; i++) {for (int j = 1; j <= m; j++) {a[i][j] = a[i - 1][j] + a[i][j - 1] - a[i - 1][j - 1] + sum[i][j];System.out.print(a[i][j] + " ");}System.out.println();}sc.close();}
}

總結

核心思路：
- 利用二維差分數組高效地處理區間加法操作。
- 通過差分數組的累加恢復最終的矩陣。
關鍵步驟：
- 構建差分數組：
  sum[i][j]=a[i][j]?a[i?1][j]?a[i][j?1]+a[i?1][j?1]
- 處理區間加法：
  sum[x1][y1]+=tmpsum[x2+1][y1]?=tmpsum[x1][y2+1]?=tmpsum[x2+1][y2+1]+=tmp
- 恢復矩陣：
  a[i][j]=a[i?1][j]+a[i][j?1]?a[i?1][j?1]+sum[i][j]
優點：
- 時間復雜度：每次區間加法操作的時間復雜度為 O(1)，恢復矩陣的時間復雜度為 O(n×m)。
- 空間復雜度：額外空間復雜度為 O(n×m)。

思路解析

1.?輸入數據

讀取棋盤的大小 n 和操作的次數 m。
創建兩個二維數組：
- b：二維差分數組，用于記錄每次翻轉操作的影響。
- s：二維前綴和數組，用于計算每個位置的翻轉次數。

2.?處理翻轉操作

對于每次操作，指定矩形區域 [x1,y1] 到 [x2,y2]：
- 在差分數組 b 中：
  - b[x1][y1] += 1：表示從位置 [x1,y1] 開始的區域增加一次翻轉。
  - b[x2 + 1][y1] -= 1：表示在位置 [x2+1,y1] 之后的區域減去一次翻轉，以抵消前面的增加操作。
  - b[x1][y2 + 1] -= 1：表示在位置 [x1,y2+1] 之后的區域減去一次翻轉，以抵消前面的增加操作。
  - b[x2 + 1][y2 + 1] += 1：表示在位置 [x2+1,y2+1] 之后的區域加上一次翻轉，以抵消前面的減法操作。
- 注意：如果某個位置超出棋盤范圍，則不需要進行操作。

3.?計算二維前綴和

遍歷差分數組 b，計算每個位置的翻轉次數：
s[i][j]=b[i][j]+s[i?1][j]+s[i][j?1]?s[i?1][j?1]
- 解釋：
  - 通過累加差分數組的值，可以計算每個位置的翻轉次數。

4.?確定最終狀態

遍歷二維前綴和數組 s，判斷每個位置的翻轉次數的奇偶性：
- 如果翻轉次數為奇數，表示該位置的顏色被翻轉了奇數次，最終狀態為白色（假設初始狀態為黑色）。
- 如果翻轉次數為偶數，表示該位置的顏色被翻轉了偶數次，最終狀態為黑色。
- 輸出每個位置的最終狀態。

代碼實現

import java.util.Scanner;public class Main {static final int N = 2000 + 10; // 假設最大值為2000，加上一些緩沖static int[][] b = new int[N][N]; // 二維差分數組，用于記錄翻轉操作的影響static int[][] s = new int[N][N]; // 二維前綴和數組，用于計算每個位置的翻轉次數static int n, m;public static void main(String[] args) {Scanner sc = new Scanner(System.in);// 讀取輸入n = sc.nextInt(); // 棋盤大小m = sc.nextInt(); // 操作次數// 處理每個翻轉操作while (m-- > 0) {int x1 = sc.nextInt();int y1 = sc.nextInt();int x2 = sc.nextInt();int y2 = sc.nextInt();// 更新二維差分數組 bb[x1][y1] += 1;if (x2 + 1 < N) b[x2 + 1][y1] -= 1;if (y2 + 1 < N) b[x1][y2 + 1] -= 1;if (x2 + 1 < N && y2 + 1 < N) b[x2 + 1][y2 + 1] += 1;}// 計算二維前綴和并確定最終狀態for (int i = 1; i <= n; i++) {for (int j = 1; j <= n; j++) {// 計算二維前綴和s[i][j] = b[i][j] + s[i - 1][j] + s[i][j - 1] - s[i - 1][j - 1];// 判斷翻轉次數的奇偶性，確定最終顏色System.out.print(s[i][j] % 2);}System.out.println(); // 換行}sc.close(); // 關閉輸入流}
}

總結

核心思路：
- 利用二維差分數組高效地處理區間翻轉操作。
- 通過二維前綴和數組計算每個位置的翻轉次數，判斷奇偶性確定最終狀態。
關鍵步驟：
- 處理翻轉操作：
  b[x1][y1]+=1b[x2+1][y1]?=1b[x1][y2+1]?=1b[x2+1][y2+1]+=1
- 計算二維前綴和：
  s[i][j]=b[i][j]+s[i?1][j]+s[i][j?1]?s[i?1][j?1]
- 確定最終狀態：
  最終狀態=s[i][j]%2
優點：
- 時間復雜度：每次翻轉操作的時間復雜度為 O(1)，計算前綴和的時間復雜度為 O(n2)。
- 空間復雜度：額外空間復雜度為 O(n2)。