fork download
copy 
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3. using ll = long long;
  4. #define int long long
  5.  
  6. struct Fenwick {
  7.     int n;
  8.     vector<ll> f;
  9.     Fenwick(int n=0){ init(n); }
  10.     void init(int n_){ n = (int)n_; f.assign(n+5, 0); }
  11.     void add(int i, ll delta){
  12.         for(; i <= n; i += i & -i) f[i] += delta;
  13.     }
  14.     void range_add(int l, int r, ll val){
  15.         if(l > r) return;
  16.         add((int)l, val);
  17.         add((int)r + 1, -val);
  18.     }
  19.     ll point_query(int i){
  20.         ll res = 0;
  21.         for(; i > 0; i -= i & -i) res += f[i];
  22.         return res;
  23.     }
  24. };
  25.  
  26. const int MAXN = 200000 + 5;
  27. const int LOG = 20;
  28.  
  29. int N, M, Q;
  30. vector<vector<int>> g;
  31. int up[MAXN][LOG];
  32. int depthArr[MAXN];
  33.  
  34. void dfs_set_parent(int root){
  35.     // iterative DFS to avoid recursion depth issues optionally
  36.     vector<int> st;
  37.     st.reserve(N);
  38.     st.push_back(root);
  39.     up[root][0] = root;
  40.     depthArr[root] = 0;
  41.     vector<int> parent(N+1, -1);
  42.     parent[root] = root;
  43.     while(!st.empty()){
  44.         int u = st.back(); st.pop_back();
  45.         for(int v: g[u]){
  46.             if(parent[v] == -1){
  47.                 parent[v] = u;
  48.                 up[v][0] = u;
  49.                 depthArr[v] = depthArr[u] + 1;
  50.                 st.push_back(v);
  51.             }
  52.         }
  53.     }
  54. }
  55.  
  56. int lca(int a, int b){
  57.     if(a == 0 || b == 0) return a ^ b; // defensive
  58.     if(depthArr[a] < depthArr[b]) swap(a,b);
  59.     int k = depthArr[a] - depthArr[b];
  60.     for(int j = 0; j < LOG; ++j) if(k & (1<<j)) a = up[a][j];
  61.     if(a == b) return a;
  62.     for(int j = LOG-1; j >= 0; --j){
  63.         if(up[a][j] != up[b][j]){
  64.             a = up[a][j];
  65.             b = up[b][j];
  66.         }
  67.     }
  68.     return up[a][0];
  69. }
  70. int distNode(int a, int b){
  71.     int w = lca(a,b);
  72.     return depthArr[a] + depthArr[b] - 2 * depthArr[w];
  73. }
  74.  
  75. // interval map
  76. struct Interval {
  77.     int l, r;
  78.     int pos;
  79. };
  80. map<int, Interval> mp; // key = l (start index)
  81. vector< set<int> > byPos; // byPos[node] stores starting indices l of intervals with pos=node
  82. Fenwick bit;
  83.  
  84. auto splitInterval(int x){
  85.     if(mp.empty()) return mp.end();
  86.     auto it = mp.lower_bound((int)x);
  87.     if(it != mp.end() && it->first == x) return it;
  88.     it = mp.upper_bound((int)x);
  89.     if(it == mp.begin()) return mp.end();
  90.     --it;
  91.     Interval cur = it->second;
  92.     if(cur.r < x) return mp.end();
  93.     // split [l, r] -> [l, x-1] and [x, r]
  94.     int l = cur.l, r = cur.r, p = cur.pos;
  95.     it->second.r = (int)(x - 1);
  96.     mp[(int)x] = {(int)x, r, p};
  97.     byPos[(size_t)p].insert((int)x);
  98.     return mp.find((int)x);
  99. }
  100.  
  101. signed main(){
  102.     ios::sync_with_stdio(false);
  103.     cin.tie(nullptr);
  104.  
  105.     freopen("HSSV.inp", "r", stdin);
  106.     freopen("HSSV.out", "w", stdout);
  107.  
  108.     if(!(cin >> N >> M >> Q)) return 0;
  109.     vector<int> a(M+2);
  110.     for(int i = 1; i <= M; ++i) cin >> a[i];
  111.  
  112.     g.assign(N+1, {});
  113.     for(int i = 0; i < N-1; ++i){
  114.         int u,v; cin >> u >> v;
  115.         g[u].push_back(v);
  116.         g[v].push_back(u);
  117.     }
  118.  
  119.     // init up table to 0
  120.     for(int i=1;i<=N;i++) for(int j=0;j<LOG;j++) up[i][j] = 0;
  121.     // build parents & depth (iterative DFS)
  122.     dfs_set_parent(1);
  123.     // build binary lifting table
  124.     for(int j=1;j<LOG;j++){
  125.         for(int i=1;i<=N;i++){
  126.             int mid = up[i][j-1];
  127.             up[i][j] = up[mid][j-1];
  128.             if(up[i][j] == 0) up[i][j] = up[mid][j-1]; // defensive
  129.         }
  130.     }
  131.  
  132.     // Fenwick init on M employees
  133.     bit.init((int)M);
  134.  
  135.     byPos.assign(N+1, set<int>());
  136.  
  137.     // build initial intervals from array a[1..M], merging adjacent same pos
  138.     int curL = 1;
  139.     for(int i = 2; i <= M+1; ++i){
  140.         if(i == M+1 || a[i] != a[i-1]){
  141.             int l = curL, r = i-1, p = a[l];
  142.             mp[l] = {l, r, p};
  143.             byPos[(size_t)p].insert(l);
  144.             curL = i;
  145.         }
  146.     }
  147.  
  148.     while(Q--){
  149.         int type; cin >> type;
  150.         if(type == 1){
  151.             int u, v; cin >> u >> v;
  152.             if(u < 1 || u > N) continue;
  153.             if(byPos[(size_t)u].empty()) continue;
  154.             vector<int> starts;
  155.             starts.reserve(byPos[(size_t)u].size());
  156.             for(int s : byPos[(size_t)u]) starts.push_back(s);
  157.             for(int s : starts){
  158.                 auto it = mp.find(s);
  159.                 if(it == mp.end()) continue;
  160.                 Interval iv = it->second;
  161.                 if(iv.pos != u) continue;
  162.                 bit.range_add(iv.l, iv.r, (ll)v);
  163.             }
  164.         } else if(type == 2){
  165.             int L, R, z; cin >> L >> R >> z;
  166.             if(L > R) swap(L, R);
  167.             if(L < 1) L = 1;
  168.             if(R > M) R = M;
  169.             if(L > R) continue;
  170.             // split at L and R+1
  171.             splitInterval((int)L);
  172.             splitInterval((int)R + 1);
  173.             auto itL = mp.lower_bound((int)L);
  174.             if(itL == mp.end() || itL->first > R){
  175.                 // there was no existing intervals inside [L,R], simply insert [L,R] at pos z
  176.                 mp[(int)L] = {(int)L, (int)R, z};
  177.                 byPos[(size_t)z].insert((int)L);
  178.             } else {
  179.                 // collect intervals in [L,R]
  180.                 vector<int> toRemoveStarts;
  181.                 vector<Interval> movedIntervals;
  182.                 auto it = itL;
  183.                 while(it != mp.end() && it->first <= R){
  184.                     movedIntervals.push_back(it->second);
  185.                     toRemoveStarts.push_back(it->first);
  186.                     ++it;
  187.                 }
  188.                 for(const Interval &iv : movedIntervals){
  189.                     int l = iv.l, r = iv.r, p = iv.pos;
  190.                     int d = distNode(p, z);
  191.                     if(d != 0) bit.range_add(l, r, - (ll)d);
  192.                     auto itset = byPos[(size_t)p].find(l);
  193.                     if(itset != byPos[(size_t)p].end()) byPos[(size_t)p].erase(itset);
  194.                 }
  195.                 for(int s : toRemoveStarts) mp.erase(s);
  196.                 // insert new interval [L,R] with pos=z
  197.                 mp[(int)L] = {(int)L, (int)R, z};
  198.                 byPos[(size_t)z].insert((int)L);
  199.             }
  200.  
  201.             // merge with previous and next safely: capture keys before erasing
  202.             auto itNew = mp.find((int)L);
  203.             if(itNew != mp.begin()){
  204.                 auto itPrev = itNew; --itPrev;
  205.                 if(itPrev->second.pos == itNew->second.pos && itPrev->second.r + 1 == itNew->second.l){
  206.                     int nl = itPrev->second.l;
  207.                     int nr = itNew->second.r;
  208.                     int p = itNew->second.pos;
  209.                     // erase keys safely
  210.                     byPos[(size_t)p].erase(itPrev->second.l);
  211.                     byPos[(size_t)p].erase(itNew->second.l);
  212.                     mp.erase(itPrev);
  213.                     mp.erase(itNew);
  214.                     mp[nl] = {nl, nr, p};
  215.                     byPos[(size_t)p].insert(nl);
  216.                     itNew = mp.find(nl);
  217.                 }
  218.             }
  219.             // merge with next
  220.             auto itNext = itNew; ++itNext;
  221.             if(itNext != mp.end()){
  222.                 if(itNext->second.pos == itNew->second.pos && itNew->second.r + 1 == itNext->second.l){
  223.                     int nl = itNew->second.l;
  224.                     int nr = itNext->second.r;
  225.                     int p = itNew->second.pos;
  226.                     byPos[(size_t)p].erase(itNew->second.l);
  227.                     byPos[(size_t)p].erase(itNext->second.l);
  228.                     mp.erase(itNew);
  229.                     mp.erase(itNext);
  230.                     mp[nl] = {nl, nr, p};
  231.                     byPos[(size_t)p].insert(nl);
  232.                 }
  233.             }
  234.  
  235.         } else if(type == 3){
  236.             int i; cin >> i;
  237.             if(i < 1 || i > M) {
  238.                 cout << 0 << '\n';
  239.             } else {
  240.                 cout << bit.point_query((int)i) << '\n';
  241.             }
  242.         }
  243.     }
  244.  
  245.     return 0;
  246. }
  247.  
Success #stdin #stdout 0.01s 5284KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Standard output is empty
https://ideone.com/zeZyed
language:
C++14 (gcc 8.3)
created:
6 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!