30分：/kk
60~80分：
考虑分块，我们对每一个块维护一个最大值，再维护一个数组，以及对应的前缀和数组（这里的两个数组都是针对块内部的）。
那么，对于一次修改操作，我们只需要把块内部的东西暴力修改了即可，时间复杂度（是块长）。
对于一次查询操作，我们暴力枚举每一个块，二分找到之前块的最大值所影响到的最靠右的位置，那么这个位置之前的答案就都是，之后的答案用数组求。
时间复杂度。
块取800左右的时候比较快。
加两个小优化可以让这个做法跑的飞快
1.重构块的时候，从修改的那个点开始向后重构，可以缩小一半的重构常数。
2.查询答案的时候，一旦前面的块的最大值整个当前块的最大值，则直接更新答案，不用二分。
这样就满分了。
100分：
一看就是个线段树题。
我们需要在每个节点处，维护一个标记，表示的是。不要问我是怎么想到的，我也不知道。
那么我们考虑怎么push_up。
首先，左儿子显然不用动，因为完全符合要求。
右儿子，我们考虑其左儿子最大值的影响力。
CASE 1：
左儿子内的最大值完整大于右儿子的最大值，那么直接把右儿子在这个节点的贡献改成即可。
CASE 2：
左儿子内的最大值比右儿子的左儿子的最大值小，那么右儿子的右儿子的贡献，显然就是，然后递归累加右儿子的左儿子的贡献。
CASE 3：
左儿子内的最大值比右儿子的左儿子的最大值大，那么右儿子的左儿子的贡献，显然是，然后递归累加右儿子的右儿子的贡献。
比较显然的，一次push_up的复杂度是，总的复杂度是。
懒得写了，题目的跟我的做法稍微有一丢丢不一样，他是把所有节点都更新成了最终答案。
#include <set>
#include <cstdio>
#include <algorithm>
using namespace std;
typedef long long ll;
inline int read() {
int x = 0;
char ch = getchar();
while (ch < '0' || ch > '9') ch = getchar();
while (ch >= '0' && ch <= '9') {
x = x * 10 + ch - '0';
ch = getchar();
}
return x;
}
const int Maxn = 3e5 + 5;
int n, m;
int a[Maxn];
namespace SegmentTree {
#define ls t[o << 1]
#define rs t[o << 1 | 1]
#define mid (l + r >> 1)
#define lc o << 1, l, mid
#define rc o << 1 | 1, mid + 1, r
struct Node {
int siz, mx;
ll sum;
void sets(int x) { mx = sum = x; }
} t[Maxn << 2];
void pushup(int o) {
t[o].mx = max(ls.mx, rs.mx);
t[o].sum = ls.sum + rs.sum;
}
ll update(int o, int l, int r, int w) {
if (t[o].mx <= w)
return 1LL * w * t[o].siz;
if (l == r)
return t[o].mx;
if (ls.mx > w) {
return update(lc, w) + rs.sum;
} else {
return 1LL * w * ls.siz + update(rc, w);
}
}
void build(int o, int l, int r) {
t[o].siz = r - l + 1;
if (l == r) {
return t[o].sets(a[l]);
}
build(lc);
build(rc);
rs.sum = update(rc, ls.mx);
pushup(o);
}
void modify(int o, int l, int r, int p) {
if (l == r) {
t[o].sets(a[l]);
return;
}
if (p <= mid)
modify(lc, p);
else
modify(rc, p);
rs.sum = update(rc, ls.mx);
pushup(o);
}
ll query() { return t[1].sum; }
} // namespace SegmentTree
int main() {
// freopen("seq5.in", "r", stdin);
// freopen("seq5.out", "w", stdout);
n = read();
for (int i = 1; i <= n; ++i) a[i] = read();
using namespace SegmentTree;
build(1, 1, n);
m = read();
for (int i = 1; i <= m; ++i) {
int pos = read();
int val = read();
a[pos] = val;
modify(1, 1, n, pos);
printf("%lld\n", query());
}
return 0;
}