fork download
  1. #include <fstream>
  2. #include <iostream>
  3. #include <vector>
  4. #include <cmath>
  5. using namespace std;
  6.  
  7. ifstream F("arbint.in");
  8. ofstream G("arbint.out");
  9.  
  10. const int N = 100010;
  11.  
  12. int n,m;
  13.  
  14. struct node {
  15. vector<int> a;
  16. int mx;
  17.  
  18. node(int x)
  19. {
  20. a.push_back(x);
  21. mx = x;
  22. }
  23. void push(int x)
  24. {
  25. a.push_back(x);
  26. mx = max(x,mx);
  27. }
  28. void update(int p,int x)
  29. {
  30. a[p] = x;
  31. mx = 0;
  32. for (int i=0;i<int(a.size());++i)
  33. mx = max(mx,a[i]);
  34. }
  35. int query(int p1,int p2)
  36. {
  37. if ( p1 == p2 || p1 >= int(a.size()) || p2 <= 0 )
  38. return 0;
  39. if ( p1 == 0 && p2 == int(a.size()) )
  40. return mx;
  41.  
  42. int _mx = 0;
  43. for (int i=p1;i<p2;++i)
  44. _mx = max(_mx,a[i]);
  45. return _mx;
  46. }
  47. void print()
  48. {
  49. for (int i=0;i<int(a.size());++i)
  50. cerr<<a[i]<<' ';
  51. }
  52. };
  53.  
  54. struct ksegment {
  55. int k;
  56. vector<node> v;
  57.  
  58. ksegment()
  59. {
  60. }
  61. ksegment(int _k)
  62. {
  63. k = _k;
  64. }
  65. void push(int x)
  66. {
  67. if ( v.empty() )
  68. v.push_back( node(x) );
  69. else
  70. if ( int(v.back().a.size()) == k )
  71. v.push_back( node(x) );
  72. else
  73. v.back().push(x);
  74. }
  75. void update(int p,int x)
  76. {
  77. int wh = (p-1)/k;
  78. p -= wh*k+1;
  79. v[wh].update(p,x);
  80. }
  81. int query(int l,int r)
  82. {
  83. int mx = 0;
  84. for (int i=0;i<int(v.size());++i)
  85. {
  86. int ll = max(l-i*k-1,0);
  87. int rr = min(k,r-i*k);
  88. mx = max(mx,v[i].query( ll,rr ));
  89. }
  90. return mx;
  91. }
  92. void print()
  93. {
  94. for (int i=0;i<int(v.size());++i)
  95. {
  96. cerr<<"[";
  97. v[i].print();
  98. cerr<<"] ";
  99. }
  100. cerr<<'\n';
  101. }
  102. };
  103.  
  104. int main()
  105. {
  106. F>>n>>m;
  107. ksegment ks = ksegment(sqrt(n));
  108. for (int i=1,x;i<=n;++i)
  109. {
  110. F>>x;
  111. ks.push(x);
  112. }
  113. for (int i=1,t,x,y;i<=m;++i)
  114. {
  115. //ks.print();
  116. F>>t;
  117. ++t;
  118.  
  119. if ( t == 1 )
  120. {
  121. F>>x>>y;
  122. G<<ks.query(x,y)<<'\n';
  123. }
  124. else
  125. {
  126. F>>x>>y;
  127. ks.update(x,y);
  128. }
  129. }
  130. }
  131.  
Success #stdin #stdout 0s 3460KB
stdin
Standard input is empty
stdout
Standard output is empty