fork download
copy 
  1. #include <bits/stdc++.h>
  2. #define endl '\n'
  3.  
  4. using namespace std;
  5. template<class T, class T2> inline void chkmax(T &x, const T2 &y) { if(x < y) x = y; }
  6. template<class T, class T2> inline void chkmin(T &x, const T2 &y) { if(x > y) x = y; }
  7. const int MAXN = (1 << 20);
  8.  
  9. int gcd(int a, int b) { return (a == 0 || b == 0) ? (a + b) : (__gcd(a, b)); }
  10.  
  11. struct segment_tree
  12. {
  13.     struct node
  14.     {
  15.         int64_t sum, lazy;
  16.  
  17.         node() {sum = 0; lazy = 0;}
  18.         node(int64_t val)
  19.         {
  20.             sum = val;
  21.             lazy = 0;
  22.         }
  23.     };
  24.  
  25.     node temp, broken;
  26.  
  27.     node merge(node l, node r)
  28.     {
  29.         temp.sum = l.sum + r.sum;
  30.         temp.lazy = 0;
  31.         return temp;
  32.     }
  33.  
  34.     node tr[4 * MAXN];
  35.  
  36.     void push(int l, int r, int idx)
  37.     {
  38.         if(tr[idx].lazy)
  39.         {
  40.             tr[idx].sum = (r - l + 1) * tr[idx].lazy;
  41.  
  42.             if(l != r)
  43.             {
  44.                 tr[2 * idx + 1].lazy = tr[idx].lazy;
  45.                 tr[2 * idx + 2].lazy = tr[idx].lazy;
  46.             }
  47.  
  48.             tr[idx].lazy = 0;
  49.         }
  50.     }
  51.  
  52.     void init(int l, int r, int idx)
  53.     {
  54.         if(l == r)
  55.         {
  56.             tr[idx] = node(0);
  57.             return;
  58.         }
  59.  
  60.         int mid = (l + r) >> 1;
  61.         init(l, mid, 2 * idx + 1);
  62.         init(mid + 1, r, 2 * idx + 2);
  63.  
  64.         tr[idx] = merge(tr[2 * idx + 1], tr[2 * idx + 2]);
  65.     }
  66.  
  67.     void update(int qL, int qR, int val, int l, int r, int idx)
  68.     {
  69.         push(l, r, idx);
  70.  
  71.         if(qL > r || l > qR)
  72.             return;
  73.  
  74.         if(qL <= l && r <= qR)
  75.         {
  76.             tr[idx].lazy = val;
  77.             push(l, r, idx);
  78.             return;
  79.         }
  80.  
  81.         int mid = (l + r) >> 1;
  82.         update(qL, qR, val, l, mid, 2 * idx + 1);
  83.         update(qL, qR, val, mid + 1, r, 2 * idx + 2);
  84.  
  85.         tr[idx] = merge(tr[2 * idx + 1], tr[2 * idx + 2]);
  86.     }
  87.  
  88.     node query(int qL, int qR, int l, int r, int idx)
  89.     {
  90.         push(l, r, idx);
  91.  
  92.         if(l > qR || r < qL)
  93.             return broken;
  94.  
  95.         if(qL <= l && r <= qR)
  96.             return tr[idx];
  97.  
  98.         int mid = (l + r) >> 1;
  99.         return merge(query(qL, qR, l, mid, 2 * idx + 1), query(qL, qR, mid + 1, r, 2 * idx + 2));
  100.     }
  101. };
  102.  
  103. segment_tree sum_t;
  104.  
  105. struct node
  106. {
  107.     int g;
  108.     node() { g = 0; }
  109.     node(int val) { g = val; }
  110. };
  111.  
  112. int a[MAXN];
  113. node temp, broken;
  114.  
  115. node merge(node l, node r)
  116. {
  117.     temp.g = gcd(l.g, r.g);
  118.     return temp;
  119. }
  120.  
  121. int bound_L[MAXN], bound_R[MAXN];
  122. struct segment_tree_gcd
  123. {
  124.     node tr[4 * MAXN];
  125.  
  126.     void init(int l, int r, int idx)
  127.     {
  128.         bound_L[idx] = l;
  129.         bound_R[idx] = r;
  130.         if(l == r)
  131.         {
  132.             tr[idx] = node(a[l]);
  133.             return;
  134.         }
  135.  
  136.         int mid = (l + r) >> 1;
  137.         init(l, mid, 2 * idx + 1);
  138.         init(mid + 1, r, 2 * idx + 2);
  139.  
  140.         tr[idx] = merge(tr[2 * idx + 1], tr[2 * idx + 2]);
  141.     }
  142.  
  143.     void update(int pos, int val, int l, int r, int idx)
  144.     {
  145.         if(l > pos || r < pos)
  146.             return;
  147.  
  148.         if(l == r && l == pos)
  149.         {
  150.             tr[idx].g = val;
  151.             return;
  152.         }
  153.  
  154.         int mid = (l + r) >> 1;
  155.         update(pos, val, l, mid, 2 * idx + 1);
  156.         update(pos, val, mid + 1, r, 2 * idx + 2);
  157.  
  158.         tr[idx] = merge(tr[2 * idx + 1], tr[2 * idx + 2]);
  159.     }
  160.  
  161.     void get_nodes(int qL, int qR, int l, int r, int idx, vector<int> &li)
  162.     {
  163.         if(l > qR || r < qL) return;
  164.         if(qL <= l && r <= qR)
  165.         {
  166.             li.push_back(idx);
  167.             return;
  168.         }
  169.  
  170.         int mid = (l + r) >> 1;
  171.         get_nodes(qL, qR, l, mid, 2 * idx + 1, li);
  172.         get_nodes(qL, qR, mid + 1, r, 2 * idx + 2, li);
  173.     }
  174.  
  175.     int get_left(int l, int r, int idx, int X)
  176.     {
  177.         if(l == r) return l;
  178.  
  179.         int mid = (l + r) >> 1, new_gcd = gcd(X, tr[2 * idx + 2].g);
  180.         if(new_gcd == 1) return get_left(mid + 1, r, 2 * idx + 2, X);
  181.         else return get_left(l, mid, 2 * idx + 1, new_gcd);
  182.     }
  183.  
  184.     int get_left_same(int l, int r, int idx, int X)
  185.     {
  186.         if(l == r) return l;
  187.  
  188.         int mid = (l + r) >> 1, new_gcd = gcd(X, tr[2 * idx + 2].g);
  189.         if(new_gcd != X) return get_left_same(mid + 1, r, 2 * idx + 2, X);
  190.         else return get_left_same(l, mid, 2 * idx + 1, new_gcd);
  191.     }
  192.  
  193.     int get_right(int l, int r, int idx, int X)
  194.     {
  195.         if(l == r) return l;
  196.  
  197.         int mid = (l + r) >> 1, new_gcd = gcd(X, tr[2 * idx + 1].g);
  198.         if(new_gcd == 1) return get_right(l, mid, 2 * idx + 1, X);
  199.         else return get_right(mid + 1, r, 2 * idx + 2, new_gcd);
  200.     }
  201. };
  202.  
  203. int n;
  204. segment_tree_gcd t;
  205.  
  206. int get_left(int pos)
  207. {
  208.     vector<int> li;
  209.     t.get_nodes(1, pos, 1, n, 0, li);
  210.     reverse(li.begin(), li.end());
  211.  
  212.     int c_gcd = 0;
  213.     for(int it: li)
  214.     {
  215.         int prv_gcd = c_gcd;
  216.         c_gcd = gcd(c_gcd, t.tr[it].g);
  217.         if(c_gcd == 1) return t.get_left(bound_L[it], bound_R[it], it, prv_gcd);
  218.     }
  219.  
  220.     return 0;
  221. }
  222.  
  223. int get_right(int pos)
  224. {
  225.     vector<int> li;
  226.     t.get_nodes(pos, n, 1, n, 0, li);
  227.  
  228.     int c_gcd = 0;
  229.     for(int it: li)
  230.     {
  231.         int prv_gcd = c_gcd;
  232.         c_gcd = gcd(c_gcd, t.tr[it].g);
  233.         if(c_gcd == 1) return t.get_right(bound_L[it], bound_R[it], it, prv_gcd);
  234.     }
  235.  
  236.     return n + 1;
  237. }
  238.  
  239. int get_left_equal(int pos, int G)
  240. {    
  241.     vector<int> li;
  242.     t.get_nodes(1, pos, 1, n, 0, li);
  243.     reverse(li.begin(), li.end());
  244.  
  245.     int c_gcd = G;
  246.     for(int it: li)
  247.     {
  248.         int prv_gcd = c_gcd;
  249.         c_gcd = gcd(c_gcd, t.tr[it].g);
  250.         if(c_gcd < G) return t.get_left_same(bound_L[it], bound_R[it], it, prv_gcd);
  251.     }
  252.  
  253.     return 0;
  254. }
  255.  
  256. void update_value(int pos, int val)
  257. {
  258.     int L_pos = get_left(pos) + 1;
  259.     if(a[pos] == 1) L_pos = pos;
  260.  
  261.     t.update(pos, val, 1, n, 0);
  262.     sum_t.update(L_pos, pos, pos, 1, n, 0);
  263.     a[pos] = val;
  264.  
  265.     int g = a[pos], curr = pos;
  266.     while(g != 1 && curr > 0)
  267.     {
  268.         int j = get_left_equal(curr, g);
  269.  
  270.         int new_r_value = get_right(j + 1);
  271.         t.update(pos, a[pos], 1, n, 0);
  272.  
  273.         sum_t.update(j + 1, curr, new_r_value, 1, n, 0);
  274.         curr = j;
  275.  
  276.         if(curr > 0) g = gcd(g, a[curr]);
  277.     }
  278. }
  279.  
  280. void update_naive(int pos, int val)
  281. {
  282.     a[pos] = val;
  283.     t.update(pos, val, 1, n, 0);
  284.     for(int i = 1; i <= n; i++)
  285.         sum_t.update(i, i, get_right(i), 1, n, 0);
  286. }
  287.  
  288. int get_r_value(int pos) { return sum_t.query(pos, pos, 1, n, 0).sum; }
  289.  
  290. int q;
  291.  
  292. void read()
  293. {
  294.     cin >> n >> q; 
  295.     for(int i = 1; i <= n; i++)
  296.         cin >> a[i];
  297. }
  298.  
  299. int64_t query(int L, int R)
  300. {
  301.     int64_t ans = 0;
  302.  
  303.     int low = L, high = R, mid, r = R + 1;
  304.     while(low <= high)
  305.     {
  306.         mid = (low + high) >> 1;
  307.         if(get_r_value(mid) > R)
  308.             r = mid, high = mid - 1;
  309.         else 
  310.             low = mid + 1;
  311.     }
  312.  
  313.     ans -= ((R + 1ll) * 1ll * (R)) / 2ll;
  314.     ans += ((L - 1ll) * 1ll * (L)) / 2ll;
  315.  
  316.     ans += (R - r + 1ll) * 1ll * (R + 1ll);
  317.     if(L < r) ans += sum_t.query(L, r - 1, 1, n, 0).sum;
  318.  
  319.     return ans;
  320. }
  321.  
  322. void solve()
  323. {
  324.     t.init(1, n, 0);
  325.     sum_t.init(1, n, 0);    
  326.  
  327.     for(int i = 1; i <= n; i++)
  328.         update_value(i, a[i]);
  329.         //update_naive(i, a[i]);
  330.  
  331.     while(q--)
  332.     {
  333.         int type;
  334.         cin >> type;
  335.  
  336.         if(type == 1)
  337.         {
  338.             int pos, val;
  339.             cin >> pos >> val;
  340.             update_value(pos, val);
  341.             //update_naive(pos, val);
  342.         }
  343.         else
  344.         {
  345.             int l, r;
  346.             cin >> l >> r;
  347.             cout << query(l, r) << endl;
  348.         }
  349.     }
  350. }
  351.  
  352. int main()
  353. {
  354.     ios_base::sync_with_stdio(false);
  355.     cin.tie(NULL);
  356.  
  357.     read();
  358.     solve();
  359.     return 0;
  360. }
Runtime error #stdin #stdout 0.01s 110336KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Standard output is empty
https://ideone.com/IbWB0z
language:
C++ (gcc 8.3)
created:
7 years 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!