fork download
copy 
  1. #include<bits/stdc++.h>
  2. using namespace std;using ll=long long;const int maxN=1e7+5;
  3. using ll = long long;
  4. const int MOD = 1e9 + 7;
  5.  
  6. template<ll M>
  7. struct modint {
  8.  
  9.     static ll _pow(ll n, ll k) {
  10.         ll r = 1;
  11.         for (; k > 0; k >>= 1, n = (n*n)%M)
  12.             if (k&1) r = (r*n)%M;
  13.         return r;
  14.     }
  15.  
  16.     ll v; modint(ll n = 0) : v(n%M) { v += (M&(0-(v<0))); }
  17.  
  18.     friend string to_string(const modint n) { return to_string(n.v); }
  19.     friend istream& operator>>(istream& i, modint& n) { return i >> n.v; }
  20.     friend ostream& operator<<(ostream& o, const modint n) { return o << n.v; }
  21.     template<typename T> explicit operator T() { return T(v); }
  22.  
  23.     friend bool operator==(const modint n, const modint m) { return n.v == m.v; }
  24.     friend bool operator!=(const modint n, const modint m) { return n.v != m.v; }
  25.     friend bool operator<(const modint n, const modint m) { return n.v < m.v; }
  26.     friend bool operator<=(const modint n, const modint m) { return n.v <= m.v; }
  27.     friend bool operator>(const modint n, const modint m) { return n.v > m.v; }
  28.     friend bool operator>=(const modint n, const modint m) { return n.v >= m.v; }
  29.  
  30.     modint& operator+=(const modint n) { v += n.v; v -= (M&(0-(v>=M))); return *this; }
  31.     modint& operator-=(const modint n) { v -= n.v; v += (M&(0-(v<0))); return *this; }
  32.     modint& operator*=(const modint n) { v = (v*n.v)%M; return *this; }
  33.     modint& operator/=(const modint n) { v = (v*_pow(n.v, M-2))%M; return *this; }
  34.     friend modint operator+(const modint n, const modint m) { return modint(n) += m; }
  35.     friend modint operator-(const modint n, const modint m) { return modint(n) -= m; }
  36.     friend modint operator*(const modint n, const modint m) { return modint(n) *= m; }
  37.     friend modint operator/(const modint n, const modint m) { return modint(n) /= m; }
  38.     modint& operator++() { return *this += 1; }
  39.     modint& operator--() { return *this -= 1; }
  40.     modint operator++(int) { modint t = *this; return *this += 1, t; }
  41.     modint operator--(int) { modint t = *this; return *this -= 1, t; }
  42.     modint operator+() { return *this; }
  43.     modint operator-() { return modint(0) -= *this; }
  44.  
  45.     modint pow(const ll k) const {
  46.         return k < 0 ? _pow(v, M-1-(-k%(M-1))) : _pow(v, k);
  47.     }
  48.     modint inv() const { return _pow(v, M-2); }
  49. };
  50.  
  51. using mint = modint<int(MOD)>;
  52. // check add
  53. class segtree {
  54.     public:
  55.     struct node {
  56.         mint mul = 1;
  57.         mint add = 1;
  58.  
  59.         void apply(int l, int r, mint x) {
  60.             mul = mul*(x.pow(r-l+1));
  61.             add = add*x;
  62.         }
  63.     };
  64.  
  65.     node unite(const node &a, const node &b) const {
  66.         node res;
  67.         res.mul = a.mul*b.mul;
  68.         return res;
  69.     }
  70.  
  71.     inline void push(int x, int l, int r) {
  72.         int y = (l + r) >> 1;
  73.         int z = x + ((y - l + 1) << 1);
  74.         if (tree[x].add != 1) { // it's wrong because of me
  75.             tree[x + 1].apply(l, y, tree[x].add);
  76.             tree[z].apply(y + 1, r, tree[x].add);
  77.             tree[x].add = 1;
  78.         }
  79.     }
  80.  
  81.     inline void pull(int x, int z) {
  82.         tree[x] = unite(tree[x + 1], tree[z]);
  83.     }
  84.  
  85.     int n;
  86.     vector<node> tree;
  87.  
  88.     template <typename M>
  89.     void build(int x, int l, int r, const vector<M> &v) {
  90.         if (l == r) {
  91.             tree[x].apply(l, r, v[l]);
  92.             return;
  93.         }
  94.         int y = (l + r) >> 1;
  95.         int z = x + ((y - l + 1) << 1);
  96.         build(x + 1, l, y, v);
  97.         build(z, y + 1, r, v);
  98.         pull(x, z);
  99.     }
  100.  
  101.     node query(int x, int l, int r, int LL, int rr) {
  102.         if (LL <= l && r <= rr) {
  103.             return tree[x];
  104.         }
  105.         int y = (l + r) >> 1;
  106.         int z = x + ((y - l + 1) << 1);
  107.         push(x, l, r);
  108.         node res{};
  109.         if (rr <= y) {
  110.             res = query(x + 1, l, y, LL, rr);
  111.         } 
  112.         else{
  113.             if (LL > y) {
  114.                 res = query(z, y + 1, r, LL, rr);
  115.             } 
  116.             else{
  117.                 res = unite(query(x + 1, l, y, LL, rr), query(z, y + 1, r, LL, rr));
  118.             }
  119.         }
  120.         pull(x, z);
  121.         return res;
  122.     }
  123.  
  124.     template <typename... M>
  125.     void update(int x, int l, int r, int LL, int rr, const M&... v) {
  126.         if (LL <= l && r <= rr) {
  127.             tree[x].apply(l, r, v...);
  128.             return;
  129.         }
  130.         int y = (l + r) >> 1;
  131.         int z = x + ((y - l + 1) << 1);
  132.         push(x, l, r);
  133.         if (LL <= y) {
  134.             update(x + 1, l, y, LL, rr, v...);
  135.         }
  136.         if (rr > y) {
  137.             update(z, y + 1, r, LL, rr, v...);
  138.         }
  139.         pull(x, z);
  140.     }
  141.  
  142.     template <typename M>
  143.     segtree(const vector<M> &v) {
  144.         n = v.size();
  145.         assert(n > 0);
  146.         tree.resize(2 * n - 1);
  147.         build(0, 0, n - 1, v);
  148.     }
  149.  
  150.     node query(int LL, int rr) {
  151.         if(LL > rr)
  152.             return {};
  153.         assert(0 <= LL && LL <= rr && rr <= n - 1);
  154.         return query(0, 0, n - 1, LL, rr);
  155.     }
  156.  
  157.     template <typename... M>
  158.     void update(int LL, int rr, const M&... v) {
  159.         assert(0 <= LL && LL <= rr && rr <= n - 1);
  160.         update(0, 0, n - 1, LL, rr, v...);
  161.     }
  162. };
  163. class segtree2 {
  164.     public:
  165.     struct node {
  166.         int mn = 1e9;
  167.         int add = 1e9;
  168.         void apply(int l, int r, int x) {
  169.             mn = min(mn,x);
  170.             add = min(add,x);
  171.         }
  172.     };
  173.  
  174.     node unite(const node &a, const node &b) const {
  175.         node res;
  176.         res.mn=min(a.mn,b.mn);
  177.         return res;
  178.     }
  179.  
  180.     inline void push(int x, int l, int r) {
  181.         int y = (l + r) >> 1;
  182.         int z = x + ((y - l + 1) << 1);
  183.         if (tree[x].add != 1e9) { // it's wrong because of me
  184.             tree[x + 1].apply(l, y, tree[x].add);
  185.             tree[z].apply(y + 1, r, tree[x].add);
  186.             tree[x].add = 1e9;
  187.         }
  188.     }
  189.  
  190.     inline void pull(int x, int z) {
  191.         tree[x] = unite(tree[x + 1], tree[z]);
  192.     }
  193.  
  194.     int n;
  195.     vector<node> tree;
  196.  
  197.     template <typename M>
  198.     void build(int x, int l, int r, const vector<M> &v) {
  199.         if (l == r) {
  200.             tree[x].apply(l, r, v[l]);
  201.             return;
  202.         }
  203.         int y = (l + r) >> 1;
  204.         int z = x + ((y - l + 1) << 1);
  205.         build(x + 1, l, y, v);
  206.         build(z, y + 1, r, v);
  207.         pull(x, z);
  208.     }
  209.  
  210.     node query(int x, int l, int r, int LL, int rr) {
  211.         if (LL <= l && r <= rr) {
  212.             return tree[x];
  213.         }
  214.         int y = (l + r) >> 1;
  215.         int z = x + ((y - l + 1) << 1);
  216.         push(x, l, r);
  217.         node res{};
  218.         if (rr <= y) {
  219.             res = query(x + 1, l, y, LL, rr);
  220.         } 
  221.         else{
  222.             if (LL > y) {
  223.                 res = query(z, y + 1, r, LL, rr);
  224.             } 
  225.             else{
  226.                 res = unite(query(x + 1, l, y, LL, rr), query(z, y + 1, r, LL, rr));
  227.             }
  228.         }
  229.         pull(x, z);
  230.         return res;
  231.     }
  232.  
  233.     template <typename... M>
  234.     void update(int x, int l, int r, int LL, int rr, int val) {
  235.         // if(tree[x].mn<=val){
  236.         // }
  237.         if (LL <= l && r <= rr) {
  238.             tree[x].apply(l, r, val);
  239.             return;
  240.         }
  241.         int y = (l + r) >> 1;
  242.         int z = x + ((y - l + 1) << 1);
  243.         push(x, l, r);
  244.         if (LL <= y) {
  245.             update(x + 1, l, y, LL, rr, val);
  246.         }
  247.         if (rr > y) {
  248.             update(z, y + 1, r, LL, rr, val);
  249.         }
  250.         pull(x, z);
  251.     }
  252.  
  253.     template <typename M>
  254.     segtree2(const vector<M> &v) {
  255.         n = v.size();
  256.         assert(n > 0);
  257.         tree.resize(2 * n - 1);
  258.         build(0, 0, n - 1, v);
  259.     }
  260.  
  261.     node query(int LL, int rr) {
  262.         if(LL > rr)
  263.             return {};
  264.         assert(0 <= LL && LL <= rr && rr <= n - 1);
  265.         return query(0, 0, n - 1, LL, rr);
  266.     }
  267.  
  268.     template <typename... M>
  269.     void update(int LL, int rr, int x) {
  270.         assert(0 <= LL && LL <= rr && rr <= n - 1);
  271.         update(0, 0, n - 1, LL, rr, x);
  272.     }
  273. };
  274. int spf[maxN],lst[maxN];
  275. vector<int> prms;
  276. void pre(){
  277.     for(int i = 2;i<maxN;++i){
  278.         if(spf[i]==0){
  279.             spf[i] = i;
  280.             prms.push_back(i);
  281.         }
  282.         for(auto&p:prms){
  283.             if(p*i>=maxN||p>spf[i]) break;
  284.             spf[p*i]=p;
  285.         }
  286.     }
  287.     for(int i=1;i<maxN;++i){
  288.         if(spf[i]==i) lst[i] = i;
  289.         else lst[i] = lst[i-1];
  290.     }
  291. }
  292. void solve(){
  293.     int n;cin>>n;
  294.     int q;cin>>q;
  295.     vector<int> a(n+1), b(n+1);
  296.     for(int i=1;i<=n;++i){
  297.         cin>>a[i];
  298.         b[i]=spf[a[i]];
  299.     }
  300.     segtree st1(a);
  301.     segtree2 st2(b);
  302.  
  303.     while(q--){
  304.         ll type, l,r;cin>>type>>l>>r;
  305.         if(type==1){
  306.             mint mul = st1.query(l,r).mul;
  307.             mint mn = st2.query(l,r).mn;
  308.             mul/=mn;
  309.             // cout << mul << " " << mn << '\n';
  310.             cout<<mul<<'\n';
  311.         }
  312.         else{
  313.             int x;cin>>x;
  314.             st1.update(l,r,x);
  315.             st2.update(l,r,spf[x]);
  316.         }
  317.     }
  318. }
  319. int32_t main(){ios_base::sync_with_stdio(0); cin.tie(0);
  320. pre();
  321. int tt=1;cin>>tt;while(tt--)
  322. solve();return 0;}
Success #stdin #stdout 0.09s 84844KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Standard output is empty
https://ideone.com/6MT1UR
F2 nucpa online 2026
language:
C++14 (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!