POJ 2464 Brownie Points II（树状数组）-白红宇

POJ 2464 Brownie Points II（树状数组）

阅读量：5921 次

发布时间：2019-06-19

本文共 1388 字，大约阅读时间需要 4 分钟。

　　一开始还以为对于每根竖线，只要与过了任意一点的横线相交都可以呢，这样枚举两条线就要O（n^2），结果发现自己想多了。。。

　　其实是每个点画根竖线和横线就好，对于相同竖线统计（一直不包含线上点）右上左下总点数的最小值，最后不同竖线求一个最大值。对于每条等于这个最小值最大化的竖线都找一个右下与左上的最大值，排序输出即可。注意这儿排序后需要去重

　　思想倒是不难，主要就是麻烦。只需要分别离散化x轴，y轴的点，然后枚举每个点找到四个方向的其他总点数，这儿用树状数组可以简单解决。但是注意空间问题不能开二维，开一维排序x轴，再左右扫一遍，一边计算一边添加点即可，注意x y轴线上的点要减去。先扫一边找到最小值最大化的值与每条竖线包含哪些点，再扫一遍找到等于那个值的竖线中的最大右下左上和

代码写得很麻烦

#include
     
      #include
      #include
       
        #include
        
         #include
         
          #include
          
           #include
           
            #include
            
             #include
             
              #include
              
               #include
               
                #include
                
                 using namespace std;#define eps 1E-8/*注意可能会有输出-0.000*/#define Sgn(x) (x<-eps? -1 :x
                 
                   0.0 ? x+eps : x-eps)//浮点数转化#define zero(x) (((x)>0?(x):-(x))
                  
                   >b)typedef long long ll;typedef unsigned long long ull;const int Inf=1<<30;const double Pi=acos(-1.0);const int Max=200010;int bit[Max];struct node{ int xx1,yy1; int lup,rup,ldo,rdo;} poi[Max];int n;bool cmp1(struct node p1,struct node p2){ if(p1.xx1==p2.xx1) return p1.yy1
                   
                    0) { sum+=bit[y]; y-=lowbit(y); } return sum;}void Dtz()//离散化{ sort(poi,poi+n,cmp2); int m=1; poi[n].yy1=Inf; for(int i=0; i
                    
                     =0; i--) { if(i!=n-1&&poi[i].xx1==poi[i+1].xx1) sum++; else sum=0; poi[i].rdo=Sum(poi[i].yy1-1); poi[i].rup=Sum(n)-Sum(poi[i].yy1)-sum; Add(poi[i].yy1); } int manx=0,mans;//统计 int coun=0,cnt=0; minx[0]=Inf; for(int i=0; i

转载于:https://www.cnblogs.com/zhuanzhuruyi/p/5863530.html

你可能感兴趣的文章