fork download
  1. #include<bits/stdc++.h>
  2. using namespace std;
  3. typedef long long int ll;
  4. ll l,r;
  5. ll segtree[400001];
  6. ll a[100001];
  7. ll b[100001];
  8. void build(ll node,ll b1,ll e)
  9.  
  10. {if(b1==e)
  11. {
  12. segtree[node]=b[b1];
  13. cout<<b[b1]<<"\n";
  14. }
  15. else
  16. {
  17. ll mid=(b1+e)/2;
  18.  
  19. build(2*node,b1,mid);
  20. build(2*node+1,mid+1,e);
  21.  
  22.  
  23. l=segtree[2*node];
  24. r=segtree[2*node+1];
  25.  
  26. if(a[l]<a[r])
  27. {
  28. segtree[node]=l;
  29.  
  30. }
  31. else if(a[l]>a[r])
  32. {
  33.  
  34. segtree[node]=r;
  35.  
  36. }
  37. else if(a[l]==a[r])
  38. {
  39.  
  40. segtree[node]=l;
  41. }
  42. else
  43. {
  44.  
  45. }
  46.  
  47. }
  48.  
  49.  
  50.  
  51. }
  52. ll sum1(ll node,ll b1,ll e,ll L,ll R)
  53. {
  54.  
  55. if(b1>R || e<L)
  56. {
  57. return -1;
  58. }
  59.  
  60. if (b1>=L && e<=R)
  61. {
  62. return segtree[node];
  63.  
  64. }
  65.  
  66.  
  67. ll mid=(b1+e)/2;
  68.  
  69. ll left=sum1(2*node,b1,mid,L,R);
  70. ll right=sum1(2*node+1,mid+1,e,L,R);
  71. if(left==-1)
  72. {
  73. return right;
  74. }
  75. else if(right==-1)
  76. {
  77. return left;
  78. }
  79. else
  80. {
  81.  
  82. if(a[left]>a[right])
  83. {
  84. return right;
  85. }
  86. else
  87. {
  88. return left;
  89. }
  90.  
  91.  
  92. }
  93.  
  94.  
  95.  
  96.  
  97.  
  98.  
  99.  
  100.  
  101. }
  102.  
  103. void update(ll node,ll b1,ll e,ll ind,ll value)
  104. {
  105.  
  106.  
  107.  
  108. if(b1==e)
  109. {
  110.  
  111. segtree[node]=ind;
  112. a[ind]=value;
  113.  
  114.  
  115.  
  116.  
  117. }
  118. else
  119. {
  120. ll mid=(b1+e)/2;
  121.  
  122. if(ind<=mid)
  123. {
  124. update(2*node,b1,mid,ind,value);
  125. }
  126. else
  127. {
  128.  
  129.  
  130. update(2*node+1,mid+1,e,ind,value);
  131.  
  132.  
  133.  
  134. }
  135.  
  136.  
  137. ll l=segtree[2*node];
  138. ll r=segtree[2*node+1];
  139.  
  140.  
  141. if(a[l]>a[r])
  142. {
  143.  
  144. segtree[node]=r;
  145.  
  146. }
  147. else
  148. {
  149.  
  150.  
  151. segtree[node]=l;
  152.  
  153.  
  154. }
  155.  
  156.  
  157.  
  158.  
  159.  
  160.  
  161.  
  162.  
  163.  
  164.  
  165.  
  166. }
  167.  
  168.  
  169.  
  170.  
  171.  
  172.  
  173.  
  174.  
  175.  
  176.  
  177.  
  178.  
  179.  
  180.  
  181.  
  182.  
  183.  
  184. }
  185.  
  186.  
  187.  
  188.  
  189. int main()
  190. {
  191. ll n;
  192. cin>>n;
  193. ll i=1;
  194. while(i<=n)
  195. {
  196. cin>>a[i];
  197. b[i]=i;
  198. i++;
  199. }
  200.  
  201. build(1,1,n);
  202.  
  203.  
  204.  
  205. cout<<sum1(1,1,n,3,5);
  206. cout<<"\n";
  207.  
  208. update( 1,1,n,3,100 );
  209.  
  210. cout<<sum1(1,1,n,3,5);
  211. cout<<"\n";
  212.  
  213.  
  214.  
  215.  
  216. return 0;
  217. }
  218.  
Success #stdin #stdout 0s 19928KB
stdin
5
1 2 3 4 5
stdout
1
2
3
4
5
3
4