洛谷 P4198 BZOJ 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能看到的樓房有多少棟

樣例輸入

3 4

2 4

3 6

1 1000000000

1 1

樣例輸出

1

2

資料約定

　　對于所有的資料1<=Xi<=N，1<=Yi<=10^9

N,M<=100000

提示

來源

中國國家隊清華集訓 2012-2013 第一天

吐槽

　　記得在WC2017day3晚上學線段樹(太菜了，這時候才學線段樹)，被同寝室的新疆大佬uncle-lu安利了這道題（

他的部落格

），從WC2017day3拖到NOI2017day0，總算AC了，不容易啊！

　　NOI前夕突然很想抒發一下内心的情感，但國文不好找不到詞兒………………

　　原來隻要在粘貼的時候末尾空一行，BZOJ獨特的題面格式就能粘上來呀…還别說藍色挺符合我部落格的風格……

解題思路

　　本着不重複造輪子的思想，偷個懶——

http://hzwer.com/6746.html

，或者上面那個連結也行……

源代碼

#include<cstdio>
#include<algorithm>

int n,m;

struct Node{
    int l,r;
    int num;//區間内可見建築數
    double maxk;//區間内最大斜率
}t[400010];
void maketree(int x,int l,int r)
{
    t[x]={l,r,0,0.0};
    if(l==r) return;
    int mid=l+r>>1;
    maketree(x<<1,l,mid);
    maketree(x<<1|1,mid+1,r);
}

int calc(int x,double k)
{
    int l=t[x].l,r=t[x].r;
    if(l==r) return t[x].maxk>k;
    if(t[x<<1].maxk<=k) return calc(x<<1|1,k);
    else return t[x].num-t[x<<1].num+calc(x<<1,k);
}

void update(int x,int pos,double k)
{
    int l=t[x].l,r=t[x].r,mid=l+r>>1;
    if(l==r)
    {
        t[x].num=1;
        t[x].maxk=k;
        return;
    }
    if(pos<=mid)
        update(x<<1,pos,k);
    else
        update(x<<1|1,pos,k);
    t[x].maxk=std::max(t[x<<1].maxk,t[x<<1|1].maxk);
    t[x].num=t[x<<1].num+calc(x<<1|1,t[x<<1].maxk);
}

int main()
{
    scanf("%d%d",&n,&m);
    maketree(1,1,n);
    int x,y;
    while(m--)
    {
        scanf("%d%d",&x,&y);
        update(1,x,(double)y/x);
        printf("%d\n",t[1].num);
    }
    return 0;
}