(好题)树状数组+离散化+DFS序+离线/莫队 HDOJ 4358 Boring counting

阅读量：6244 次

发布时间：2019-06-22

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

题意：给你一棵树，树上的每个节点都有树值，给m个查询，问以每个点u为根的子树下有多少种权值恰好出现k次。

分析：首先要对权值离散化，然后要将树形转换为线形，配上图：。然后按照右端点从小到大排序，离线操作：将每一个深度的权值分组到相同权值的cnt中，当sz == k时，用树状数组更新+1，表示在该深度已经存在k个相同的权值，如果>k，之前k个-2(-1是恢复原样，再-1是为下次做准备？)，然后一个点的子树的答案就是 sum (r) - sum (l-1)。

当然，区间离线问题用莫队算法是很好做的。

收获：1. 离散化　　2. DFS序，树形变线形　　3. 离线操作　　4. 莫队算法

代码(树状数组)：

/************************************************* Author        :Running_Time* Created Time  :2015/9/10 星期四 19:15:22* File Name     :I.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;struct Edge { int v, nex;}edge[N*2];struct Query { int l, r, id; Query (int _l = 0, int _r = 0, int _id = 0) : l (_l), r (_r), id (_id) {} bool operator < (const Query &x) const { return r < x.r; }}q[N];struct BIT { int c[N]; void init(void) { memset (c, 0, sizeof (c)); } void updata(int i, int x) { while (i < N) { c[i] += x; i += i & (-i); } } int query(int i) { int ret = 0; while (i) { ret += c[i]; i -= i & (-i); } return ret; }}bit;int head[N], dfn[N], low[N], w[N], p[N], val[N], ans[N];vector
                      
                        cnt[N];int e, dep;void init(void) { memset (head, -1, sizeof (head)); e = 0; dep = 0;}void add_edge(int u, int v) { edge[e].v = v; edge[e].nex = head[u]; head[u] = e++;}bool cmp(int i, int j) { return w[i] < w[j];}void compress(int n) { for (int i=1; i<=n; ++i) p[i] = i; sort (p+1, p+1+n, cmp); int rk = 0, pre = w[p[1]] - 1; for (int i=1; i<=n; ++i) { if (pre != w[p[i]]) { pre = w[p[i]]; w[p[i]] = ++rk; } else { w[p[i]] = rk; } }}void DFS(int u, int fa) { dfn[u] = ++dep; val[dep] = w[u]; for (int i=head[u]; ~i; i=edge[i].nex) { int v = edge[i].v; if (v == fa) continue; DFS (v, u); } low[u] = dep;}int main(void) { int T, cas = 0; scanf ("%d", &T); while (T--) { if (cas) puts (""); printf ("Case #%d:\n", ++cas); int n, k; scanf ("%d%d", &n, &k); init (); for (int i=1; i<=n; ++i) { scanf ("%d", &w[i]); } compress (n); //离散化，升序排序，相同的还是相同的 for (int u, v, i=1; i
                       
                        = k) { if (sz == k) bit.updata (cnt[v][sz-k], 1); else { bit.updata (cnt[v][sz-k-1], -2); //? bit.updata (cnt[v][sz-k], 1); } } while (qu <= m && q[qu].r == i) { ans[q[qu].id] = bit.query (q[qu].r) - bit.query (q[qu].l - 1); qu++; } } for (int i=1; i<=m; ++i) { printf ("%d\n", ans[i]); } } return 0;}

代码(莫队算法)：

/************************************************* Author        :Running_Time* Created Time  :2015/9/10 星期四 19:15:22* File Name     :I.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;struct Edge { int v, nex;}edge[N*2];struct Data { int l, r, id, b; Data () {} Data (int l, int r, int id, int b) : l (l), r (r), id (id), b (b) {} bool operator < (const Data &x) const { if (b == x.b) return r < x.r; else return b < x.b; }}data[N];int head[N], dfn[N], low[N], w[N], p[N], val[N], ans[N];int cnt[N];int n, k, m, e, dep, sum; void init(void) { memset (head, -1, sizeof (head)); e = 0; dep = 0;} void add_edge(int u, int v) { edge[e].v = v; edge[e].nex = head[u]; head[u] = e++;} bool cmp(int i, int j) { return w[i] < w[j];} void compress(int n) { for (int i=1; i<=n; ++i) p[i] = i; sort (p+1, p+1+n, cmp); int rk = 0, pre = w[p[1]] - 1; for (int i=1; i<=n; ++i) { if (pre != w[p[i]]) { pre = w[p[i]]; w[p[i]] = ++rk; } else { w[p[i]] = rk; } }} void DFS(int u, int fa) { dfn[u] = ++dep; val[dep] = w[u]; for (int i=head[u]; ~i; i=edge[i].nex) { int v = edge[i].v; if (v == fa) continue; DFS (v, u); } low[u] = dep;} inline void updata(int x, int c) { cnt[x] += c; if (cnt[x] == k) sum++; else if (c > 0 && cnt[x] == k + 1) sum--; else if (c < 0 && cnt[x] == k - 1) sum--;} void Modui(void) { memset (cnt, 0, sizeof (cnt)); sum = 0; int l = 1, r = 0; for (int i=1; i<=m; ++i) { while (data[i].l < l) updata (val[--l], 1); while (data[i].l > l) updata (val[l], -1), l++; while (data[i].r > r) updata (val[++r], 1); while (data[i].r < r) updata (val[r], -1), r--; ans[data[i].id] = sum; } for (int i=1; i<=m; ++i) { printf ("%d\n", ans[i]); }} int main(void) { int T, cas = 0; scanf ("%d", &T); while (T--) { if (cas) puts (""); printf ("Case #%d:\n", ++cas); scanf ("%d%d", &n, &k); init (); for (int i=1; i<=n; ++i) { scanf ("%d", &w[i]); } compress (n); //离散化，升序排序，相同的还是相同的 for (int u, v, i=1; i

Codeforces Round #136 (Div. 1) B. Little Elephant and Array

分析：估计这是上面那道题的母题(弱化版)，直接套用就行了，现在稍微理解了树状数组的维护方法，配上图：

代码(树状数组)：

/************************************************* Author        :Running_Time* Created Time  :2015/9/11 星期五 18:39:17* File Name     :B.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 n, m;struct BIT { int c[N]; void init(void) { memset (c, 0, sizeof (c)); } void updata(int i, int x) { while (i <= n) { c[i] += x; i += i & (-i); } } int query(int i) { int ret = 0; while (i) { ret += c[i]; i -= i & (-i); } return ret; }}bit;struct Query { int l, r, id; bool operator < (const Query &x) const { return r < x.r; }}q[N];int a[N], ans[N];vector
                      
                        cnt[N];int main(void) { scanf ("%d%d", &n, &m); for (int i=1; i<=n; ++i) scanf ("%d", &a[i]); for (int i=1; i<=m; ++i) { scanf ("%d%d", &q[i].l, &q[i].r); q[i].id = i; } sort (q+1, q+1+m); int qu = 1; for (int i=1; i<=n; ++i) cnt[i].clear (); bit.init (); for (int i=1; i<=n; ++i) { if (a[i] > n) continue; cnt[a[i]].push_back (i); int sz = cnt[a[i]].size (); if (sz >= a[i]) { bit.updata (cnt[a[i]][sz-a[i]], 1); if (sz > a[i]) bit.updata (cnt[a[i]][sz-a[i]-1], -2); if (sz > a[i] + 1) bit.updata (cnt[a[i]][sz-a[i]-2], 1); } while (qu <= m && q[qu].r == i) { ans[q[qu].id] = bit.query (q[qu].r) - bit.query (q[qu].l - 1); qu++; } } for (int i=1; i<=m; ++i) { printf ("%d\n", ans[i]); } return 0;}

代码(莫队)：

/************************************************* Author        :Running_Time* Created Time  :2015/9/11 星期五 20:05:22* File Name     :B_Modui.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;struct Data { int l, r, id, b; bool operator < (const Data &x) const { if (b == x.b) return r < x.r; else return b < x.b; }}data[N];int a[N], ans[N], cnt[N];int n, m, sum;inline void updata(int x, int c) { if (x > n) return ; cnt[x] += c; if (cnt[x] == x) sum++; else if (c > 0 && cnt[x] == x + 1) sum--; else if (c < 0 && cnt[x] == x - 1) sum--;}void Modui(void) { sum = 0; memset (cnt, 0, sizeof (cnt)); int l = 1, r = 0; for (int i=1; i<=m; ++i) { while (data[i].l < l) updata (a[--l], 1); while (data[i].l > l) updata (a[l], -1), l++; while (data[i].r > r) updata (a[++r], 1); while (data[i].r < r) updata (a[r], -1), r--; ans[data[i].id] = sum; } for (int i=1; i<=m; ++i) { printf ("%d\n", ans[i]); }}int main(void) { scanf ("%d%d", &n, &m); int block = (int) sqrt (n + 0.5); for (int i=1; i<=n; ++i) { scanf ("%d", &a[i]); } for (int i=1; i<=m; ++i) { scanf ("%d%d", &data[i].l, &data[i].r); data[i].id = i; data[i].b = data[i].l / block; } sort (data+1, data+1+m); Modui (); return 0;}

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

你可能感兴趣的文章

人工智能和机器学习领域的一些有趣的开源项目