SHARE
TWEET

Untitled

a guest Apr 18th, 2019 61 Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. #include <bits/stdc++.h>
  2.  
  3. using namespace std;
  4.  
  5. long long a[100001], t[400004][2];
  6.  
  7. void build(int v, int tl, int tr)
  8. {
  9.     if (tl == tr)
  10.     {
  11.         t[v][0] = t[v][1] = a[tl];
  12.         return;
  13.     }
  14.     int mid = (tl + tr)/2;
  15.     build(v*2, tl, mid);
  16.     build(v*2+1, mid+1, tr);
  17.     t[v][0] = min(t[v*2][0], t[v*2+1][0]);
  18.     t[v][1] = max(t[v*2][1], t[v*2+1][1]);
  19. }
  20.  
  21. pair <long long, long long> ask(int v, int tl, int tr, int l, int r)
  22. {
  23.     if (l > r) return {1e9, -1e9};
  24.     if (l == tl && r == tr)
  25.     {
  26.         return {t[v][0], t[v][1]};
  27.     }
  28.     int mid = (tl + tr)/2;
  29.     auto duck1 = ask(v*2, tl, mid, l, min(mid, r));
  30.     auto duck2 = ask(v*2+1, mid+1, tr, max(l, mid+1), r);
  31.     return {min(duck1.first, duck2.first), max(duck1.second, duck2.second)};
  32. }
  33.  
  34. void act(int v, int tl, int tr, int x, int val)
  35. {
  36.     if (tl == tr)
  37.     {
  38.         t[v][0] = t[v][1] = val;
  39.         return;
  40.     }
  41.     int mid = (tl + tr)/2;
  42.     if (x <= mid) act(v*2, tl, mid, x, val);
  43.     else act(v*2+1, mid+1, tr, x, val);
  44.     t[v][0] = min(t[v*2][0], t[v*2+1][0]);
  45.     t[v][1] = max(t[v*2][1], t[v*2+1][1]);
  46. }
  47.  
  48. int main()
  49. {
  50.     int n=1e5, m;
  51.  
  52.     for (long long i=1; i <= n; i++)
  53.     {
  54.         a[i] = (i*i)%12345ll + (i*i*i)%23456ll;
  55.     }
  56.     build(1, 1, n);
  57.     cin >> m;
  58.     while (m--)
  59.     {
  60.         int l, r;
  61.         cin >> l >> r;
  62.         if (l > 0)
  63.         {
  64.             auto x = ask(1, 1, n, l , r);
  65.             cout << x.second - x.first << endl;
  66.         }
  67.         else
  68.         {
  69.             act(1, 1, n, -l, r);
  70.         }
  71.     }
  72.  
  73. }
RAW Paste Data
We use cookies for various purposes including analytics. By continuing to use Pastebin, you agree to our use of cookies as described in the Cookies Policy. OK, I Understand
 
Top