【P4198】楼房重建（线段树维护前缀最值）

线段树维护前缀最值相关的模板题。

关键思想在于合并，\([l,mid]\) 的前缀最值仍然是 \([l,r]\) 的前缀最值，而 \((mid,r]\) 中只有 \(\geq mx_l\) 的前缀最值才是 \([l,r]\) 的前缀最值。

而前缀最值是单调的，于是可以对于 \((mid,r]\) 在线段树上二分，统计 \(\geq mx_l\) 的前缀最值的信息和。

当信息具有可减性时，直接按原来的方法记录 \([l,r]\) 的前缀最值的信息和 \(su_u\) 即可。此时单点修改 \(O(\log^2n)\)，全局询问 \(O(1)\)，区间询问 \(O(\log^2n)\)。

而当信息不具有可减性时，需要多维护 \(sr_u\) 表示 \([l,r]\) 中位于 \((mid,r]\) 的前缀最值的信息和，便于线段树上二分时的合并。时间复杂度和上面一样。

#include<bits/stdc++.h>

#define rep(i,a,b) for(int i=(a);i<=(b);i++)
#define per(i,a,b) for(int i=(b);i>=(a);i--)
#define repg(i,u,v) for(int i=head[u],v=to[i];i;i=nxt[i],v=to[i])
#define N 100010

using namespace std;

inline int read()
{
	int x=0,f=1;
	char ch=getchar();
	while(ch<'0'||ch>'9')
	{
		if(ch=='-') f=-1;
		ch=getchar();
	}
	while(ch>='0'&&ch<='9')
	{
		x=(x<<1)+(x<<3)+(ch^'0');
		ch=getchar();
	}
	return x*f;
}

struct Point
{
	int x,y;
	Point(){};
	Point(int a,int b){x=a,y=b;}
};

bool operator < (Point a,Point b)
{
	return 1ll*a.y*b.x<1ll*b.y*a.x;
}

bool operator == (Point a,Point b)
{
	return 1ll*a.y*b.x==1ll*b.y*a.x;
}

bool operator > (Point a,Point b)
{
	return b<a;
}

bool operator <= (Point a,Point b)
{
	return (a<b||a==b);
}

int n,m;
int su[N<<2],sr[N<<2];
Point maxn[N<<2];

int query(int k,int l,int r,Point x)
{
	if(l==r) return maxn[k]>x?su[k]:0;
	int mid=(l+r)>>1;
	if(maxn[k<<1]<=x) return query(k<<1|1,mid+1,r,x);
	return query(k<<1,l,mid,x)+sr[k];
}

void up(int k,int mid,int r)
{
	maxn[k]=max(maxn[k<<1],maxn[k<<1|1]);
	sr[k]=query(k<<1|1,mid+1,r,maxn[k<<1]);
	su[k]=su[k<<1]+sr[k];
}

void build(int k,int l,int r)
{
	if(l==r)
	{
		maxn[k]=Point(l,0);
		su[k]=0,sr[k]=0;
		return;
	}
	int mid=(l+r)>>1;
	build(k<<1,l,mid);
	build(k<<1|1,mid+1,r);
	up(k,mid,r);
}

void update(int k,int l,int r,int x,int y)
{
	if(l==r)
	{
		maxn[k]=Point(l,y),su[k]=1;
		return;
	}
	int mid=(l+r)>>1;
	if(x<=mid) update(k<<1,l,mid,x,y);
	else update(k<<1|1,mid+1,r,x,y);
	up(k,mid,r);
}

int main()
{
	n=read(),m=read();
	build(1,1,n);
	rep(i,1,m)
	{
		int x=read(),y=read();
		update(1,1,n,x,y);
		printf("%d\n",su[1]);
	}
	return 0;
}