离散化+线段树/二分查找/尺取法 HDOJ 4325 Flowers-白红宇

离散化+线段树/二分查找/尺取法 HDOJ 4325 Flowers

阅读量：5836 次

发布时间：2019-06-18

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

题意：给出一些花开花落的时间，问某个时间花开的有几朵

分析：这题有好几种做法，正解应该是离散化坐标后用线段树成端更新和单点询问。还有排序后二分查找询问点之前总花开数和总花凋谢数，作差是当前花开的数量，放张图易理解：

还有一种做法用尺取法的思想，对暴力方法优化，对询问点排序后再扫描一遍，花开+1，花谢-1。详细看代码。

收获：一题收获很多：1. 降低复杂度可以用二分 2. 线段计数问题可以在端点标记1和-1 3. 离散化+线段树终于会了:) ()

代码1：离散化+线段树

/************************************************* Author        :Running_Time* Created Time  :2015-8-25 8:55:54* File Name     :F.cpp ************************************************/#include 
     
      #include 
      
       #include 
       
        #include 
        
         #include 
         
          #include 
          
           #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 | 1typedef long long ll;typedef pair
                      
                        P;const int N = 1e5 + 10;const int INF = 0x3f3f3f3f;struct ST { int sum[N<<2], col[N<<2]; void push_up(int rt) { sum[rt] = sum[rt<<1] + sum[rt<<1|1]; } void push_down(int rt, int len) { if (col[rt]) { col[rt<<1] += col[rt]; col[rt<<1|1] += col[rt]; sum[rt<<1] += col[rt] * (len - (len >> 1)); sum[rt<<1|1] += col[rt] * (len >> 1); col[rt] = 0; } } void build(int l, int r, int rt) { col[rt] = 0; sum[rt] = 0; if (l == r) return ; int mid = (l + r) >> 1; build (lson); build (rson);// push_up (rt); } void updata(int ql, int qr, int l, int r, int rt) { if (ql <= l && r <= qr) { sum[rt] += (r - l + 1); col[rt] += 1; return ; } push_down (rt, r - l + 1); int mid = (l + r) >> 1; if (ql <= mid) updata (ql, qr, lson); if (qr > mid) updata (ql, qr, rson);// push_up (rt); } int query(int ql, int qr, int l, int r, int rt) { if (ql <= l && r <= qr) return sum[rt]; push_down (rt, r - l + 1); int mid = (l + r) >> 1; if (ql <= mid) return query (ql, qr, lson); if (qr > mid) return query (ql, qr, rson); }}st;int x1[N], x2[N], q[N];int X[N*3];int my_binary_search(int l, int r, int key) { while (l <= r) { int mid = (l + r) >> 1; if (X[mid] == key) return mid; if (X[mid] < key) l = mid + 1; else r = mid - 1; } return -1;}int main(void) { int T, cas = 0; scanf ("%d", &T); while (T--) { int n, m; scanf ("%d%d", &n, &m); int tot = 0; for (int i=1; i<=n; ++i) { scanf ("%d%d", &x1[i], &x2[i]); X[tot++] = x1[i]; X[tot++] = x2[i]; } for (int i=1; i<=m; ++i) { scanf ("%d", &q[i]); X[tot++] = q[i]; } sort (X, X + tot); int k = 1; for (int i=1; i

代码2：二分查找

/************************************************* Author        :Running_Time* Created Time  :2015-8-25 8:55:54* File Name     :F.cpp ************************************************/#include 
     
      #include 
      
       #include 
       
        #include 
        
         #include 
         
          #include 
          
           #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 | 1typedef long long ll;const int N = 1e5 + 10;const int INF = 0x3f3f3f3f;const int MOD = 1e9 + 7;int x1[N], x2[N];int n, m;int main(void) { int T, cas = 0; scanf ("%d", &T); while (T--) { scanf ("%d%d", &n, &m); for (int i=1; i<=n; ++i) { scanf ("%d%d", &x1[i], &x2[i]); } sort (x1+1, x1+1+n); sort (x2+1, x2+1+n); printf ("Case #%d:\n", ++cas); for (int i=1; i<=m; ++i) { int p; scanf ("%d", &p); printf ("%d\n", lower_bound (x1+1, x1+1+n, p) - (x1 + 1) - (lower_bound (x2+1, x2+1+n, p) - (x2 + 1))); } } return 0;}

代码3：尺取法

#include 
     
      #include 
      
       #include 
       
        using namespace std;typedef long long ll;typedef pair
        
          P;const int N = 1e5 + 10;const int INF = 0x3f3f3f3f;P p[N], q[N];int ans[N];int n, m;int main(void)    {	int T, cas = 0;	scanf ("%d", &T);	while (T--)	{		scanf ("%d%d", &n, &m);		int tot = 0;		for (int a, b, i=1; i<=n; ++i)	{			scanf ("%d%d", &a, &b);			p[++tot] = P (a, 1);			p[++tot] = P (b + 1, -1);		}		sort (p+1, p+1+tot);		for (int i=1; i<=m; ++i)	{			int x;	scanf ("%d", &x);			q[i] = P (x, i);		}		sort (q+1, q+1+m);		printf ("Case #%d:\n", ++cas);		for (int j=1, cnt=0, i=1; i<=m; ++i)	{			while (j <= tot && p[j].first <= q[i].first)	{				cnt += p[j].second;	++j;			}			ans[q[i].second] = cnt;		}		for (int i=1; i<=m; ++i)	printf ("%d\n", ans[i]);	}    return 0;}

转载于:https://www.cnblogs.com/Running-Time/p/4758324.html

你可能感兴趣的文章