题意：给个T，T组数据；
每组给个n，m；n个数，m个操作；
(对序列的操作是，一开始假设你手上东西是-INF，到i=1时拿起1，之后遍历，遇到比手头上的数量大的数时替换(拿到手的算拿走)，问最后拿走几个)
每次操作是将p位变为q；问此时序列能拿走几个数；
思路：假设p位变了，不管变大变小，我们都得知道一件事，就是要找到在p之前最长的序列；
因为这个是不变的，可以预处理，所以说我们就在第i位置记录1~i的最大值，和最大取走的数量以及最大数的id，这样就可以知道p-1位置的信息就是1~p-1位置最大的数的信息，O（1）得到；
（如果q比1~p-1最大的数小，那么就将q变为那个最大的数，因为这样我们就可以不用分情况去查询）
之后就是要找到比q大的第一个数，我是用线段树维护的，找比q大的第一个数的位置；找到了之后你就会希望能得到以这个数为起点的最大可取数量，那么我们就要计算出每个位置开始可以得到的最大数量；实现方法就是倒过来遍历那n个数，每次查询i~n里比a[i]大的第一个数的位置cnt，然后假设记录数组为dp，那么就是dp[i]=dp[cnt]+1；没找到的情况就令这个位置为1
以下是代码实现：
#include<bits/stdc++.h>
#define mid ((node[now].l+node[now].r)>>1)
#define Max(a, b) (a>b?a:b)
using namespace std;
typedef long long ll;
const int N=1e5+, INF=0x3f3f3f3f, mod=;
int dp[N];
struct Node{
int num, id, len;
}maxn[N];
int sav[N];
struct No{
int ret;
struct no{
int l, r, maxn;
}node[N<<];
void build(int L, int R, int now){
node[now].l=L;
node[now].r=R;
if(L==R) node[now].maxn=sav[L];
else{
build(L, mid, now<<);
build(mid+, R, now<<^);
node[now].maxn=Max(node[now<<].maxn, node[now<<^].maxn);
}
}
void querymax(int v, int now, int L, int R){
if(node[now].l==node[now].r){
if(node[now].maxn>v) ret=min(ret, node[now].l);
return ;
}
if(node[now].r<=R&&node[now].l>=L){
if(node[now<<].maxn>v){
querymax(v, now<<, L, R);
}else{
querymax(v, now<<^, L, R);
}
return ;
}
if(L<=mid)
querymax(v, now<<, L, R);
if(R>mid)
querymax(v, now<<^, L, R);
}
}tree;
int main( ){
int T, m, n, p, q;
register int i, j, k, ans, cnt, sav1;
scanf("%d", &T);
while(T--){
scanf("%d%d", &n, &m);
for(i=; i<=n; ++i){
scanf("%d", sav+i);
if(maxn[i-].num<sav[i]){
maxn[i].num=sav[i];
maxn[i].id=i;
maxn[i].len=maxn[i-].len+;
}else{
maxn[i]=maxn[i-];
}
dp[i]=;
}
tree.build(, n, );
for(i=n; i>; --i){
tree.ret=n+;
tree.querymax(sav[i], , i, n);
cnt=tree.ret;
if(cnt>n)
cnt=;
dp[i]=dp[cnt]+;
}
while(m--){
sav1=ans=;
scanf("%d%d", &p, &q);
if(p==){
tree.ret=n+;
tree.querymax(q, , p+, n);
cnt=tree.ret;
if(cnt<=n) printf("%d\n", dp[cnt]+);
else puts("");
continue;
}
ans=maxn[p-].len;
if(q>maxn[p-].num){
++ans;
}else{
q=maxn[p-].num;
}
tree.ret=n+;
tree.querymax(q, , p+, n);
cnt=tree.ret;
if(cnt<=n)
ans+=dp[cnt];
printf("%d\n", ans);
}
}
}
拙略的代码