Hello_MMM

Untitled

Jun 16th, 2021
581
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. #include <iostream>
  2. #include <algorithm>
  3. #include <cmath>
  4. #include <vector>
  5.  
  6. using namespace std;
  7.  
  8. typedef long long ll;
  9.  
  10. vector<pair< ll, ll >> t; // max, min
  11.  
  12. pair<ll, ll> get(ll v, ll tl, ll tr, ll l, ll r) {
  13.     if (tl == l && tr == r) {
  14.         return t[v];
  15.     }
  16.     else {
  17.         ll tm = (tl + tr) / 2;
  18.         if (r <= tm) {
  19.             return get(v * 2, tl, tm, l, r);
  20.         }
  21.         else if (l >= tm + 1) {
  22.             return get(v * 2 + 1, tm + 1, tr, l, r);
  23.         }
  24.         else {
  25.             pair<ll, ll> a = get(v*2, tl, tm, l, tm);
  26.             pair<ll, ll> b = get(v * 2 + 1, tm + 1, tr, tm + 1, r);
  27.             return make_pair(max(a.first, b.first), min(a.second, b.second));
  28.         }
  29.     }
  30. }
  31.  
  32. void update(int pos, int l, int r, int npos, int nv)
  33. {
  34.     if (l == r)
  35.     {
  36.         t[pos].first = nv;
  37.         t[pos].second = nv;
  38.     }
  39.     else
  40.     {
  41.         int m = (l + r) / 2;
  42.         if (npos <= m)
  43.             update(pos * 2, l, m, npos, nv);
  44.         else
  45.             update(pos * 2 + 1, m + 1, r, npos, nv);
  46.         t[pos] = make_pair(max(t[pos * 2].first, t[pos * 2 + 1].first), min(t[pos * 2].second, t[pos * 2 + 1].second));
  47.     }
  48. }
  49.  
  50. void build(ll v, ll tl, ll tr) {
  51.     if (tl == tr) {
  52.         t[v].first = (tl % 12345) * (tl % 12345) % 12345 + ((tl % 23456) * (tl % 23456) % 23456) * (tl % 23456) % 23456;
  53.         t[v].second = t.at(v).first;
  54.     }
  55.     else {
  56.         ll tm = (tl + tr) / 2;
  57.         build(v * 2, tl, tm);
  58.         build(v * 2 + 1, tm + 1, tr);
  59.         t[v] = make_pair(max(t[v * 2].first, t[v * 2 + 1].first), min(t[v * 2].second, t[v * 2 + 1].second));
  60.     }
  61. }
  62.  
  63. int main() {
  64.     ios::sync_with_stdio(false); cin.tie(0); cout.tie(0);
  65.     t.resize(4 * 100000 + 1);
  66.     build(1, 1, 100000);
  67.  
  68.     ll n, x, y;
  69.  
  70.     cin >> n;
  71.  
  72.     for (ll i = 0; i < n; i++) {
  73.         cin >> x >> y;
  74.         if (x > 0) {
  75.             pair<ll, ll> q = get(1, 1, 100000, x, y);
  76.             cout << q.first - q.second << "\n";
  77.         }
  78.         else {
  79.             update(1, 1, 100000, -x, y);
  80.         }
  81.     }
  82.  
  83.  
  84.     return 0;
  85. }
RAW Paste Data