fork download
copy 
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3.  
  4. #define endl     '\n'
  5. #define int      long long
  6.  
  7. const int N = 2e5, oo = 2e18, MOD = 1e9+7;
  8.  
  9.  
  10. int modpow(int b, int p) {
  11.     int res = 1;
  12.     while (p) {
  13.         if (p & 1) res = (b * res) % MOD;
  14.         b = (b * b)  % MOD;
  15.         p >>= 1;
  16.     }
  17.     return res;
  18. }
  19.  
  20. int inv(int a) {
  21.     return modpow(a, MOD - 2);
  22. }
  23.  
  24. vector<int> spf;
  25. void sieve(int n) { // O (n . log(n))
  26.     spf.assign(n + 1,0 );
  27.    vector<bool> is_prime(n+1, true);
  28.    is_prime[0] = is_prime[1] = false;
  29.    for (int i = 2; i <= n; i++) {
  30.       if (is_prime[i]) {
  31.          spf[i] = i;
  32.          for (int j = 2 * i; j <= n; j+=i) {
  33.             is_prime[j] = false;
  34.             if (spf[j] == 0) {
  35.                 spf[j] = i;
  36.             }
  37.          }
  38.       }
  39.    }
  40. }
  41.  
  42.  
  43.  
  44. struct Node2 {
  45.     int sum, lazy = 0;
  46.     bool isLazy = false;
  47.     Node2(){
  48.         sum=oo;
  49.     }
  50.     Node2(int x) : sum(x) {}
  51.     void updateNode(int x, int lx, int rx) {
  52.         sum=min(sum,x);
  53.         lazy=x;
  54.         isLazy=true;
  55.     }
  56. };
  57.  
  58.  
  59. struct SagaraWithLazy2 {
  60. #define leftChild  (node * 2 + 1)
  61. #define rightChild (node * 2 + 2)
  62. #define mid        ((lx + rx >> 1))
  63.  
  64.     int treeSize;
  65.     vector<Node2> segData;
  66.  
  67.     void build(int node, int lx, int rx, vector<int>& arr) {
  68.         if (rx - lx == 1) {
  69.             if (lx < (int)arr.size())
  70.                 segData[node] = Node2(arr[lx]);
  71.             return;
  72.         }
  73.  
  74.         build(leftChild, lx, mid, arr);
  75.         build(rightChild, mid, rx, arr);
  76.  
  77.         segData[node] = merge(segData[leftChild], segData[rightChild]);
  78.     }
  79.  
  80.     Node2 merge(Node2& L, Node2& R) {
  81.         Node2 res = Node2();
  82.         res.sum=min(L.sum,R.sum);
  83.         return res;
  84.     }
  85.  
  86.  
  87.     void propagate(int node, int lx, int rx) {
  88.         if (rx - lx == 1 or !segData[node].isLazy) return;
  89.  
  90.         segData[leftChild].updateNode(segData[node].lazy, lx, mid);
  91.         segData[rightChild].updateNode(segData[node].lazy, mid, rx);
  92.  
  93.         segData[node].isLazy = segData[node].lazy = 0;
  94.     }
  95.  
  96.     void update(int l, int r, int x, int node, int lx, int rx) {
  97.         propagate(node, lx, rx);
  98.  
  99.         if (l >= rx or lx >= r) return;
  100.         if (l <= lx and rx <= r) {
  101.             segData[node].updateNode(x, lx, rx);
  102.             return;
  103.         }
  104.  
  105.         update(l, r, x, leftChild, lx, mid);
  106.         update(l, r, x, rightChild, mid, rx);
  107.  
  108.         segData[node] = merge(segData[leftChild], segData[rightChild]);
  109.     }
  110.  
  111.  
  112.     Node2 query(int l, int r, int node, int lx, int rx) {
  113.         propagate(node, lx, rx);
  114.  
  115.         if (l >= rx or lx >= r) return Node2();
  116.         if (l <= lx and rx <= r) {
  117.             return segData[node];
  118.         }
  119.  
  120.         Node2 left = query(l, r, leftChild, lx, mid);
  121.         Node2 right = query(l, r, rightChild, mid, rx);
  122.  
  123.         return merge(left, right);
  124.     }
  125.  
  126. public:
  127.     SagaraWithLazy2(int n, vector<int>& arr) {
  128.         treeSize = 1;
  129.         while (treeSize < n) treeSize <<= 1;
  130.         segData = vector<Node2>(treeSize << 1);
  131.         build(0, 0, treeSize, arr);
  132.     }
  133.  
  134.     void update(int l, int r, int x) {
  135.         update(l, r, x, 0, 0, treeSize);
  136.     }
  137.  
  138.     int query(int l, int r) {
  139.         Node2 a = query(l, r, 0, 0, treeSize);
  140.         return (a.sum);
  141.     }
  142. #undef LeftChild
  143. #undef RightChild
  144. #undef mid
  145. };
  146.  
  147. struct Node {
  148.     int prod;
  149.     int sum, lazy = 0;
  150.     bool isLazy = false;
  151.  
  152.     Node() :prod(1) { }
  153.     Node(int x) :  prod(x) {}
  154.     void updateNode(int x, int lx, int rx) {
  155.         prod *= modpow(x,rx-lx);
  156.         prod %= MOD;
  157.         if(lazy==0)lazy=1;
  158.         lazy *= x;
  159.         lazy%=MOD;
  160.         isLazy = true;
  161.     }
  162. };
  163.  
  164.  
  165. struct SagaraWithLazy {
  166. #define leftChild  (node * 2 + 1)
  167. #define rightChild (node * 2 + 2)
  168. #define mid        ((lx + rx >> 1))
  169.  
  170.     int treeSize;
  171.     vector<Node> segData;
  172.  
  173.     void build(int node, int lx, int rx, vector<int>& arr) {
  174.         if (rx - lx == 1) {
  175.             if (lx < (int)arr.size())
  176.                 segData[node] = Node(arr[lx]);
  177.             return;
  178.         }
  179.  
  180.         build(leftChild, lx, mid, arr);
  181.         build(rightChild, mid, rx, arr);
  182.  
  183.         segData[node] = merge(segData[leftChild], segData[rightChild]);
  184.     }
  185.  
  186.     Node merge(Node& L, Node& R) {
  187.         Node res = Node();
  188.         res.prod = (L.prod * R.prod) % MOD;
  189.         return res;
  190.     }
  191.  
  192.  
  193.     void propagate(int node, int lx, int rx) {
  194.         if (rx - lx == 1 or !segData[node].isLazy) return;
  195.  
  196.         segData[leftChild].updateNode(segData[node].lazy, lx, mid);
  197.         segData[rightChild].updateNode(segData[node].lazy, mid, rx);
  198.  
  199.         segData[node].isLazy = segData[node].lazy = 0;
  200.     }
  201.  
  202.     void update(int l, int r, int x, int node, int lx, int rx) {
  203.         propagate(node, lx, rx);
  204.  
  205.         if (l >= rx or lx >= r) return;
  206.         if (l <= lx and rx <= r) {
  207.             segData[node].updateNode(x, lx, rx);
  208.             return;
  209.         }
  210.  
  211.         update(l, r, x, leftChild, lx, mid);
  212.         update(l, r, x, rightChild, mid, rx);
  213.  
  214.         segData[node] = merge(segData[leftChild], segData[rightChild]);
  215.     }
  216.  
  217.  
  218.     Node query(int l, int r, int node, int lx, int rx) {
  219.         propagate(node, lx, rx);
  220.  
  221.         if (l >= rx or lx >= r) return Node();
  222.         if (l <= lx and rx <= r) {
  223.             return segData[node];
  224.         }
  225.  
  226.         Node left = query(l, r, leftChild, lx, mid);
  227.         Node right = query(l, r, rightChild, mid, rx);
  228.  
  229.         return merge(left, right);
  230.     }
  231.  
  232. public:
  233.     SagaraWithLazy(int n, vector<int>& arr) {
  234.         treeSize = 1;
  235.         while (treeSize < n) treeSize <<= 1;
  236.         segData = vector<Node>(treeSize << 1);
  237.         build(0, 0, treeSize, arr);
  238.     }
  239.  
  240.     void update(int l, int r, int x) {
  241.         update(l, r, x, 0, 0, treeSize);
  242.     }
  243.  
  244.     int query(int l, int r) {
  245.         Node a = query(l, r, 0, 0, treeSize);
  246.         return (a.prod ) % MOD;
  247.     }
  248. #undef LeftChild
  249. #undef RightChild
  250. #undef mid
  251. };
  252.  
  253.  
  254.  
  255. void solve() {
  256.     int n, q; cin >> n >> q;
  257.     vector<int> a(n),b(n);
  258.     for (int i = 0; i < n; i++) cin >> a[i],b[i]=spf[a[i]];
  259.  
  260.     SagaraWithLazy st(n, a);
  261.  
  262.     SagaraWithLazy2 st2(n,b);
  263.     while (q--) {
  264.         int t; cin >> t;
  265.         if (t == 1) {
  266.             int l, r; cin >> l >> r;
  267.             l--, r--;
  268.             int prod = st.query(l, r + 1);
  269.             int sp = st2.query(l, r + 1);
  270.             cout << (prod * inv(sp)) % MOD << endl;
  271.  
  272.         } else {
  273.             int l, r, x; cin >> l >> r >> x;
  274.             st.update(l-1, r, x);
  275.             st2.update(l-1, r, spf[x]);
  276.  
  277.         }
  278.     }
  279. }
  280.  
  281.  
  282. signed main() {
  283.     ios_base::sync_with_stdio(false); 
  284.     cin.tie(NULL); cout.tie(NULL);
  285.     // #ifndef ONLINE_JUDGE 
  286.     //    freopen("input.txt", "r", stdin); 
  287.     //    freopen("output.txt", "w", stdout); 
  288.     // #endif 
  289.     int t; t = 1;
  290.     sieve(1e7);
  291.     cin >> t;
  292.     while (t--) solve();
  293.     return 0;
  294. }
Success #stdin #stdout 0.36s 82496KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Standard output is empty
https://ideone.com/30HOEc
language:
C++ (gcc 8.3)
created:
2 hours 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!