闲话

首先要坦白一下，我之所以突然说要使用分块是因为我单纯想搞事情而已。

但是在我真正的写出来之后，我发现其实分块真的简单。

思路

容易发现，题目其实查询的就是从第 $1$ 项开始的上升的斜率的长度。

考虑使用万能的分块，将 $\sqrt{n}$ 设为一块，给每一个块i开一个 vector 储存从这个块开始看可以看到的斜率。

对于修改操作，直接清空 vector，接着遍历整个块。开一个变量储存当前最大的斜率，如果遍历到一个点的斜率大于最大值，那么将这个斜率丢进 vector 并更新最大值。

对于查询操作，将最大值设为 $0$。依次遍历所有的块，对每个块的 vector 进行二分，得到大于最大值的数量并更新最大值。

修改操作时间复杂度为 $O(\sqrt{n})$，查询操作时间复杂度为 $O(\sqrt{n}\log \sqrt{n})$，所以总共时间复杂度为 $O(m\sqrt{n}\log \sqrt{n})$。

AC Code

#include<bits/stdc++.h>
using namespace std;
const int N=2e5+5,M=5e2+5;
int n,q,m,pos[N],l[N],r[N];
vector<double> v[N];
double a[N];
void pre(){
	m=sqrt(n);
	for(int i=1;i<=m;i++){
		l[i]=(i-1)*m+1;
		r[i]=i*m;
	}
	if(r[m]<n){
		l[++m]=r[m]+1;
		r[m]=n;
	}
	for(int i=1;i<=m;i++){
		for(int j=l[i];j<=r[i];j++){
			pos[j]=i;
		}
	}
}
void change(int x,double val){
	int p=pos[x];
	double mmax=0;
	v[p].clear();
	a[x]=val;
	for(int i=l[p];i<=r[p];i++){
		if(a[i]>mmax){
			mmax=a[i];
			v[p].push_back(a[i]);
		}
	}
}
int zask(int x,double val){
	return v[x].end()-upper_bound(v[x].begin(),v[x].end(),val);
}
int ask(){
	double mmax=0;
	int ans=0;
	for(int i=1;i<=m;i++){
		ans+=zask(i,mmax);
		if(v[i].size()){
			mmax=max(mmax,v[i][v[i].size()-1]);
		}
	}
	return ans;
}
int main(){
	ios::sync_with_stdio(false);
	cin.tie(nullptr);
	cin>>n>>q;
	pre(); 
	for(int i=1,x,v;i<=q;i++){
		cin>>x>>v;
		change(x,v*1.0/x);
		cout<<ask()<<'\n';
	}
	return 0;
}