fork download
copy 
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3. using ll = long long;
  4. using ull = unsigned long long;
  5.  
  6. // ---- Lazy‐Segment‐Tree for range‐assign + range‐OR‐query/popcount ----
  7. struct SegTree {
  8.     int n;
  9.     vector<ull> seg, lazy;
  10.     vector<bool> marked;
  11.     SegTree(int _n): n(_n) {
  12.         seg.assign(4*n, 0);
  13.         lazy.assign(4*n, 0);
  14.         marked.assign(4*n, false);
  15.     }
  16.     void push(int v, int l, int r) {
  17.         if (!marked[v]) return;
  18.         seg[v] = lazy[v];
  19.         if (l < r) {
  20.             for (int c : {v<<1, v<<1|1}) {
  21.                 marked[c] = true;
  22.                 lazy[c]   = lazy[v];
  23.             }
  24.         }
  25.         marked[v] = false;
  26.     }
  27.     void build(int v, int l, int r, vector<ull> &flat) {
  28.         if (l == r) {
  29.             seg[v] = flat[l];
  30.             return;
  31.         }
  32.         int m = (l+r)>>1;
  33.         build(v<<1,   l, m, flat);
  34.         build(v<<1|1, m+1, r, flat);
  35.         seg[v] = seg[v<<1] | seg[v<<1|1];
  36.     }
  37.     void upd(int v, int l, int r, int ql, int qr, ull mask) {
  38.         push(v,l,r);
  39.         if (qr < l || r < ql) return;
  40.         if (ql <= l && r <= qr) {
  41.             marked[v] = true;
  42.             lazy[v]   = mask;
  43.             push(v,l,r);
  44.             return;
  45.         }
  46.         int m = (l+r)>>1;
  47.         upd(v<<1,   l, m, ql, qr, mask);
  48.         upd(v<<1|1, m+1, r, ql, qr, mask);
  49.         seg[v] = seg[v<<1] | seg[v<<1|1];
  50.     }
  51.     ull qry(int v, int l, int r, int ql, int qr) {
  52.         push(v,l,r);
  53.         if (qr < l || r < ql) return 0ULL;
  54.         if (ql <= l && r <= qr) return seg[v];
  55.         int m = (l+r)>>1;
  56.         return qry(v<<1,   l, m, ql, qr)
  57.              | qry(v<<1|1, m+1, r, ql, qr);
  58.     }
  59.     // wrappers:
  60.     void build(vector<ull> &flat) { build(1,1,n,flat); }
  61.     void update(int l, int r, ull mask) { upd(1,1,n,l,r,mask); }
  62.     int query_popcount(int l, int r) {
  63.         ull x = qry(1,1,n,l,r);
  64.         return __builtin_popcountll(x);
  65.     }
  66. };
  67.  
  68. // ---- Euler Tour flattening ----
  69. static const int MAXN = 400000;
  70. vector<int> adj[MAXN+1];
  71. int n, m;
  72. int tin[MAXN+1], tout[MAXN+1];
  73. ull arr_val[MAXN+1];
  74. int timer = 0;
  75. vector<ull> flat; // 1..n
  76.  
  77. void dfs(int u, int p) {
  78.     tin[u] = ++timer;
  79.     flat[timer] = arr_val[u];
  80.     for (int v: adj[u]) {
  81.         if (v == p) continue;
  82.         dfs(v,u);
  83.     }
  84.     tout[u] = timer;
  85. }
  86.  
  87. int main(){
  88.     ios::sync_with_stdio(false);
  89.     cin.tie(nullptr);
  90.  
  91.     cin >> n >> m;
  92.     // read initial bitsets
  93.     for(int i = 1; i <= n; i++){
  94.         int c; 
  95.         cin >> c;
  96.         arr_val[i] = (1ULL << c);
  97.     }
  98.     // read tree edges
  99.     for(int i = 0; i < n-1; i++){
  100.         int u,v;
  101.         cin >> u >> v;
  102.         adj[u].push_back(v);
  103.         adj[v].push_back(u);
  104.     }
  105.  
  106.     // 1) Euler‐tour flatten
  107.     flat.assign(n+1, 0ULL);
  108.     dfs(1, 0);
  109.  
  110.     // 2) Build lazy‐segtree on flat[1..n]
  111.     SegTree st(n);
  112.     st.build(flat);
  113.  
  114.     // 3) Process m operations:
  115.     //    Format (example): 
  116.     //      type=1:   1 u newColor    (assign subtree u to mask=(1<<newColor))
  117.     //      type=2:   2 u              (query popcount over subtree u)
  118.     while(m--){
  119.         int type; 
  120.         cin >> type;
  121.         if(type == 1){
  122.             int u, c;
  123.             cin >> u >> c;
  124.             ull mask = (1ULL << c);
  125.             st.update(tin[u], tout[u], mask);
  126.         } else {
  127.             int u; 
  128.             cin >> u;
  129.             int ans = st.query_popcount(tin[u], tout[u]);
  130.             cout << ans << "\n";
  131.         }
  132.     }
  133.  
  134.  
  135.  
  136.     return 0;
  137. }
  138.  
Success #stdin #stdout 0.01s 18036KB
comments (?)
stdin
copy 
7 10
1 1 1 1 1 1 1
1 2
1 3
1 4
3 5
3 6
3 7
1 3 2
2 1
1 4 3
2 1
1 2 5
2 1
1 6 4
2 1
2 2
2 3
stdout
copy 
2
3
4
5
1
2
https://ideone.com/64QQTB
language:
C++ (gcc 8.3)
created:
7 days ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!