P4198 楼房重建
题意
一个长度为(n)的序列,有(m)次单点修改,问每次修改完后前缀最大值的数量。
数据范围:(n,mle10^5)
思路
考虑用线段树维护,每个节点维护区间(max)和区间前缀最大值个数。
那么合并两个区间时,左区间所有的前缀最大值必然会保存。
右区间的前缀最大值会保存所有大于左区间最大值的前缀最大值。
我们设一个(pushup(o,l,r,lx))表示节点(o),区间([l,r]),前缀最大值中大于(lx)的个数。
如果左区间最大值不超过(lx),那么直接递归到右区间
否则,递归到左区间,右区间收到的限制为左区间的最大值,所以答案为(cnt_{o}-cnt_{ls})
只会递归(log_2 n)层
它的复杂度就对了。
代码
#include<bits/stdc++.h>
#define ls o<<1
#define rs o<<1|1
using namespace std;
const int sz=1e5+7;
int n,m;
int x,y;
int cnt[sz<<2];
double a[sz];
double mx[sz<<2];
int pushup(int o,int l,int r,double lx){
if(lx>mx[o]) return 0;
if(a[l]>lx) return cnt[o];
if(l==r) return mx[o]>lx;
int mid=(l+r)>>1;
if(mx[ls]<=lx) return pushup(rs,mid+1,r,lx);
else return pushup(ls,l,mid,lx)+cnt[o]-cnt[ls];
}
void update(int o,int l,int r,int x){
if(l==r){ mx[o]=a[l]; cnt[o]=1; return;}
int mid=(l+r)>>1;
if(x<=mid) update(ls,l,mid,x);
else update(rs,mid+1,r,x);
mx[o]=max(mx[ls],mx[rs]);
cnt[o]=cnt[ls]+pushup(rs,mid+1,r,mx[ls]);
}
int main(){
scanf("%d%d",&n,&m);
for(int i=1;i<=m;i++){
scanf("%d%d",&x,&y);
a[x]=1.0*y/x;
update(1,1,n,x);
printf("%d
",cnt[1]);
}
}