Advertisement
7oSkaaa

J - Batman Fight

Aug 13th, 2022
1,023
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 4.99 KB | None | 0 0
  1. #include <bits/stdc++.h>
  2.  
  3. using namespace std;
  4.  
  5. #define cin_2d(vec, n, m) for(int i = 0; i < n; i++) for(int j = 0; j < m && cin >> vec[i][j]; j++);
  6. #define cout_2d(vec, n, m) for(int i = 0; i < n; i++, cout << "\n") for(int j = 0; j < m && cout << vec[i][j] << " "; j++);
  7. #define fixed(n) fixed << setprecision(n)
  8. #define ceil(n, m) (((n) / (m)) + ((n) % (m) ? 1 : 0))
  9. #define fill(vec, value) memset(vec, value, sizeof(vec));
  10. #define mul_mod(a, b, m) (((a % m) * (b % m)) % m)
  11. #define add_mod(a, b, m) (((a % m) + (b % m)) % m)
  12. #define all(vec) vec.begin(), vec.end()
  13. #define rall(vec) vec.rbegin(), vec.rend()
  14. #define sz(x) int(x.size())
  15. #define debug(x) cout << #x << ": " << (x) << "\n";
  16. #define fi first
  17. #define se second
  18. #define ll long long
  19. #define ull unsigned long long
  20. #define Mod  1'000'000'007
  21. #define OO 2'000'000'000
  22. #define EPS 1e-9
  23. #define PI acos(-1)
  24. template < typename T = int > using Pair = pair < T, T >;
  25. vector < string > RET = {"NO", "YES"};
  26.  
  27. template < typename T = int > istream& operator >> (istream &in, vector < T > &v) {
  28.     for (auto &x : v) in >> x;
  29.     return in;
  30. }
  31.  
  32. template < typename T = int > ostream& operator << (ostream &out, const vector < T > &v) {
  33.     for (const T &x : v) out << x << ' ';
  34.     return out;
  35. }
  36.  
  37. template < typename T = int, int Mode = 0 > struct Segment_Tree {
  38.  
  39.     struct Node {
  40.  
  41.         int val, cnt;
  42.  
  43.         Node(int V = 0, int C = 1) : val(V), cnt(C) {}
  44.    
  45.         Node& operator = (const T rhs){
  46.             val = rhs;
  47.             cnt = 1;
  48.             return *this;
  49.         }
  50.  
  51.     };
  52.  
  53.     int size;
  54.     Node DEFAULT;
  55.     vector < Node > tree;
  56.    
  57.     void intial(int n){
  58.         size = 1, DEFAULT = 0;
  59.         while(size < n) size *= 2;
  60.         tree = vector < Node > (2 * size, DEFAULT);
  61.     }
  62.  
  63.     Segment_Tree(int n){
  64.         intial(n);
  65.     }
  66.  
  67.     // Main operation to do
  68.  
  69.     Node operation(Node a, Node b){
  70.         int GCD = __gcd(a.val, b.val);
  71.         if(GCD == a.val && GCD == b.val) return Node(GCD, a.cnt + b.cnt);
  72.         if(GCD == a.val) return a;
  73.         if(GCD == b.val) return b;
  74.         return Node(GCD, 0);
  75.     }
  76.    
  77.     // If Mode is 1 so the array is 1-based else the array is 0-based
  78.    
  79.     void build(vector < T >& nums, int idx, int lx, int rx){
  80.         if(Mode ? lx >= sz(nums) : lx > sz(nums)) return;
  81.         if(rx == lx) tree[idx] = nums[lx - !Mode];
  82.         else {
  83.             int m = (rx + lx) / 2;
  84.             build(nums, 2 * idx, lx, m);
  85.             build(nums, 2 * idx + 1, m + 1, rx);
  86.             tree[idx] = operation(tree[2 * idx], tree[2 * idx + 1]);
  87.         }
  88.     }
  89.  
  90.     void build(vector < T >& nums){
  91.         build(nums, 1, 1, size);
  92.     }
  93.  
  94.     void update(int i, T v, int idx, int lx, int rx){
  95.         if(rx == lx) tree[idx] = v;
  96.         else {  
  97.             int m = (rx + lx) / 2;
  98.             if(i <= m) update(i, v, 2 * idx, lx, m);
  99.             else update(i, v, 2 * idx + 1, m + 1, rx);
  100.             tree[idx] = operation(tree[2 * idx], tree[2 * idx + 1]);
  101.         }
  102.     }
  103.  
  104.     void update(int i, int v){
  105.         update(i, v, 1, 1, size);
  106.     }
  107.  
  108.     Node query(int l, int r, int idx, int lx, int rx){
  109.         if(lx > r || l > rx) return DEFAULT;
  110.         if(lx >= l && rx <= r) return tree[idx];
  111.         int m = (lx + rx) / 2;
  112.         return operation(query(l, r, 2 * idx, lx, m), query(l, r, 2 * idx + 1, m + 1, rx));
  113.     }
  114.  
  115.     int query(int l, int r){
  116.         return query(l, r, 1, 1, size).cnt;
  117.     }
  118.  
  119.     friend ostream& operator << (ostream &out, const Node &node) {
  120.         out << node.val << ' ' << node.cnt;
  121.         return out;
  122.     }
  123.    
  124. };
  125.  
  126. int n, q;
  127. vector < ll > vertex, path, pos;
  128. vector < Pair < int > > Interval;
  129. vector < vector < int > > adj;
  130.  
  131. void dfs(int u, int p){
  132.     for(auto& v : adj[u]){
  133.         if(v == p) continue;
  134.         dfs(v, u);
  135.         Interval[u].fi = min(Interval[u].fi, Interval[v].fi);
  136.     }
  137.     pos[u] = sz(path);
  138.     if(Interval[u].fi == OO)
  139.         Interval[u].fi = sz(path);
  140.     Interval[u].se = sz(path);
  141.     path.push_back(vertex[u]);
  142. }
  143.  
  144. void Solve(){
  145.     cin >> n >> q;
  146.     vertex = pos = vector < ll > (n + 5);
  147.     Interval = vector < Pair < int > > (n + 5, {OO, OO});
  148.     adj = vector < vector < int > > (n + 5);
  149.     for(int i = 1; i <= n; i++)
  150.         cin >> vertex[i];
  151.     for(int i = 2, u, v; i <= n && cin >> u >> v; i++)
  152.         adj[u].push_back(v), adj[v].push_back(u);
  153.     path.push_back(0);
  154.     dfs(1, 0);
  155.     Segment_Tree < ll, 1 > st(sz(path));
  156.     st.build(path);
  157.     while(q--){
  158.         int t, s, x;
  159.         cin >> t;
  160.         if(t == 1){
  161.             cin >> s >> x;
  162.             st.update(pos[s], x);
  163.         }else {
  164.             cin >> s;
  165.             int l = Interval[s].fi, r = Interval[s].se;
  166.             cout << r - l + 1 - st.query(l, r) << '\n';
  167.         }
  168.     }
  169. }
  170.  
  171. int main(){
  172.     ios_base::sync_with_stdio(false), cin.tie(nullptr), cout.tie(nullptr);
  173.     int t = 1;
  174.     //cin >> t;
  175.     while(t--)
  176.         Solve();
  177.     return 0;
  178. }
  179.  
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement