鏈接：https://ac.nowcoder.com/acm/contest/3566/D
來源：牛客網

---

小翔和泰拉瑞亞

時間限制：C/C++ 1秒，其他語言2秒 空間限制：C/C++ 131072K，其他語言262144K 64bit IO Format: %lld

題目描述

小翔愛玩泰拉瑞亞 。
一天，他碰到了一幅地圖。這幅地圖可以分為n列，第i列的高度為Hi，他認為這個地圖不好看，決定對它進行改造。
小翔又學會了m個魔法，實施第i個魔法可以使地圖的第Li列到第Ri列每一列的高度減少Wi，每個魔法只能實施一次，魔法的區間可能相交或包含。
小翔認為，一幅地圖中最高的一列與最低的一列的高度差越大，這幅地圖就越美觀。
小翔可以選擇m個魔法中的任意一些魔法來實施，使得地圖盡量美觀。但是他不知道該如何選擇魔法，于是他找到了你。請你求出所有可行方案中，高度差的最大值。
對于100%的數據，滿足1≤n,m≤200000,-109≤Hi≤109,1≤Wi≤109,1≤Li≤Ri≤n。

輸入描述:

輸入文件的第一行包含兩個整數n,m。
輸入的第二行包含n個整數，相鄰兩數間用一個空格隔開，第i個整數為Hi。
接下來的m行，每行包含3個整數，分別是Li,Ri,Wi，相鄰兩數間用一個空格隔開。

輸出描述:

一行一個整數，表示高度差的最大值。

示例1

輸入
復制

3 3 7 -2 -10 1 3 4 3 3 4 1 2 8

輸出
復制

21

思路：

區間更新，線段樹去維護。
極差最大，值只減小，考慮固定最小值，然后求整個區間的最大值。
假設i位置上的值是最小值，那么覆蓋了i的區間都可以對i位置上的值變小產生貢獻，即[l,r],l<=i&&r>=i的區間能夠讓假設位置的最小值變小（l<i&&r>=i的在i之前已經使用了但是沒有被撤銷，此時只需使用l=i的區間）。那么此時應該把這些區間都使用一下，然后詢問一下整個區間的最大值。
按上述假設做的正確性很容易證明：如果最大值在使用過的區間里面，因為是同時更新，對結果沒有影響；如果不在使用的區間里面，那更明顯，最小值變小了，最大值沒有受到影響，極差肯定變大！
此時要考慮i+1為最小值了，之前用過的區間對i+1位置沒有貢獻的要撤銷，因為可能影響到最大值。之前使用的區間[l,r]對i+1沒有貢獻的條件是：r<i+1。即在每次使用i+1之前把r=i的區間撤銷。
時間復雜度分析：
影響時間復雜度的是區間操作（不能單純看循環來定時間復雜度）。
對于區間操作，每個區間最多操作2次，每次操作復雜度為logn,
共m個區間，所以時間復雜度為：mlogn

AC代碼:

#include <bits/stdc++.h> #define lson rt<<1,l,mid #define rson rt<<1|1,mid+1,r #define ls rt<<1 #define rs rt<<1|1 using namespace std; typedef long long LL; const LL N = 2e5+5; const LL INF = 0x3f3f3f3f3f3f3f3f; int a[N]; struct Node {LL minx,maxx;LL tag; }node[N<<2]; struct PII {int l,r,v; }; vector<PII> L[N],R[N]; inline void push_up(int rt) {node[rt].minx = min(node[ls].minx,node[rs].minx);node[rt].maxx = max(node[ls].maxx,node[rs].maxx);return; } void build_tree(int rt,int l,int r) {node[rt].tag = 0;if(l == r){node[rt].minx = a[l];node[rt].maxx = a[l];return;}int mid = (l + r) >> 1;build_tree(lson);build_tree(rson);push_up(rt); } inline void push_down(int rt) {if(node[rt].tag){//認真思考，不要少更新了需要維護的值！node[ls].minx += node[rt].tag;node[ls].maxx += node[rt].tag;node[ls].tag += node[rt].tag;node[rs].minx += node[rt].tag;node[rs].maxx += node[rt].tag;node[rs].tag += node[rt].tag;node[rt].tag = 0;}return; } void update_range(int L,int R,int v,int rt,int l,int r) {if(L <= l && r <= R){node[rt].minx += v;node[rt].maxx += v;node[rt].tag += v;return;}push_down(rt);int mid = (l + r) >> 1;if(L <= mid)update_range(L,R,v,lson);if(R > mid)update_range(L,R,v,rson);push_up(rt); } int main() {int n,m;scanf("%d%d",&n,&m);for(int i = 1; i <= n; i++){scanf("%d",&a[i]);}build_tree(1,1,n);PII p;while(m--){scanf("%d%d%d",&p.l,&p.r,&p.v);L[p.l].push_back(p);R[p.r].push_back(p);}LL ans = node[1].maxx - node[1].minx;for(int i = 1; i <= n; i++){int lSize = L[i].size();int rSize = R[i].size();for(int j = 0; j < lSize; j++){update_range(L[i][j].l,L[i][j].r,-L[i][j].v,1,1,n);}ans = max(ans,node[1].maxx - node[1].minx);for(int j = 0; j < rSize; j++){update_range(R[i][j].l,R[i][j].r,R[i][j].v,1,1,n);}}printf("%lld\n",ans);return 0; }

