codeforces #261 D题 Pashmak and Parmida's problem（线段树+离散化） - c++编程基础

TOP

codeforces #261 D题 Pashmak and Parmida's problem（线段树+离散化）

2015-07-20 17:46:58 来源: 作者: 【大中小】浏览:2次

Tags：codeforces #261 Pashmak and Parmida' problem 线段离散

这个题攒了好长时间了，一直也没看。。今天看了下，也不难。当时做的时候明明还有半个多小时可以看这题的，但是。。由于某些人的打扰。。我一直在应付着拒绝。。所以这题当时连看都没来得及看。。以后做CF果断不上QQ了。。。

这题就是求逆序数。需要先预处理每个点的左边与右边与之相同的数的个数。然后用线段树去求逆序数就可以了。因为数的范围是10^9，而数据范围只有10^6，所以要先对其离散化。

代码如下：

#include 
  
   
#include 
   
     #include 
    
      #include 
     
       #include 
      
        #include 
       
         #include 
        
          #include 
         
           #include
           #include 
           
             #include 
            
              using namespace std; #define lson l, mid, rt<<1 #define rson mid+1, r, rt<<1|1 #define LL __int64 int dp1[1100000], dp2[1100000], a[1100000], b[1100000], c[1100000], _hash[1100000]; LL sum[5100000]; void PushUp(int rt) { sum[rt]=sum[rt<<1]+sum[rt<<1|1]; } void update(int p, int l, int r, int rt) { if(l==r) { sum[rt]++; return ; } int mid=l+r>>1; if(p<=mid) update(p,lson); else update(p,rson); PushUp(rt); } LL query(int ll, int rr, int l, int r, int rt) { if(ll<=l&&rr>=r) return sum[rt]; int mid=l+r>>1; LL ans=0; if(ll<=mid) ans+=query(ll,rr,lson); if(rr>mid) ans+=query(ll,rr,rson); return ans; } int erfen(int x, int high) { int low=0, mid; while(low<=high) { mid=low+high>>1; if(c[mid]>x) high=mid-1; else if(c[mid]
             
              =1;i--) { dp2[i]=++_hash[a[i]]; } memset(sum,0,sizeof(sum)); /*for(i=n;i>=1;i--) { printf(%d ,dp1[i]); } printf( ); for(i=n;i>=1;i--) { printf(%d ,dp2[i]); } printf( );*/ for(i=n;i>=1;i--) { ans+=query(0,dp1[i]-1,0,max1,1); update(dp2[i],0,max1,1); //printf(%I64d ,ans); } printf(%I64d ,ans); return 0; }


【大中小】【打印】【繁体】【投稿】【收藏】【推荐】【举报】【评论】【关闭】【返回顶部】
分享到:
上一篇：Word Break	下一篇：Linked List Cycle [leetcode]

帐　　号:

密码: (新用户注册)

验证码:

表　　情:

内　　容: