• API
• FAQ
• Tools
• Archive
SHARE
TWEET

# Untitled

a guest Apr 18th, 2019 66 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.

Top