题意（FJUT翻译HDU）：
钱陶陶家门前有一棵苹果树。 秋天来了，树上的n个苹果成熟了，淘淘会去采摘这些苹果。
到园子里摘苹果时，淘淘将这些苹果从第一个苹果扫到最后一个。 如果当前的苹果是第一个苹果，或者它严格高于之前选择的苹果，那么淘淘将采摘这个苹果; 否则，他不会选择。
题目来了：已知这些苹果的高度为h1，h2，⋯，hn，您需要回答一些独立的查询。 每个查询是两个整数p，q，表示如果第p个苹果的高度修改为q，询问当前淘淘将摘到的苹果的数量。 你能解决这个问题吗？
思路：pre表示1~i的最大连续答案，tail代表i~n的最大连续答案。最终答案为p前，p，p后三部分的贡献和。
预处理pre和tail。tail从后往前预处理，用二分（线段树）查找第一个比i位置大的数。
然后每次找p前最大值下标preMax，ans += pre[preMax]，为p前贡献。
ans += q > a[preMax]，为p的贡献。
查找p后第一个大于前面所有数的值的下标tailMax，ans += tail[tailMax]，为p后贡献。
三者贡献和为总贡献。
二分查找p后第一个大于前面所有数的值的下标一顿好写啊（微笑
思考了半天发现是线段树写错了。显然（？）只有在L <= l && R >= r（就是说当前区间是查询区间子集）才能直接剪枝选择左儿子或者右儿子。
代码：
#include<set>
#include<map>
#include<stack>
#include<cmath>
#include<queue>
#include<vector>
#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>
typedef long long ll;
using namespace std;
const int maxn = + ;
const int seed = ;
const ll MOD = 1e9 + ;
const ll INF = 0x3f3f3f3f;
int n;
ll a[maxn];
ll pre[maxn], tail[maxn], Max[maxn << ];
//1~i最多递增,i~n最多递增
void build(int l, int r, int rt){
if(l == r){
Max[rt] = a[l];
return;
}
int m = (l + r) >> ;
build(l, m, rt << );
build(m + , r, rt << | );
Max[rt] = max(Max[rt << ], Max[rt << | ]);
}
int tailMax, preMax;
void queryPre(int l, int r, int L, int R, int rt){
if(R == ) return;
if(l == r){
if(a[l] > a[preMax]) preMax = l;
return;
}
int m = (l + r) >> ;
if(L <= l && R >= r){
if(Max[rt << ] > Max[rt << | ])
queryPre(l, m, L, R, rt << );
else
queryPre(m + , r, L, R, rt << | );
return;
}
if(L <= m)
queryPre(l, m, L, R, rt << );
if(R > m)
queryPre(m + , r, L, R, rt << | );
}
void queryTail(int l, int r, int L, int R, int rt, ll v){
if(L == n + ) return;
if(l == r){
if(Max[rt] > v) tailMax = min(l, tailMax);
return;
}
int m = (l + r) >> ;
if(L <= l && R >= r){
if(Max[rt << ] > v){
queryTail(l, m, L, R, rt << , v);
}
else if(Max[rt << | ] > v){
queryTail(m + , r, L, R, rt << | , v);
}
return;
}
if(Max[rt << ] > v && L <= m){
queryTail(l, m, L, R, rt << , v);
}
if(Max[rt << | ] > v && R > m){
queryTail(m + , r, L, R, rt << | , v);
}
}
int main(){
int m, T;
scanf("%d", &T);
while(T--){
scanf("%d%d", &n ,&m);
ll u = ;
pre[] = ;
a[] = ;
for(int i = ; i <= n; i++){
scanf("%lld", &a[i]);
if(a[i] > u){
u = a[i];
pre[i] = pre[i - ] + ;
}
else{
pre[i] = pre[i - ];
}
}
build(, n, );
for(int i = n; i >= ; i--){
tailMax = INF;
queryTail(, n, i + , n, , a[i]);
if(tailMax == INF) tail[i] = ;
else tail[i] = + tail[tailMax];
}
while(m--){
int p;
ll q;
scanf("%d%lld", &p, &q);
ll ans = ;
preMax = ;
queryPre(, n, , p - , );
ans += pre[preMax];
if(q > a[preMax]){
ans += ;
}
tailMax = INF;
queryTail(, n, p + , n, , max(a[preMax], q));
if(tailMax != INF) ans += tail[tailMax];
printf("%lld\n", ans);
}
}
return ;
}