BZOJ 2957：楼房重建

正文索引 [隐藏]

Description
Input
Output
Sample Input
Sample Output
题解
代码

Description

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

Input

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

Output

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

Sample Input

3 4
2 4
3 6
1 1000000000
1 1

Sample Output

1
1
1
2
数据约定
对于所有的数据1<=Xi<=N，1<=Yi<=10^9
N,M<=100000

题解

这道题目乍一看上去好像就是暴力能做，再一看就是一个分块暴力维护！我们把楼房分块成根号n个块，每个块内在暴力维护一个单调上升的序列，然后再用二分来生成整个序列的单调上升序列，得到答案就行了。

代码

/*Author:WNJXYK*/
#include<cstdio>
using namespace std;
const int Maxn=100000;
const int SMaxn=320;
double w[Maxn+5];
int nowCnt;
double tmpMax;
int ans;
int cnts;
int cntLen;
int len[SMaxn+5];
struct Seq{
    double num[SMaxn+5];
    int siz;
    inline void add(double x){
        num[++siz]=x;
    }
};
Seq seq[SMaxn+5];
int n,m;
int x,y;
int main(){
    scanf("%d%d",&n,&m);
    while((cntLen+1)*(cntLen+1)<n) cntLen++;
    cnts=n/cntLen+(n%cntLen==0?0:1);
    for (int i=1;i<cnts;i++) len[i]=cntLen;
    len[cnts]=n-cntLen*(cnts-1);
    for (int i=1;i<=m;i++){
        scanf("%d%d",&x,&y);
        w[x]=(double)y/(double)x;
        nowCnt=(x-1)/cntLen+1;
        tmpMax=0;seq[nowCnt].siz=0;
        for (int j=cntLen*(nowCnt-1)+1;j<=cntLen*(nowCnt-1)+len[nowCnt];j++)
            if (w[j]>tmpMax){
                seq[nowCnt].add(w[j]);
                tmpMax=w[j];
            }
        ans=seq[1].siz;
        tmpMax=seq[1].num[seq[1].siz];
        for (int j=2;j<=cnts;j++){
            if (seq[j].num[seq[j].siz]>tmpMax){
                int left=1,right=seq[j].siz,tmpAns=0;
                while(left<=right){
                    int mid=(left+right)/2;
                    if (seq[j].num[mid]>tmpMax){
                        tmpAns=mid;
                        right=mid-1;
                    }else{
                        left=mid+1;
                    }
                }
                ans+=seq[j].siz+1-tmpAns;
                tmpMax=seq[j].num[seq[j].siz];
            }
        }
        printf("%dn",ans);
    }
    return 0;
}

/*Author:WNJXYK*/

#include<cstdio>

using namespace std;

const int Maxn=100000;

const int SMaxn=320;

double w[Maxn+5];

int nowCnt;

double tmpMax;

int ans;

int cnts;

int cntLen;

int len[SMaxn+5];

struct Seq{

double num[SMaxn+5];

int siz;

inline void add(double x){

num[++siz]=x;

}

};

Seq seq[SMaxn+5];

int n,m;

int x,y;

int main(){

scanf("%d%d",&n,&m);

while((cntLen+1)*(cntLen+1)<n) cntLen++;

cnts=n/cntLen+(n%cntLen==0?0:1);

for (int i=1;i<cnts;i++) len[i]=cntLen;

len[cnts]=n-cntLen*(cnts-1);

for (int i=1;i<=m;i++){

scanf("%d%d",&x,&y);

w[x]=(double)y/(double)x;

nowCnt=(x-1)/cntLen+1;

tmpMax=0;seq[nowCnt].siz=0;

for (int j=cntLen*(nowCnt-1)+1;j<=cntLen*(nowCnt-1)+len[nowCnt];j++)

if (w[j]>tmpMax){

seq[nowCnt].add(w[j]);

tmpMax=w[j];

}

ans=seq[1].siz;

tmpMax=seq[1].num[seq[1].siz];

for (int j=2;j<=cnts;j++){

if (seq[j].num[seq[j].siz]>tmpMax){

int left=1,right=seq[j].siz,tmpAns=0;

while(left<=right){

int mid=(left+right)/2;

if (seq[j].num[mid]>tmpMax){

tmpAns=mid;

right=mid-1;

}else{

left=mid+1;

}

ans+=seq[j].siz+1-tmpAns;

tmpMax=seq[j].num[seq[j].siz];

}

printf("%dn",ans);

}

return 0;

}

一	二	三	四	五	六	日
						1
2	3	4	5	6	7	8
9	10	11	12	13	14	15
16	17	18	19	20	21	22
23	24	25	26	27	28	29
30	31

WNJXYKの博客

喂你脚下有坑