fork(2) download
  1. #include <iostream>
  2. #include <utility>
  3. #include <algorithm>
  4. #define SIZE 100000
  5. using namespace std;
  6.  
  7. void build(pair<int, int>* tree, int pos, int l, int r)
  8. {
  9. if (l == r)
  10. {
  11. tree[pos].first = (l % 12345) * (l % 12345) % 12345 + ((l % 23456) * (l % 23456) % 23456) * (l % 23456) % 23456;
  12. tree[pos].second = tree[pos].first;
  13. }
  14. else
  15. {
  16. int m = (l + r) / 2;
  17. build(tree, pos * 2, l, m);
  18. build(tree, pos * 2 + 1, m + 1, r);
  19. tree[pos] = make_pair(max(tree[pos * 2].first, tree[pos * 2 + 1].first), min(tree[pos * 2].second, tree[pos * 2 + 1].second));
  20. }
  21. }
  22.  
  23. pair<int, int> get(pair<int, int>* tree, int pos, int l, int r, int ql, int qr)
  24. {
  25. if (l == ql && r == qr)
  26. return tree[pos];
  27. else
  28. {
  29. int m = (l + r) / 2;
  30. if (qr <= m)
  31. return get(tree, pos * 2, l, m, ql, qr);
  32. else if (ql >= m + 1)
  33. return get(tree, pos * 2 + 1, m + 1, r, ql, qr);
  34. else
  35. {
  36. pair<int, int> a = get(tree, pos * 2, l, m, ql, m);
  37. pair<int, int> b = get(tree, pos * 2 + 1, m + 1, r, m + 1, qr);
  38. return make_pair(max(a.first, b.first), min(a.second, b.second));
  39. }
  40. }
  41. }
  42.  
  43. void modify(pair<int, int>* tree, int pos, int l, int r, int npos, int nv)
  44. {
  45. if (l == r)
  46. {
  47. tree[pos].first = nv;
  48. tree[pos].second = nv;
  49. }
  50. else
  51. {
  52. int m = (l + r) / 2;
  53. if (npos <= m)
  54. modify(tree, pos * 2, l, m, npos, nv);
  55. else
  56. modify(tree, pos * 2 + 1, m + 1, r, npos, nv);
  57. tree[pos] = make_pair(max(tree[pos * 2].first, tree[pos * 2 + 1].first), min(tree[pos * 2].second, tree[pos * 2 + 1].second));
  58. }
  59. }
  60.  
  61. int main()
  62. {
  63. ios::sync_with_stdio(false);
  64. pair<int, int> tree[SIZE * 4];
  65. build(tree, 1, 1, SIZE);
  66. int n, x, y;
  67. cin >> n;
  68. for (int i = 0; i < n; i++)
  69. {
  70. cin >> x >> y;
  71. if (x > 0)
  72. {
  73. pair<int, int> query = get(tree, 1, 1, SIZE, x, y);
  74. cout << query.first - query.second << endl;
  75. }
  76. else
  77. modify(tree, 1, 1, SIZE, -x, y);
  78. }
  79. return 0;
  80. }
Success #stdin #stdout 0.01s 6460KB
stdin
13
1 17
-5 -400
-3 500
3 5
1 17
-2 345
2 345
2 3
2 5
-1 -100000
-2 100000
1 2
1 100000
stdout
5200
900
5602
35813
155
900
200000
200000