SHARE
TWEET

Untitled

a guest Jul 18th, 2019 52 Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. #define INF 1e9
  2. const int N=100000;
  3.  
  4. int t1[4*N], t2[4*N];
  5.  
  6. void build(int v, int l, int r) {
  7.     if (l == r) {
  8.         t1[v] = (long long)(l*l)%12345 + (long long)(l*l*l)%23456;
  9.         t2[v] = t1[v];
  10.     } else {
  11.         int m=(l+r)/2;
  12.         build(2*v, l, m);
  13.         build(2*v+1, m+1, r);
  14.         t1[v] = min(t1[2*v], t1[2*v+1]);
  15.         t2[v] = max(t2[2*v], t2[2*v+1]);
  16.     }
  17. }
  18.  
  19. int get_min(int v, int l, int r, int lt, int rt) {
  20.     if (l > r)
  21.         return INF;
  22.     if (l==lt && r==rt)
  23.         return t1[v];
  24.     int m=(l+r)/2;
  25.     get_min(2*v, l, m, lt, rt);
  26.     get_min(2*v+1, m+1, r, lt, rt);
  27. }
  28.  
  29. int get_max(int v, int l, int r, int lt, int rt) {
  30.     if (l > r)
  31.         return -INF;
  32.     if (l==lt && r==rt)
  33.         return t2[v];
  34.     int m=(l+r)/2;
  35.     get_max(2*v, l, m, lt, rt);
  36.     get_max(2*v+1, m+1, r, lt, rt);
  37. }
  38.  
  39. void update(int v, int l, int r, int pos, int x) {
  40.     if (l == r) {
  41.         t1[v] = x;
  42.         t2[v] = x;
  43.     } else {
  44.         int m=(l+r)/2;
  45.         if (pos <= m)
  46.             update(2*v, l, m, pos, x);
  47.         else
  48.             update(2*v+1, m+1, r, pos, x);
  49.         t1[v] = min(t1[2*v], t1[2*v+1]);
  50.         t2[v] = max(t2[2*v], t2[2*v+1]);
  51.     }
  52. }
  53.  
  54. int main() {
  55.     ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
  56.     build(1, 1, N);
  57.     int K=0; cin >> K;
  58.     for (int i=0; i<K; i++) {
  59.         int x=0, y=0; cin >> x >> y;
  60.         if (x > 0) {
  61.             cout << get_max(1, 1, N, x, y) - get_min(1, 1, N, x, y  ) << '\n';
  62.         } else {
  63.             update(1, 1, N, -x, y);
  64.         }
  65.     }
  66. }
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