另一種寫法：

#include <bits/stdc++.h> #define lson rt<<1,l,mid #define rson rt<<1|1,mid+1,r #define ls rt<<1 #define rs rt<<1|1 using namespace std; typedef long long LL; const LL N = 2e5+5; const LL INF = 1e18; int a[N]; struct Node {LL minx,maxx;LL tag; }node[N<<2]; struct PII {int l,r,v; }; vector<PII> L[N],R[N]; inline void push_up(int rt) {node[rt].minx = min(node[ls].minx,node[rs].minx);node[rt].maxx = max(node[ls].maxx,node[rs].maxx); } void build(int rt,int l,int r) {node[rt].tag = 0;if(l == r){node[rt].minx = a[l];node[rt].maxx = a[l];return;}int mid = (l + r) >> 1;build(lson);build(rson);push_up(rt); } inline void push_down(int rt) {if(node[rt].tag){node[ls].minx += node[rt].tag;node[ls].maxx += node[rt].tag;node[ls].tag += node[rt].tag;node[rs].minx += node[rt].tag;node[rs].maxx += node[rt].tag;node[rs].tag += node[rt].tag;node[rt].tag = 0;}return; } void update_range(int L,int R,int v,int rt,int l,int r) {if(L <= l && r <= R){node[rt].minx += v;node[rt].maxx += v;node[rt].tag += v;return;}push_down(rt);int mid = (l + r) >> 1;if(L <= mid)update_range(L,R,v,lson);if(R > mid)update_range(L,R,v,rson);push_up(rt); }LL query_min(int L,int R,int rt,int l,int r) {if(L <= l && r <= R){return node[rt].minx;}push_down(rt);int mid = (l + r) >> 1;LL res = INF;if(L <= mid)return min(res,query_min(L,R,lson));if(R > mid)return min(res,query_min(L,R,rson));return res; } LL query_max(int L,int R,int rt,int l,int r) {if(L <= l && r <= R){return node[rt].maxx;}push_down(rt);int mid = (l + r) >> 1;LL res = -INF;if(L <= mid)return max(res,query_max(L,R,lson));if(R > mid)return max(res,query_max(L,R,rson));return res; } int main() {int n,m;scanf("%d%d",&n,&m);for(int i = 1; i <= n; i++){scanf("%d",&a[i]);}build(1,1,n);PII p;while(m--){scanf("%d%d%d",&p.l,&p.r,&p.v);L[p.l].push_back(p);R[p.r].push_back(p);}LL ans = -INF;for(int i = 1; i <= n; i++){int lSize = L[i].size();int rSize = R[i].size();for(int j = 0; j < lSize; j++){update_range(L[i][j].l,L[i][j].r,-L[i][j].v,1,1,n);}/*這里去query_max(1,n,1,1,n)會測試樣例的5%會時間超限，因為update_range的時候，更新結果會push_up上去,此時完全可以不寫query（我寫是因為很久沒寫了，鞏固一下），node[1]上的最值即為需要的值。*/ans = max(ans,node[1].maxx-query_min(i,i,1,1,n));for(int j = 0; j < rSize; j++){update_range(R[i][j].l,R[i][j].r,R[i][j].v,1,1,n);}}printf("%lld\n",ans);return 0; }

總結

以上是生活随笔為你收集整理的小翔和泰拉瑞亚（线段树+思维）的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。