楼房重建

Time Limit: 1 Sec Memory Limit: 256 MB

题目连接

http://www.lydsy.com/JudgeOnline/problem.php?id=2957

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

Sample Input

Sample Output

数据约定

　　对于所有的数据1<=Xi<=N，1<=Yi<=10^9

N,M<=100000

HINT

题意

题解：

首先这道题肯定是得转化成斜率来做，我们只有后面的斜率大于前面的斜率的时候，才能看见

我们分块做，首先我们得明确，在每一个块中，斜率大小一定是单调的

所以我们可以在每一个块中，都二分找到分界点，然后直接加上去就好了

代码：

//qscqesze#include 
     
      #include 
      
       #include 
       
        #include 
        
         #include 
         
          #include 
          
           #include 
           
            #include 
            
             #include 
             
              #include 
              
               #include 
               
                #include 
                
                 #include 
                 #include 
                  
                   typedef long long ll;using namespace std;//freopen("D.in","r",stdin);//freopen("D.out","w",stdout);#define sspeed ios_base::sync_with_stdio(0);cin.tie(0)#define maxn 200001#define mod 10007#define eps 1e-9int Res,Num;char C,CH[12];//const int inf=0x7fffffff; //无限大const int inf=0x3f3f3f3f;/*inline void P(int x){ Num=0;if(!x){putchar('0');puts("");return;} while(x>0)CH[++Num]=x%10,x/=10; while(Num)putchar(CH[Num--]+48); puts("");}*///**************************************************************************************inline ll read(){ int x=0,f=1;char ch=getchar(); while(ch<'0'||ch>'9'){ if(ch=='-')f=-1;ch=getchar();} while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();} return x*f;}inline void P(int x){ Num=0;if(!x){putchar('0');puts("");return;} while(x>0)CH[++Num]=x%10,x/=10; while(Num)putchar(CH[Num--]+48); puts("");}int n,m,sum,sz;int a,b;int num[maxn];double k[maxn];double maxv[maxn];vector
                   
                     see[500];int l[500],r[500];void makeblock(){ memset(maxv,0,sizeof(maxv)); sz=sqrt((double)n*1.05); for(sum=1;sum*sz
                    
                     maxv[num[a]]) { maxv[num[a]]=k[i]; see[num[a]].push_back(k[i]); } }}void query(){ int ans=0; double tmp=0; for(int i=1;i<=sum;i++) { if(!see[i].empty()) { ans+=see[i].end()-upper_bound(see[i].begin(),see[i].end(),tmp); tmp=max(tmp,maxv[i]); } } P(ans);}int main(){ n=read(),m=read(); makeblock(); while(m--) { scanf("%d%d",&a,&b); updata(); query(); }}

转载于:https://www.cnblogs.com/qscqesze/p/4441225.html

你可能感兴趣的文章