设为首页 加入收藏

TOP

HDU 4343 Interval query（倍增思想+贪心）
2015-11-21 00:55:58 来源: 作者: 【大 中 小】 浏览:1次
Tags：HDU 4343 Interval query 倍增 思想 贪心

题意：给定n(n<=100000)个区间（左闭右开）和m(m<=100000)次询问[l, r]，问所有在[l, r]区间内最多有多少个两两不相交的区间。，

思路：首先贪心的思想，去除掉包含其他区间的大区间，这样做肯定不会影响结果。

然后对于所有区间，按照左端点升序排序，那么由于这时所有区间不相互包含，他们的右端点也是递增的。

那么对于每个询问，肯定是从左到右去尽可能多的区间，这个贪心容易想到。

对数据离散化，记录从每个点开始的经过i个区间所达到的最近距离，这一步用到了倍增的思想，因为如果一个点一个点顺序找，那么时间复杂度和空间复杂度都无法承受。

具体来说，用f[i][j]记录从i出发经过2^j个区间所达到的最近点，那么可以得出递推关系

f[i][j] = f[ f[i][j-1] ][j-1];

那么对于每个询问，我们将询问ql,qr也离散化,只需找到从ql最多经过多少区间使得其不超过qr即可。

ps：半夜睡不着真是心痛，起来补题.........

?

#include
  
     
#include
   
     #include
    
      #include
     
       #include
      
        #include
       
         #include
        
          #include
          #include
          
            #include
           
             #include
            
              #include
              #include
              
                #define eps 1e-6 #define LL long long #define pii (pair
               
                ) //#pragma comment(linker, /STACK:1024000000,1024000000) using namespace std; const int maxn = 100000 + 100; const int INF = 0x3f3f3f3f; int n, m; struct Node { int l, r; bool operator < (const Node& A) const { if(l == A.l) return r > A.r; return l < A.l; } } node[maxn]; int discret[2*maxn]; int fa[2*maxn][20]; int solve(int l, int r) { int ans = 0; for(int i = 16; i >= 0; i--) { int t = fa[l][i]; // cout << t << endl; if(t == r) return ans+(1<
                
                 = 0; i--) { // cout << node[i].l << endl; if(i == node[cnt2].l) { fa[i][0] = min(node[cnt2].r, fa[i+1][0]); while(i == node[cnt2].l) cnt2--; } else fa[i][0] = fa[node[cnt2+1].l][0]; } for(int i = 1; i < 17; i++) { for(int j = 0; j < cnt; j++) if(fa[j][i-1] != INF) fa[j][i] = fa[ fa[j][i-1] ][i-1]; } for(int i = 0; i < m; i++) { int l, r; scanf(%d%d, &l, &r); l = lower_bound(discret, discret+cnt, l) - discret; r = upper_bound(discret, discret+cnt, r) - discret - 1; // cout << l << << r << endl; printf(%d , solve(l, r)); } //cout << fa[0][0] << endl; } return 0; }
【大 中 小】【打印】 【繁体】【投稿】【收藏】 【推荐】【举报】【评论】 【关闭】 【返回顶部】
分享到: 
上一篇：POJ - 1716 Integer Intervals（.. 下一篇：uva 11177(凸多边形和圆的相交)

评论

帐　　号: 密码: (新用户注册)
验 证 码:
表　　情:
内　　容: