fork download 
  1. #include <bits/stdc++.h>
  2.  
  3. #define  all(v) v.begin(),v.end()
  4. using namespace std;
  5. #define ll long long
  6. const int N = 5e5 + 10;
  7. const double EPS = 1e-9;
  8. const double PI = acos(-1);
  9. #define MAX 1000007
  10. #define  ld long double
  11. #define INF 3e9
  12. //#define  endl  '\n'
  13.  
  14. const ll mod1 = 17, mod2 = 5882353;
  15.  
  16. ll fst(ll a, ll b, ll mod){
  17.     a  = (a % mod + mod) % mod;
  18.     ll res = 1;
  19.     while(b){
  20.         if(b & 1) res = res * a % mod;
  21.         a = a * a % mod;
  22.         b >>= 1;
  23.     }
  24.     return res;
  25. }
  26. using T = __int128;
  27. // ax + by = __gcd(a, b)
  28. // returns __gcd(a, b)
  29. T extended_euclid(T a, T b, T &x, T &y) {
  30.     T xx = y = 0;
  31.     T yy = x = 1;
  32.     while (b) {
  33.         T q = a / b;
  34.         T t = b; b = a % b; a = t;
  35.         t = xx; xx = x - q * xx; x = t;
  36.         t = yy; yy = y - q * yy; y = t;
  37.     }
  38.     return a;
  39. }
  40. // finds x such that x % m1 = a1, x % m2 = a2. m1 and m2 may not be coprime
  41. // here, x is unique modulo m = lcm(m1, m2). returns (x, m). on failure, m = -1.
  42. pair<T, T> CRT(T a1, T m1, T a2, T m2) {
  43.     T p, q;
  44.     T g = extended_euclid(m1, m2, p, q);
  45.     if (a1 % g != a2 % g) return make_pair(0, -1);
  46.     T m = m1 / g * m2;
  47.     p = (p % m + m) % m;
  48.     q = (q % m + m) % m;
  49.     return make_pair((p * a2 % m * (m1 / g) % m + q * a1 % m * (m2 / g) % m) %  m, m);
  50. }
  51.  
  52. struct SegTree{
  53.     vector<ll> mul, add, base;
  54.     ll mod;
  55.     int n;
  56.     SegTree(int n) : n(n), mul(2*n, 1), add(2*n), base(n){}
  57.     void build(vector<ll> &b){
  58.         for (int i = 0; i < b.size(); ++i) {
  59.             base[i] = (b[i] % mod + mod) % mod;
  60.         }
  61.     }
  62.     void apply(int idx, ll m0, ll a0){
  63.         add[idx] = (add[idx] * m0 % mod + a0) % mod;
  64.         mul[idx] = (mul[idx] * m0) % mod;
  65.     }
  66.     void push(int idx, int l, int r){
  67.         if(add[idx] != 0 || mul[idx] != 1){
  68.             int mid = (l + r) / 2;
  69.             apply(idx + 1, mul[idx], add[idx]);
  70.             apply(idx + 2 * (mid - l + 1), mul[idx], add[idx]);
  71.             add[idx] = 0, mul[idx] = 1;
  72.         }
  73.     }
  74.     void upd(int idx, int tl, int tr, int l, int r, ll m0, ll a0){
  75.         if(tl > r || tr < l) return;
  76.         if(tl >= l && tr <= r){
  77.             apply(idx, m0, a0);
  78.             return;
  79.         }
  80.         push(idx, tl, tr);
  81.         int mid = (tl + tr) / 2;
  82.         upd(idx + 1, tl, mid, l, r, m0, a0);
  83.         upd(idx + 2 * (mid - tl + 1), mid + 1, tr, l, r, m0, a0);
  84.     }
  85.     ll query(int idx, int l, int r, int pos){
  86.         if(l == r){
  87.             return (base[l] * mul[idx] % mod + add[idx]) % mod;
  88.         }
  89.         push(idx, l, r);
  90.         int mid = (l + r) / 2;
  91.         if(pos <= mid) return query(idx + 1, l, mid, pos);
  92.         return query(idx + 2 * (mid - l + 1), mid + 1, r, pos);
  93.     }
  94. };
  95. void sol() {
  96.     int g; cin >> g;
  97.  
  98.     SegTree a(g), b(g);
  99.     a.mod = mod1, b.mod = mod2;
  100.     vector<ll> v(g + 1);
  101.     int curr_sz = 0;
  102.     int sz = g;
  103.     int j = 0;
  104.     vector<vector<ll>> qt(g);
  105.     vector<ll> base;
  106.  
  107.  
  108.  
  109.     for (int i = 0; i < g; ++i) {
  110.         int t; cin >> t;
  111.         if(t == 3){
  112.             ll p, q; cin >> p >> q;
  113.             qt[i] = {t, p, q};
  114.         } else{
  115.             ll x; cin >> x;
  116.             qt[i] = {t, x};
  117.             if(t == 1){
  118.                 base.push_back(x);
  119.             }
  120.         }
  121.     }
  122.     a.build(base), b.build(base);
  123.     for(int i = 0; i < g; ++i){
  124.         int t = qt[i][0];
  125.         if(t == 2){
  126.             ll x = qt[i][1];
  127.             ll x1 = (x % mod1 + mod1) % mod1;
  128.             ll x2 = (x % mod2 + mod2) % mod2;
  129.             a.upd(1, 0, sz - 1, 0, curr_sz - 1, 1, x1);
  130.             b.upd(1, 0, sz - 1, 0, curr_sz - 1, 1, x2);
  131.  
  132.         } else if(t == 3){
  133.             ll p = qt[i][1], q = qt[i][2];
  134.             ll q1 = fst(q, mod1 - 2, mod1), q2 = fst(q, mod2 - 2, mod2);
  135.             ll p1 = (p % mod1 + mod1) % mod1, p2 = (p % mod2 + mod2) % mod2;
  136.             a.upd(1, 0, sz - 1, 0, curr_sz - 1, p1 * q1 % mod1, 0);
  137.             b.upd(1, 0, sz - 1, 0, curr_sz - 1, p2 * q2 % mod2, 0);
  138.         } else if(t == 1){
  139.             v[j] = curr_sz;
  140.             curr_sz++;
  141.         } else{
  142.             int p = qt[i][1]; p--;
  143.             ll v1 = a.query(1, 0, sz - 1, v[p]), v2 = b.query(1, 0, sz - 1, v[p]);
  144.             cout << (ll)CRT(v1, mod1, v2, mod2).first << '\n';
  145.         }
  146.         ++j;
  147.     }
  148. }
  149.  
  150. signed main() {
  151.  
  152.     ios::sync_with_stdio(0);
  153.     cin.tie(0);
  154.     int t = 1;
  155. //    cin >> t;
  156.     while (t--) {
  157.         sol();
  158.     }
  159.  
  160. }
Success #stdin #stdout 0.01s 5268KB
comments (?)
stdin 
Standard input is empty
stdout 
Standard output is empty
https://ideone.com/sXZvx6
language:
C++14 (gcc 8.3)
created:
2 days 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!