C44 线段树+递归合并 P4198 楼房重建

#include<bits/stdc++.h>
using namespace std;
#define lc(p) (p<<1)
#define rc(p) (p<<1|1)
const int N=1e5+10;
struct trnode{int l,r;double mx;int sum;}tr[N<<2];//mx:区间最大斜率, sum:区间可见楼房数
void bt(int p,int l,int r)
{
    tr[p]={l,r,0,0};
    if(l==r) return ;
    int m=(l+r)>>1;
    bt(lc(p),l,m);bt(rc(p),m+1,r);
}
int dfs(int p,double x)//求右分支sum
{ 
    if(tr[p].mx<=x) return 0;//剪枝
    if(tr[p].l==tr[p].r) return tr[p].mx>x; //叶子
    if(tr[lc(p)].mx<=x) return dfs(rc(p),x);
    else                return dfs(lc(p),x)+tr[p].sum-tr[lc(p)].sum;
}
void pushup(int p)
{
    tr[p].mx=max(tr[lc(p)].mx,tr[rc(p)].mx);
    tr[p].sum=tr[lc(p)].sum+dfs(rc(p),tr[lc(p)].mx);
}
void change(int p,int x,double v)
{
    if(x<tr[p].l || tr[p].r<x)return ;
    if(tr[p].l==tr[p].r){tr[p].mx=v; tr[p].sum=1; return;}
    change(lc(p),x,v);change(rc(p),x,v);
    pushup(p);
}
int main()
{
    int n,m;scanf("%d%d",&n,&m);
    bt(1,1,n);
    for(int i=1,x,y;i<=m;i++)
    {
        scanf("%d%d",&x,&y);
        change(1,x,(double)y/x);
        printf("%d\n",tr[1].sum);
    }
    return 0;
}

C44 线段树+递归合并 P4198 楼房重建

#include<bits/stdc++.h>
using namespace std;
#define lc(p) (p<<1)
#define rc(p) (p<<1|1)
const int N=1e5+10;
struct trnode{int l,r;double mx;int sum;}tr[N<<2];//mx:区间最大斜率, sum:区间可见楼房数
void bt(int p,int l,int r)
{
    tr[p]={l,r,0,0};
    if(l==r) return ;
    int m=(l+r)>>1;
    bt(lc(p),l,m);bt(rc(p),m+1,r);
}
int dfs(int p,double x)//求右分支sum
{ 
    if(tr[p].mx<=x) return 0;//剪枝
    if(tr[p].l==tr[p].r) return tr[p].mx>x; //叶子
    if(tr[lc(p)].mx<=x) return dfs(rc(p),x);
    else                return dfs(lc(p),x)+tr[p].sum-tr[lc(p)].sum;
}
void pushup(int p)
{
    tr[p].mx=max(tr[lc(p)].mx,tr[rc(p)].mx);
    tr[p].sum=tr[lc(p)].sum+dfs(rc(p),tr[lc(p)].mx);
}
void change(int p,int x,double v)
{
    if(x<tr[p].l || tr[p].r<x)return ;
    if(tr[p].l==tr[p].r){tr[p].mx=v; tr[p].sum=1; return;}
    change(lc(p),x,v);change(rc(p),x,v);
    pushup(p);
}
int main()
{
    int n,m;scanf("%d%d",&n,&m);
    bt(1,1,n);
    for(int i=1,x,y;i<=m;i++)
    {
        scanf("%d%d",&x,&y);
        change(1,x,(double)y/x);
        printf("%d\n",tr[1].sum);
    }
    return 0;
}