P4198 楼房重建

题面

https://www.luogu.org/problem/P4198

题解

#include<bits/stdc++.h>
using namespace std;
const int N=1e5+50;
int n,m;
double a[N];
struct node{
  double mx;
  int len;
} tt[4*N];
void pushup1(int x){
  tt[x].mx=max(tt[x<<1].mx,tt[x<<1|1].mx);
}
int pushup2(double lx,int x,int l,int r){
  if (tt[x].mx<=lx) return 0;
  if (a[l]>lx) return tt[x].len;
  if (l==r) return a[l]>lx;
  int s1=x<<1,s2=x<<1|1;
  int mid=l+r>>1;
  if (tt[s1].mx<=lx) return pushup2(lx,s2,mid+1,r);
  else return pushup2(lx,s1,l,mid)+tt[x].len-tt[s1].len;
}

void chan(int x,int l,int r,int to,int c){
  if (l==r && l==to) {
    tt[x].mx=(double)c/to;
    tt[x].len=1;
    return;
  }
  int mid=l+r>>1;
  if (to<=mid) chan(x<<1,l,mid,to,c); else if (to>mid) chan(x<<1|1,mid+1,r,to,c);
  pushup1(x);
  tt[x].len=tt[x<<1].len+pushup2(tt[x<<1].mx,x<<1|1,mid+1,r);
}

int main(){
  scanf("%d %d",&n,&m);
  int x,y;
  for (int i=1;i<=m;i++) {
    scanf("%d %d",&x,&y);
    a[x]=(double)y/x;
    chan(1,1,n,x,y);
    printf("%d\n",tt[1].len);
  }
  return 0;
}