Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include <bits/stdc++.h>
- using namespace std;
- long long a[100001], t[400004][2];
- void build(int v, int tl, int tr)
- {
- if (tl == tr)
- {
- t[v][0] = t[v][1] = a[tl];
- return;
- }
- int mid = (tl + tr)/2;
- build(v*2, tl, mid);
- build(v*2+1, mid+1, tr);
- t[v][0] = min(t[v*2][0], t[v*2+1][0]);
- t[v][1] = max(t[v*2][1], t[v*2+1][1]);
- }
- pair <long long, long long> ask(int v, int tl, int tr, int l, int r)
- {
- if (l > r) return {1e9, -1e9};
- if (l == tl && r == tr)
- {
- return {t[v][0], t[v][1]};
- }
- int mid = (tl + tr)/2;
- auto duck1 = ask(v*2, tl, mid, l, min(mid, r));
- auto duck2 = ask(v*2+1, mid+1, tr, max(l, mid+1), r);
- return {min(duck1.first, duck2.first), max(duck1.second, duck2.second)};
- }
- void act(int v, int tl, int tr, int x, int val)
- {
- if (tl == tr)
- {
- t[v][0] = t[v][1] = val;
- return;
- }
- int mid = (tl + tr)/2;
- if (x <= mid) act(v*2, tl, mid, x, val);
- else act(v*2+1, mid+1, tr, x, val);
- t[v][0] = min(t[v*2][0], t[v*2+1][0]);
- t[v][1] = max(t[v*2][1], t[v*2+1][1]);
- }
- int main()
- {
- int n=1e5, m;
- for (long long i=1; i <= n; i++)
- {
- a[i] = (i*i)%12345ll + (i*i*i)%23456ll;
- }
- build(1, 1, n);
- cin >> m;
- while (m--)
- {
- int l, r;
- cin >> l >> r;
- if (l > 0)
- {
- auto x = ask(1, 1, n, l , r);
- cout << x.second - x.first << endl;
- }
- else
- {
- act(1, 1, n, -l, r);
- }
- }
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement