fork download
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3.  
  4. int n,q;
  5. vector<int> a;
  6. vector< pair<int,int> > node;
  7. int resmax, resmin;
  8.  
  9. void Init_Tree(int k, int l, int r, int i)
  10. {
  11. if(l>i || r<i) return;
  12. if(l==r)
  13. {
  14. node[k]=make_pair(a[i],a[i]);
  15. return;
  16. }
  17. int m=(l+r)/2;
  18. Init_Tree(2*k,l,m,i);
  19. Init_Tree(2*k+1,m+1,r,i);
  20. node[k]=make_pair(max(node[2*k].first, node[2*k+1].first),min(node[2*k].second, node[2*k+1].second));
  21. }
  22.  
  23. void Init()
  24. {
  25. scanf("%d%d",&n,&q);
  26. a.resize(n+2);
  27. node.resize(4*n);
  28. for (int i=1;i<=n;i++)
  29. {
  30. scanf("%d",&a[i]);
  31. Init_Tree(1,1,n,i);
  32. }
  33. }
  34.  
  35. void Query(int k, int l, int r, int A, int B)
  36. {
  37. if(l>B || r<A) return;
  38. if(A<=l && B>=r)
  39. {
  40. resmax=max(resmax,node[k].first);
  41. resmin=min(resmin,node[k].second);
  42. return;
  43. }
  44. int m=(l+r)/2;
  45. Query(2*k,l,m,A,B);
  46. Query(2*k+1,m+1,r,A,B);
  47. }
  48.  
  49. void Solve()
  50. {
  51. for (int i=1;i<=q;i++)
  52. {
  53. int A, B;
  54. scanf("%d%d",&A,&B);
  55. resmax=0;
  56. resmin=10000000;
  57. Query(1,1,n,A,B);
  58. printf("%dn",resmax-resmin);
  59. }
  60. }
  61.  
  62. int main()
  63. {
  64. Init();
  65. Solve();
  66. }
Success #stdin #stdout 0s 2876KB
stdin
Standard input is empty
stdout
Standard output is empty