题目传送门（内部题116）
输入格式
第一行两个整数$n,m$，如题
第二行有$n$个整数表示$h_1-h_n(1\leqslant h_i\leqslant 10^9)$
接下来有$m$行，每行两个整数，$p,H_p$，表示第$p$个位置的苹果实际高度为$H_p$。
输出格式
输出共$m$行，每行一个整数，表示这种修改情况下的答案。
样例
样例输入：
5 3
1 2 3 4 4
1 5
5 5
2 3
样例输出：
1
5
3
数据范围与提示
样例解释：
第一种情况 苹果高度为$5\ 2\ 3\ 4\ 4$，只摘第一个苹果
第二种情况 苹果高度为$1\ 2\ 3\ 4\ 5$，陶陶会摘五个苹果
第三种情况 苹果高度为$1\ 3\ 3\ 4\ 4$，所以会选择$1,2,4$号位置的苹果
数据范围：
对于$20\%$的数据，$n,m\leqslant 5,000$
对于$100\%$的数据，$n,m\leqslant 100,000$。
题解
做法很多，我的做法是线段树维护单调栈。
开场$20$分钟切，就是个板子，没什么好说的了……
时间复杂度：$\Theta(n\log^2n)$。
期望得分：$100$分。
实际得分：$100$分。
代码时刻
#include<bits/stdc++.h>
#define L(x) x<<1
#define R(x) x<<1|1
using namespace std;
int n,m;
int a[200001];
int trmx[500001],trsm[500001];
int pushup(int x,int l,int r,int w)
{
if(l==r)return trmx[x]>w;int mid=(l+r)>>1;
if(trmx[L(x)]<=w)return pushup(R(x),mid+1,r,w);
return trsm[x]-trsm[L(x)]+pushup(L(x),l,mid,w);
}
void pushup(int x,int l,int r)
{
if(trmx[L(x)]<=trmx[R(x)])trmx[x]=trmx[R(x)];
else trmx[x]=trmx[L(x)];int mid=(l+r)>>1;
trsm[x]=trsm[L(x)]+pushup(R(x),mid+1,r,trmx[L(x)]);
}
void add(int x,int l,int r,int k,int w)
{
if(l==r){trmx[x]=w;trsm[x]=1;return;}
int mid=(l+r)>>1;
if(k<=mid)add(L(x),l,mid,k,w);
else add(R(x),mid+1,r,k,w);
pushup(x,l,r);
}
pair<int,int> ask(int x,int l,int r,int k,int w)
{
if(l>n)return make_pair(0,0);
if(k<=l)return make_pair(max(w,trmx[x]),pushup(x,l,r,w));
int mid=(l+r)>>1;
if(mid<k)return ask(R(x),mid+1,r,k,w);
pair<int,int> flag=ask(L(x),l,mid,k,w);
pair<int,int> res=ask(R(x),mid+1,r,k,max(w,flag.first));
res.second+=flag.second;
return res;
}
int main()
{
scanf("%d%d",&n,&m);
for(int i=1;i<=n;i++)
{
scanf("%d",&a[i]);
add(1,1,n,i,a[i]);
}
for(int i=1;i<=m;i++)
{
int p,h;
scanf("%d%d",&p,&h);
add(1,1,n,p,h);
printf("%d\n",ask(1,1,n,1,0).second);
add(1,1,n,p,a[p]);
}
return 0;
}
rp++