fork download
  1. #include<iostream>
  2. #include<cmath>
  3. #include<climits>
  4. #include<cstring>
  5. using namespace std;
  6. int a[500001],segTree[500001];
  7. void constructSegTree(int l, int r, int pos)
  8. {
  9.  
  10. if(l == r) {
  11. segTree[pos] = a[l];
  12. return;
  13. }
  14. int mid = (l+r)>>1;
  15. int child = (pos<<1)+1;
  16. constructSegTree(l,mid,child);
  17. constructSegTree(mid+1,r,child+1);
  18. segTree[pos] = min(segTree[child],segTree[child+1]);
  19. }
  20. int rmq(int l, int r, int pos, int qL, int qH)
  21. {
  22. int mid = (l+r)>>1;
  23. int child = (pos<<1)+1;
  24. if(l>r) return INT_MAX;
  25. else if(l>=qL && r<=qH)
  26. return segTree[pos];
  27. else if(qL > r || qH < l)
  28. return INT_MAX;
  29. else return min(rmq(l,mid,child,qL,qH),rmq(mid+1,r,child+1,qL,qH));
  30. // else return min(rmq(l,(l+r)/2,((pos*2)+1),qL,qH),rmq(((l+r)/2)+1,r,(pos*2)+2,qL,qH));
  31. }
  32. int main()
  33. {
  34. int t;
  35. scanf("%d",&t);
  36. int i = 0;
  37. memset(segTree,INT_MAX,sizeof(segTree));
  38. while(t--)
  39. {
  40. i++;
  41. int n, q;
  42. scanf("%d%d",&n,&q);
  43. for(int i=0;i<n;i++)
  44. scanf("%d",&a[i]);
  45. constructSegTree(0,n-1,0);
  46. printf("Scenario #%d:\n",i);
  47. while(q--)
  48. {
  49. int l,r;
  50. cin >> l >> r;
  51. l--;
  52. r--;
  53. printf("%d\n",rmq(0,n-1,0,l,r) );
  54. }
  55. }
  56. return 0;
  57. }
Success #stdin #stdout 0s 5776KB
stdin
2
5 3
1 2 3 4 5
1 5
1 3
2 4
5 3
1 -2 -4 3 -5
1 5
1 3
2 4
stdout
Scenario #1:
1
1
2
Scenario #2:
-5
-4
-4