fork(1) download
copy 
  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
comments (?)
stdin
copy 
5
1 2 3 4 5
stdout
copy 
1
2
3
4
5
3
4
https://ideone.com/NngMkb
language:
C++14 (gcc 8.3)
created:
4 years ago
visibility:
secret

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!