fork download
copy 
  1. #include<bits/stdc++.h>
  2. #define int long long
  3. #define oo 1000000000000000000
  4. #define ii pair<int, int>
  5. #define fi first
  6. #define se second
  7. #define all(x) x.begin(), x.end()
  8. #define uniq(x) x.erase(unique(all(x)), x.end())
  9. #define pb push_back
  10. using namespace std;
  11. const int mod = 676767677;
  12. const int N = 200005;
  13. const int LOG = 19;
  14.  
  15. /*
  16. Nếu mà mỗi khi một phòng đc thêm tiện tích mà phải duyệt qua mọi nhân viên thì rất mất thời gian 
  17. => bonus[phòng] += val;
  18.  
  19. và đáp án sẽ là bonus[phòng đang ở] + base[]
  20. do truy vấn 2 nên là nó sẽ giống việc update trên đoạn => dùng fenwick tree để update trên đoạn và get tại 1 điểm.
  21.  
  22. đang ở phòng B mà bị chuyển đến phòng A:
  23. đáp án đúng là: base[u] + bonus[B]
  24.  
  25.  
  26. => đáp án lấy ra là: base[u] + bonus[A]
  27. => để đáp án lấy ra đúng => base[u] + bonus[B] - bonus[A]
  28.                             (đây là giá trị đúng mà phải + thêm bonus[A] nữa nên sẽ trừ đi bonus[A])
  29.  
  30. */
  31. struct FenTree {
  32.     vector<int> bit;
  33.     int n;
  34.     void init(int _n) {
  35.         n = _n;
  36.         bit.assign(n + 1, 0);
  37.     }
  38.  
  39.     void update(int pos, int val) {
  40.         for(int i = pos; i <= n; i += i&-i) {
  41.             bit[i] += val;
  42.         }
  43.     }
  44.     void update(int l, int r, int val) {
  45.         update(l, val);
  46.         update(r + 1, -val);
  47.     }
  48.     int get(int pos) {
  49.         int ans = 0;
  50.         for(int i = pos; i >= 1; i -= i&-i) {
  51.             ans += bit[i];
  52.         }
  53.         return ans;
  54.     }
  55. } fen;
  56.  
  57. int f[N][LOG], hi[N];
  58. vector<int> e[N];
  59. void dfs(int u, int p) {
  60.     for(auto v: e[u]) {
  61.         if(v == p) continue;
  62.         f[v][0] = u;
  63.         hi[v] = hi[u] + 1;
  64.         dfs(v, u);
  65.     }
  66. }
  67. int lca(int u, int v) {
  68.     if(hi[u] > hi[v]) swap(u, v);
  69.     for(int i = LOG - 1; i >= 0; i--) {
  70.         if(hi[f[v][i]] >= hi[u]) {
  71.             v = f[v][i];
  72.         }
  73.     }
  74.     if(u == v) return u;
  75.     for(int i = LOG - 1; i >= 0; i--) {
  76.         if(f[u][i] != f[v][i]) {
  77.             u = f[u][i];
  78.             v = f[v][i];
  79.         }
  80.     }
  81.     return f[u][0];
  82. }
  83.  
  84. int kc(int u, int v) {
  85.     return hi[u] + hi[v] - 2 * hi[lca(u, v)];
  86. }
  87.  
  88. struct nhan {
  89.     int l, r, ph;
  90.     nhan(int _l, int _r, int _ph): l(_l), r(_r), ph(_ph) {}
  91.     bool operator < (const nhan &other) const {
  92.         return this->l < other.l;
  93.     }
  94. };
  95. set<nhan> st;
  96. int bonus[N];
  97. int n, m, q;
  98. int a[N];
  99.  
  100. /*
  101. Nếu update 1 đoạn từ L -> R thì để dễ xử lý thì biến mọi đoạn mình xử lý thành 1 đoạn ở trong set
  102. => split tại L và split tại R + 1
  103. */
  104. set<nhan>::iterator split(int pos) {
  105.     if (pos > m) return st.end();
  106.     auto it = prev(st.upper_bound({pos, 0, 0}));
  107.     if (it->l == pos) return it;
  108.     int l = it->l, r = it->r, ph = it->ph;
  109.     st.erase(it);
  110.     st.insert({l, pos - 1, ph});
  111.     return st.insert({pos, r, ph}).first;
  112. }
  113.  
  114.  
  115. void solve() {
  116.     cin >> n >> m >> q;
  117.  
  118.  
  119.     for(int i = 1; i <= m; i++) {
  120.         cin >> a[i];
  121.     }
  122.  
  123.     for(int i = 1; i < n; i++) {
  124.         int u, v;
  125.         cin >> u >> v;
  126.         e[u].pb(v);
  127.         e[v].pb(u);
  128.     }
  129.  
  130.     hi[1] = 1;
  131.     dfs(1, 1);
  132.  
  133.     for(int j = 1; j < LOG; j++) {
  134.         for(int i = 1; i <= n; i++) {
  135.             if(f[i][j - 1]) {
  136.                 f[i][j] = f[f[i][j - 1]][j - 1];
  137.             } 
  138.         }
  139.     }
  140.  
  141.     fen.init(m);
  142.  
  143.     for(int i = 1; i <= m; i++) {
  144.         int pos = i;
  145.         while(pos + 1 <= m && a[i] == a[pos + 1]) pos++;
  146.  
  147.         st.insert(nhan(i, pos, a[pos]));
  148.         i = pos;
  149.     }
  150.  
  151.     while(q--) {
  152.         char c; cin >> c;
  153.         if(c == 'e') {
  154.             int x, v; cin >> x >> v;
  155.             bonus[x] += v;
  156.         }
  157.         else if(c == 't') {
  158.             int l, r, z;
  159.             cin >> l >> r >> z;
  160.  
  161.             auto R = split(r + 1);
  162.             auto L = split(l);
  163.  
  164.  
  165.             for(auto it = L; it != R; it++) {
  166.                 int l = it->l;
  167.                 int r = it->r;
  168.                 int ph = it->ph;
  169.                 int delta = bonus[ph] - bonus[z] - kc(ph, z);
  170.                 fen.update(l, r, delta);
  171.             }
  172.             st.erase(L, R);
  173.             st.insert(nhan(l, r, z));
  174.         }
  175.         else {
  176.             int k;
  177.             cin >> k;
  178.             auto it = prev(st.upper_bound({k, 0, 0}));
  179.             cout << fen.get(k) + bonus[it->ph] << "\n";
  180.         }
  181.     }
  182. }
  183.  
  184. signed main() {
  185.     ios_base::sync_with_stdio(0);
  186.     cin.tie(0); cout.tie(0);
  187.  
  188.     if(fopen("hsnv.inp", "r")) {
  189.         freopen("hsnv.inp", "r", stdin);
  190.         freopen("hsnv.out", "w", stdout);
  191.     }
  192.  
  193.     int t = 1;
  194.     // cin >> t;
  195.     while(t--) {
  196.         solve();
  197.     }
  198. }
  199.  
Success #stdin #stdout 0.01s 9632KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Standard output is empty
https://ideone.com/iSRnd0
language:
C++ (gcc 8.3)
created:
19 days ago
visibility:
secret

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!