Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include <vector>
- #include <utility>
- #include <algorithm>
- #include <set>
- #include <iostream>
- #include <string>
- #include <map>
- #include <queue>
- #include <unordered_map>
- #include <math.h>
- #include <stdio.h>
- using namespace std;
- typedef long long ll;
- typedef vector<int> vi;
- typedef vector<ll> vl;
- typedef vector<vi> vvi;
- typedef pair<int, int> pii;
- typedef pair<double, double> pdd;
- const int inf = (int)1e9;
- const int mod = (int)1e9 + 7;
- #define eps 1e-9
- #define mp make_pair
- #define PI 3.14159265359
- #define all(x) (x).begin(), (x).end()
- #define name ""
- vector<pii> t;
- vi a;
- void build(int v, int tl, int tr)
- {
- if (tl == tr) {
- t[v].first = t[v].second = a[tl];
- return;
- }
- int tm = (tl + tr) / 2;
- build(2 * v, tl, tm);
- build(2 * v + 1, tm + 1, tr);
- t[v].first = max({ t[2 * v + 1].first, t[2 * v].first, t[2 * v + 1].second, t[2 * v].second });
- t[v].second = min({ t[2 * v + 1].first, t[2 * v].first, t[2 * v + 1].second, t[2 * v].second });
- }
- pii query(int v, int tl, int tr, int l, int r)
- {
- if (l > r)
- return mp(-inf, inf);
- if (l == tl && r == tr)
- return t[v];
- int tm = (tl + tr) / 2;
- pii p1 = query(2 * v, tl, tm, l, min(r, tm));
- pii p2 = query(2 * v + 1, tm + 1, tr, max(l, tm + 1), r);
- return mp(max(p1.first, p2.first), min(p1.second, p2.second));
- }
- void upd(int v, int tl, int tr, int i, int x)
- {
- if (tl == tr)
- t[v].first = t[v].second = x;
- else {
- int tm = (tl + tr) / 2;
- if (i <= tm)
- upd(2 * v, tl, tm, i, x);
- else
- upd(2 * v + 1, tm + 1, tr, i, x);
- t[v].first = max({ t[2 * v + 1].first, t[2 * v].first, t[2 * v + 1].second, t[2 * v].second });
- t[v].second = min({ t[2 * v + 1].first, t[2 * v].first, t[2 * v + 1].second, t[2 * v].second });
- }
- }
- int main()
- {
- #ifdef _DEBUG
- freopen("input.txt", "rt", stdin);
- freopen("output.txt", "wt", stdout);
- #else
- freopen(name".in", "rt", stdin);
- freopen(name".out", "wt", stdout);
- #endif
- a.resize(100000);
- for (ll i = 1; i <= 100000; i++) {
- a[i - 1] = (int)((i * i) % 12345) + (int)((i * i * i) % 23456);
- }
- t.assign(a.size() * 4, pii(-inf, inf));
- build(1, 0, a.size() - 1);
- int k;
- scanf("%d", &k);
- for (int i = 0; i < k; i++) {
- int x, y;
- scanf("%d %d", &x, &y);
- if (x > 0) {
- x--;
- y--;
- pii p = query(1, 0, a.size() - 1, x, y);
- printf("%d\n", p.first - p.second);
- }
- else {
- x *= -1;
- x--;
- upd(1, 0, a.size() - 1, x, y);
- }
- }
- return 0;
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement