fork(4) download
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3.  
  4. const int N = 1<<20;
  5. const int LOG = 21;
  6.  
  7. int rmq[N][LOG];
  8. int arr[N],n;
  9.  
  10. void preprocess(int *a, int n) {
  11. int i,j;
  12. for(i=1;i<=n;i++) rmq[i][0]=a[i];
  13. for(j=1;(1<<j)<=n;j++) for(i=1;i+(1<<j)-1<=n;i++) rmq[i][j]=min(rmq[i][j-1],rmq[i+(1<<(j-1))][j-1]);
  14. }
  15.  
  16. int query(int a, int b) {
  17. int k=log2(b-a+1);
  18. return min(rmq[a][k],rmq[b-(1<<k)+1][k]);
  19. }
  20.  
  21. int main() {
  22. n=5;
  23. arr[1]=3;
  24. arr[2]=5;
  25. arr[3]=1;
  26. arr[4]=5;
  27. arr[5]=2;
  28. preprocess(arr,5);
  29. cout<<query(1,5)<<endl<<query(1,2)<<endl<<query(4,5)<<endl;
  30. return 0;
  31. }
Success #stdin #stdout 0s 93568KB
stdin
Standard input is empty
stdout
1
3
2