fork(1) 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. int main()
  104. {
  105. ll n;
  106. cin>>n;
  107. ll i=1;
  108. while(i<=n)
  109. {
  110. cin>>a[i];
  111. b[i]=i;
  112. i++;
  113. }
  114.  
  115. build(1,1,n);
  116.  
  117.  
  118.  
  119. cout<<sum1(1,1,n,2,8);
  120.  
  121.  
  122.  
  123.  
  124.  
  125.  
  126.  
  127.  
  128. return 0;
  129. }
  130.  
  131.  
  132.  
  133.  
  134.  
  135.  
  136.  
  137.  
  138.  
  139.  
  140.  
  141.  
  142.  
  143.  
  144.  
  145.  
  146.  
  147.  
  148.  
  149.  
  150.  
  151.  
  152.  
  153.  
  154.  
  155.  
  156.  
Success #stdin #stdout 0s 19920KB
stdin
9
1 1 2 2 3 2 1 2 1
stdout
1
2
3
4
5
6
7
8
9
2