POJ 3067 Japan（经典树状数组）-白红宇

POJ 3067 Japan（经典树状数组）

阅读量：6574 次

发布时间：2019-06-24

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

　　基础一维树状数组

　　题意：左边一排 1-n 的城市，右边一排 1-m 的城市，都从上到下依次对应。接着给你一些城市对，表示城市这两个城市相连，最后问你一共有多少个交叉，其中处于城市处的交叉不算并且每个位置最多只能有有一个交叉。

　　树状数组：利用二进制特点解决单点更新与满足区间减法的区间求值，例如求区间和。二进制：因为每个数字一定可以用二进制转化为 log2 n个数，所以我们可以另外开一个数组bit记录当前位置前二进制表示此位置的最后一位1代表数的个数之和（例如：10->1010记录前两个数）。所以我们更新则只需要向后更新含有这个位置的bit数组（log2 n个），求和则需要向前更新到最前端得到从头到此位置的总和。注意这儿因为我们使用的二进制 & ，所以我们一定要避免下标0出现

　　如果左边计数 x1-xn，右边计数 y1-yn，则要出现交叉就是x1与y2相连，y1与x2相连并（x1-x2）*（y2-y1）<0。所以我们可以首先升序排序x轴，因为城市处不算交叉，则x轴相同时y轴升序排序，然后得出y轴的逆序数就是交叉点数。

　　逆序数大小：一串数字中每一个数字前面比它大的个数总和。

　　求逆序数经典解法就是树状数组我们可以首先给每一位加一个位置标记，接着升序排序，数字相同时按照标记升序。然后反向首先计算标记位置及前面的个数，接着再在标记的位置插入1（1方便处理），最后求出总和。

#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<<28;const double Pi=acos(-1.0);const int Mod=1e9+7;const int Max=1000010;struct node{ int lef,rig,pos;}num[Max];int bit[Max],k;bool cmp1(struct node p1,struct node p2){ if(p1.lef==p2.lef) return p1.rig
                   
                    0) { sum+=(ll)bit[x]; x-=lowbit(x); } return sum;}int main(){ int t,n,m,coun=0; ll ans; scanf("%d",&t); while(t--) { memset(bit,0,sizeof(bit)); scanf("%d %d %d",&n,&m,&k); for(int i=1;i<=k;++i) scanf("%d %d",&num[i].lef,&num[i].rig); sort(num+1,num+k+1,cmp1); for(int i=1;i<=k;++i) num[i].pos=i; sort(num+1,num+k+1,cmp2); ans=0ll; for(int i=k;i>0;--i) { ans+=Sum(num[i].pos); Add(num[i].pos,1); } printf("Test case %d: %I64d\n",++coun,ans); } return 0;}

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

你可能感兴趣的文章