CS Academy Remove Update

题目链接：https://csacademy.com/contest/round-45/task/remove-update/

题目大意：N个数初始值为0，现在给出Q个操作(l，r，x)，每个操作将区间[l，r]的值加x。倘若除去其中一次更新，那么整个数列的最大值就会改变。问除去一次更新能达到的数列最大值的最小值是多少。

解题思路：线段树区间更新，维护最大值。先进行Q此操作，之后枚举每个操作，执行操作(l，r，-x)，记录最大值，之后执行(l，r，x)还原。

代码：

 1 const int maxn = 1e6 + 5;
 2 struct node{
 3     int v, inc;
 4 };
 5 node tree[maxn];
 6 int n, q;
 7 int al[maxn], ar[maxn], ax[maxn];
 8 
 9 void build(int l, int r, int k){
10     tree[k].v = tree[k].inc = 0;
11     if(l == r) return;
12     int mid = (l + r) >> 1, lc = k << 1, rc = k << 1 | 1;
13     build(l, mid, lc);
14     build(mid + 1, r, rc);
15 }
16 void update(int ul, int ur, int x, int l, int r, int k){
17     if(ul <= l && ur >= r){
18         tree[k].inc += x;
19         return;
20     }
21     if(ul > r || ur < l) return;
22     int mid = (l + r) >> 1, lc = k << 1, rc = k << 1 | 1;
23     tree[k].v = tree[k].v + tree[k].inc;
24     tree[lc].inc += tree[k].inc; tree[rc].inc += tree[k].inc; 
25     tree[k].inc = 0;
26     update(ul, ur, x, l, mid, lc);
27     update(ul, ur, x, mid + 1, r, rc);
28     tree[k].v = max(tree[lc].v + tree[lc].inc, tree[rc].v + tree[rc].inc);
29 }
30 
31 void solve(){
32     build(1, n, 1);
33     for(int i = 1; i <= q; i++){
34         update(al[i], ar[i], ax[i], 1, n, 1);
35     }
36     int ans = inf;
37     for(int i = 1; i <= q; i++){
38         update(al[i], ar[i], -ax[i], 1, n, 1);
39         ans = min(ans, tree[1].v + tree[1].inc);
40         update(al[i], ar[i], ax[i], 1, n, 1);
41     }
42     printf("%d
", ans);
43 }
44 int main(){
45     scanf("%d %d", &n, &q);
46     for(int i = 1; i <= q; i++){
47         int l, r, x;
48         scanf("%d %d %d", &l, &r, &x);
49         al[i] = l; ar[i] = r; ax[i] = x;
50     }
51     solve();
52 }

题目：

Remove Update

Time limit: 1000 ms
Memory limit: 256 MB

You have an array

You have

Given $A_l, A_{l+1},..., A_rAl,Al+1,...,Ar$

You can choose to skip exactly one of the updates. In the end you want the maximum element of

Standard input

The first line contains two integers

Each of the next

Standard output

Print on the first line the smallest maximum value you can get by skipping one update.

Constraints and notes

$10^51≤N≤105$
$10^51≤Q≤105$
$10^91≤x≤109$
It is guaranteed that if you perform all the updates $A_i leq 10^9Ai≤109$

Input	Output
4 2 1 3 1 2 4 1	1
4 3 2 4 2 1 2 2 3 4 1	2
6 4 2 3 1 4 6 2 3 4 3 1 4 2	4