There is a large construction site outside the building of Xiao A. There are N buildings to be built on the construction site. Every day, houses on this construction site are demolished, built and demolished. He often looked out of the window in a daze, counting how many houses he could see.
To simplify the problem, we consider that these events occur in a two-dimensional plane. The location of small A at (0,0) points in the plane can be represented by a line connecting (i,0) and (i,Hi), where Hi is the height of the first building. If any point above 0 in the building does not intersect the (0,0) line with the previous line segment, the building is considered visible.
The construction team lasted for A total of M days. Initially, all buildings had not yet been built, and their height was 0. On day i, the building team will change the height of the house with the abscissa of Xi to Yi (the height can be bigger than before - built or smaller - demolished or even kept unchanged - the building team did nothing on that day). How many buildings can he see every day after the construction team is finished?
The first line has two positive integers N,M
Next, line M, with two positive integers per line Xi,Yi
Line M, an integer in line i indicates how many buildings can be seen by A after day i
3 4
2 4
3 6
1 1000000000
1 1
1
1
1
2
| Test points | N,M |
| 1 | <=100 |
| 2 | <=5000 |
| 3 | <=50000 |
| 4 | <=100000 |
| 5 | <=30000 |
| 6 | <=50000 |
| 7 | <=70000 |
| 8 | <=80000 |
| 9 | <=90000 |
| 10 | <=100000 |
Classification label Tags Click here to expand.
The visible number and maximum slope of each node in the maintenance interval.
When two intervals are merged, the visible number on the left remains unchanged, and the visible number on the right cannot be obtained directly.
To consider recursive queries:
Let the maximum slope of the left interval be k. We will calculate for each node if we add one to the left of it.
What is the visible number of a building with a slope of k?
#include<iostream>
#include<cstdio>
#include<cstring>
#include<cmath>
#include<bitset>
#define ls k<<1
#define rs k<<1|1
using namespace std;
const int MAXN=1000001;
inline void read(int &n)
{
char c='+';int x=0;bool flag=0;
while(c<'0'||c>'9'){c=getchar();if(c=='-')flag=1;}
while(c>='0'&&c<='9'){x=x*10+(c-48);c=getchar();}
n=flag==1?-x:x;
}
struct node
{
int l,r,num;
double maxrake;
}tree[MAXN<<2];
int n,m;
int calc(int k,double val)
{
if(tree[k].l==tree[k].r)
return tree[k].maxrake>val;// Visible
if(tree[ls].maxrake<=val)
return calc(rs,val);// The tallest ones are smaller than it. Calculate directly to the right.
return tree[k].num-tree[ls].num+calc(ls,val);//
}
void update(int k)
{
tree[k].maxrake=max(tree[ls].maxrake,tree[rs].maxrake);
tree[k].num=tree[ls].num+calc(rs,tree[ls].maxrake);
}
void build_tree(int ll,int rr,int k)
{
tree[k].l=ll;tree[k].r=rr;
if(ll==rr)
return ;
int mid=(ll+rr)>>1;
build_tree(ll,mid,ls);
build_tree(mid+1,rr,rs);
}
void change(int k,int pos,double val)
{
if(tree[k].l==tree[k].r)
{
tree[k].num=1;
tree[k].maxrake=val;
return ;
}
int mid=(tree[k].l+tree[k].r)>>1;
if(pos<=mid) change(ls,pos,val);
else change(rs,pos,val);
update(k);
}
int main()
{
freopen("hh.in","r",stdin);
read(n);read(m);
build_tree(1,n,1);
for(int i=1;i<=m;i++)
{
int pos,h;
read(pos);read(h);
change(1,pos,(double)h/pos);
printf("%d\n",tree[1].num);
}
return 0;
}