0分代码

// Problem: P11021 「LAOI-6」区间测速
// Contest: Luogu
// URL: https://www.luogu.com.cn/problem/P11021
// Memory Limit: 512 MB
// Time Limit: 1000 ms
// 
// Powered by CP Editor (https://cpeditor.org)

#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<vector>
#include<queue>
#include<stack>
#include<deque>
#include<set>
#include<map>
#include<cmath>
#include<bitset>
#include<list>
#define rint register int
#define mem(a,b) memset(a,b,sizeof a)
#define lowbit(x) (x&-x)
#define debug(a,b) cout<<"line"<<__LINE__<<":"<<a<<" = "<<b<<endl;
#define eb emplace_back
#define pb push_back
#define read raed
#define int long long
#define ls (p<<1)
#define rs (p<<1|1)
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef pair<int,int> pii;
const int inf=0x3f3f3f3f;
const ll INF=1e18;
const int N=1e5+8;
template<typename T>
void read(T &x){
    x=0;int f=1;char c=getchar();
    while(!isdigit(c)){if(c=='-') f=-1;c=getchar();}
    while(isdigit(c)){x=x*10+c-'0';c=getchar();}
    x*=f;
}
template<typename T,typename ... Args>
void read(T &x, Args &... y){read(x);read(y...);}
int n,m;
int a[N],pos[N];
struct tree{
	int mx;
	#define mx(p) t[p].mx
}t[N*4];
struct node{
	int x,y,id;
}b[N];
inline void update(int p){mx(p)=max(mx(ls),mx(rs));}
void build(int p,int l,int r){
	mx(p)=-inf;
	if(l==r){
		mx(p)=a[l];
		return ;
	}
	int mid=l+r>>1;
	build(ls,l,mid);build(rs,mid+1,r);
	update(p);
}
void change(int p,int l,int r,int x,int k){
	if(l==r&&l==x){mx(p)=k;return ;}
	int mid=l+r>>1;
	if(x<=mid) change(ls,l,mid,x,k);
	else change(rs,mid+1,r,x,k);
	update(p);
}
inline int get(int i){
	return floor(abs(b[i].x-b[i-1].x))/floor(abs(b[i].y-b[i-1].y));
}
signed main(){
	read(n,m);
	for(rint i=1;i<=n;i++) read(b[i].x,b[i].y),b[i].id=i;
	sort(b+1,b+1+n,[](node A,node B){return A.y>B.y;});
	for(rint i=1;i<=n;i++){
		pos[b[i].id]=i;
		if(i>1) a[i-1]=get(i);
	}
	build(1,1,n-1);
	for(rint i=1,u,v;i<=m;i++){
		read(u,v);u=pos[u];
		int tmp=b[u].y;b[u].y=v;
		if(u>1) change(1,1,n-1,u-1,get(u));
		if(u<n) change(1,1,n-1,u,get(u+1));
		printf("%lld\n",mx(1));
		b[u].y=tmp;
		if(u>1) change(1,1,n-1,u-1,get(u));
		if(u<n) change(1,1,n-1,u,get(u+1));
	}
	return 0;
}