題目

原題

題目背景

語文考試結束了，成績還是一如既往地有問題。

題目描述

語文老師總是寫錯成績，所以當她修改成績的時候，總是累得不行。她總是要一遍遍地給某些同學增加分數，又要注意最低分是多少。你能幫幫她嗎？

輸入格式

第一行有兩個整數 $n$，$p$，代表學生數與增加分數的次數。

第二行有 $n$ 個數，$a_1～a_n$，代表各個學生的初始成績。

接下來 $p$ 行，每行有三個數，$x$，$y$，$z$，代表給第 $x$ 個到第 $y$ 個學生每人增加 $z$ 分。

輸出格式

輸出僅一行，代表更改分數后，全班的最低分。

樣例 #1

樣例輸入 #1

3 2 1 1 1 1 2 1 2 3 1

樣例輸出 #1

2

提示

對于 $40\%$ 的數據，有 $n\le 10^3$。

對于 $60\%$ 的數據，有 $n\le 10^4$。

對于 $80\%$ 的數據，有 $n\le 10^5$。

對于 $100\%$ 的數據，有 $n\le 5\times 10^6$，$p\le n$，學生初始成績 $ \le 100$，$z
\le 100$。

思路

這里的思路是差分。因為直接模擬的話時間會爆。
離散化操作就是生成一個新的數組。每個元素都是由原數組當前位置減去元素組上一個位置得到（$b[i]=a[i]?a[i?1]$）。特別的新的數組第一個元素就是其本身因為第一個元素前面沒有元素。新的數組的前綴和得到的就是原數組。
例如新數組第一個元素和第二個元素相加，第二個元素是第二個和第一個元素的差值，這個差值加上第一個元素原數組第一個元素很明顯就是等于第二元素本身，而新數組里第一個元素和原數組第一個元素恰好相等。同理新數組第三個元素是原數組第三個和第二個元素差值。而新數組第一個和第二個元素相加等于原第二元素，這樣第一二三個元素相加就是等于原數組第三個元素。這就是前綴和等于原數組。
這里的新數組有什么好處呢。好處在于在新數組上任意位置加上某個數，該位置后面元素全會加上這個數。在上面例子中如果在第二個位置減去1，那么根據前綴和計算出來的第二個元素會比原數組小1，而第三個元素也需要加上第二個元素，也就是說第三個元素也會比原數組第三個元素小于1.如果后面還有元素又會繼續小1。
那如果希望某個區間加上某個值，這里只需要在右界減去同一個值。這樣右邊超過區域的位置原本加上的值就會被這個減去的值抵消。這樣可以大大減少時間消耗。因為改一個區域只需要改元素兩個位置。如果是直接模擬區間一旦變大就會消耗大量時間。

代碼

#include<iostream>
using namespace std;
int d[5000001];
int de[5000001];
int main(){int m,n;cin>>n>>m;for(int i=1;i<=n;i++){cin>>d[i];de[i]=d[i]-d[i-1];}int x,y,z;for(int j=1;j<=m;j++){cin>>x>>y>>z;de[x]+=z;			//左邊界加zde[y+1]-=z;			//右邊界減z}int mins=9999999;for(int i=1;i<=n;i++){	//前綴和還原數組d[i]=de[i]+d[i-1];if(d[i]<mins)mins=d[i];}cout<<mins;
}