题目大意
给定一个长度为\(n\)的序列\(a\)，保证任何时间序列\(a\)两两不同，\(i\)和\(j\)有边当且仅当\(a_i < a_j\)。询问连通块的个数，带单点修。
做法
step 1 观察性质
结论：若\(i,j\)连通，则\(\forall k \in (i, j), i, j\)和\(k\)连通。
$\mathcal{proof} : $ 分讨：
-
\(a_i < a_j\) 这种情况很显然， 若\(a_i < a_k\)则\(i\)一定和\(k\)连通，否则即\(a_i > a_k\),那么\(a_k < a_j\),那么\(k,j\)连通
-
\(a_i > a_j\), 继续分讨：
\(\mathcal{A} : \exist x<i,a_x<a_j<a_i\) : 若\(a_k<a_x,k\)和\(j\)之间有边；否则\(x, k\)有边
\(\mathcal{B} : \exist x>j,a_j<a_i<a_x\) : 若\(a_k>a_x,k\)和\(i\)之间有边；否则\(x, k\)有边
\(\mathcal{Q.E.D}\)
这个没想到。。
问题转化
所以发现每次的计算变成了\(\sum \limits_{pos} [[1, pos]\text{和}[pos + 1, n]\text{没有边}]\)
等价于\(\sum \limits_{pos} [\forall x\in [1, pos], y \in [pos + 1, n], a_x > a_y]\)
还等价于\(\sum \limits_{pos} [\min \limits_{i=1}^{pos} a_i > \max \limits_{i=pos+1}^{n} a_i]\)
套路的，记\(mx =\max\limits_{i=pos+1}^{n} a_i\), 将\(\le mx\)的设为\(0\), 剩下的设为\(1\), 一个\(pos\)会产生贡献当且仅当转化后的\(01\)序列为\(pos\)个\(1\)和\(n - pos\)个\(0\)依次组成的，即：
\[\overset{\text{pos}个1}{\overbrace{1111...1111}}\overset{\text{n-pos}个0}{\overbrace{0000...0000}} \]记录+维护
我们计\(f_{mx}\)为在\(\text{max}=mx\)的序列的\(10\)的个数。考虑建值域线段树，以\(mx\)为下标建线段树维护\(f_{mx}\)的值。
加入一个数的时候相当于将\([min(a_i,a_{i+1}),max(a_i,a_{i+1})]\)之间的\(f_{mx}++\)，因为这些会产生一对\(10\)。
特殊的考虑\(a_0=\infty, a_{n+1}=0\)，这样方便处理边界。
然后我们发现\(\forall mx, f_{mx} > 0\)，而我们原问题是球有多少个\(f_{mx}=1\)的个数，于是直接转化为区间最小值+维护最小值个数。
code
void upd(int x, int v) {change(1, 0, V, Min(a[x], a[x + 1]), Max(a[x], a[x + 1]) - 1, v);}
// in main
read(n, q); rep(i, 1, n) read(a[i]); a[0] = V + 1, a[n + 1] = 0;
rep(i, 1, n)chane_cnt(1, 0, V, a[i], 1); rep(i, 0, n) upd(i, 1);
rep(_, 1, q, x, v) {
read(x, v); upd(x - 1, -1), upd(x, -1), chane_cnt(1, 0, V, a[x], -1);
a[x] = v; upd(x - 1, 1), upd(x, 1), chane_cnt(1, 0, V, a[x], 1); writeln(seg[1].cnt);
}