G. The Great Equalizer

通过分析之后得知，每次询问的答案就是当前数组中的最大值和当下数组排序后相邻元素差值的最大值之和。

接下来考虑如何维护数组。这会想到用一颗二叉平衡搜索树来实现。这样的一颗树在STL里已经用multiset封装好了，直接使用即可。

创建两个辅助函数add(int x) 和del(int x)，表示数组中的元素改变。

jls的代码。

 1 #include<bits/stdc++.h>
 2 using namespace std;
 3 
 4 void solve(){
 5     int n;
 6     cin >> n;
 7     vector<int> a(n);
 8     for(int i = 0; i < n; i++){
 9         cin >> a[i];
10     }
11 
12     multiset<int> s, d{0};
13     auto add = [&](int x){
14         auto it = s.insert(x);
15         auto r = next(it);
16         if(it != s.begin()){
17             d.insert(x - *prev(it));
18         }
19         if(r != s.end()){
20             d.insert(*r - x);
21         }
22         if(it != s.begin() && r != s.end()){
23             d.extract(*r - *prev(it));
24         }
25     };
26     auto del = [&](int x){
27         auto it = s.find(x);
28         auto r = next(it);
29         if(it != s.begin()){
30             d.extract(x - *prev(it));
31         }
32         if(r != s.end()){
33             d.extract(*r - x);
34         }
35         if(it != s.begin() && r != s.end()){
36             d.insert(*r - *prev(it));
37         }
38         s.extract(x);
39         //s.erase(it);
40     };
41 
42     for(int i = 0; i < n; i++){
43         add(a[i]);
44     }
45 
46     int q;
47     cin >> q;
48     while(q--){
49         int i, x;
50         cin >> i >> x;
51         i--;
52         del(a[i]);
53         a[i] = x;
54         add(a[i]);
55         int ans = *s.rbegin() + *d.rbegin();
56         cout << ans << " ";
57     }
58     cout << endl;
59 }
60 
61 int main(){
62     int t;
63     cin >> t;
64     while(t--){
65         solve();
66     }
67     return 0;
68 }