2957: 楼房重建

　　小A的楼房外有一大片施工工地，工地上有N栋待建的楼房。每天，这片工地上的房子拆了又建、建了又拆。他经常无聊地看着窗外发呆，数自己能够看到多少栋房子。
　　为了简化问题，我们考虑这些事件发生在一个二维平面上。小A在平面上(0,0)点的位置，第i栋楼房可以用一条连接(i,0)和(i,Hi)的线段表示，其中Hi为第i栋楼房的高度。如果这栋楼房上任何一个高度大于0的点与(0,0)的连线没有与之前的线段相交，那么这栋楼房就被认为是可见的。
　　施工队的建造总共进行了M天。初始时，所有楼房都还没有开始建造，它们的高度均为0。在第i天，建筑队将会将横坐标为Xi的房屋的高度变为Yi(高度可以比原来大---修建，也可以比原来小---拆除，甚至可以保持不变---建筑队这天什么事也没做)。请你帮小A数数每天在建筑队完工之后，他能看到多少栋楼房？

　　第一行两个正整数N,M
　　接下来M行，每行两个正整数Xi,Yi

　　M行，第i行一个整数表示第i天过后小A能看到的楼房有多少栋

 1 #include<cstdio> 2 #include<algorithm> 3 #define lson l,m,rt<<1 4 #define rson m+1,r,rt<<1|1 5  6 using namespace std; 7 const int MAXN = 100100; 8  9 double mx[MAXN<<2];10 int sum[MAXN<<2],a[MAXN];11 int n,m;12 13 int read()14 {15     int x = 0,f = 1;char ch = getchar();16     while (ch<‘0‘||ch>‘9‘) {if(ch==‘-‘)f=-1; ch=getchar(); }17     while (ch>=‘0‘&&ch<=‘9‘) {x=x*10+ch-‘0‘; ch=getchar(); }18     return x*f;19 }20 int calc(int l,int r,int rt,double k)21 {22     if (l==r) return mx[rt]>k;23     int m = (l+r)>>1;24     if (mx[rt<<1]>k) return calc(lson,k)+sum[rt]-sum[rt<<1];25     else  return calc(rson,k);26 }27 void pushup(int l,int r,int rt)28 {29     mx[rt] = max(mx[rt<<1],mx[rt<<1|1]);30     int m = (l+r)>>1;31     sum[rt] = sum[rt<<1]+calc(rson,mx[rt<<1]);32 }33 void update(int l,int r,int rt,int p,double c)34 {35     if (l==r)36     {37         mx[rt] = c;38         sum[rt] = 1;39         return ;40     }41     int m = (l+r)>>1;42     if (p<=m) update(lson,p,c);43     else update(rson,p,c);44     pushup(l,r,rt);45 }46 int main()47 {48     n = read();m = read();49     while (m--)50     {51         double x = read(), y = read();52         update(1,n,1,(int)x,y/x);53         printf("%d\n",sum[1]);54     }    55     return 0;56 }