fork download
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3. const int N = 50001;
  4. int inter[2][N], arr[N];
  5. int n, q, l, r;
  6. int ls(int indx) {
  7. return indx & (-indx);
  8. }
  9. void update(int indx, int val) {
  10. int mx = val, mn = val;
  11. for (; indx <= n; indx += ls(indx)) {
  12. inter[1][indx] = mx = max(mx, inter[1][indx]);
  13. inter[0][indx] = mn = min(mn, inter[0][indx]);
  14. }
  15. }
  16. int get(int l, int r) {
  17. int mx = 0, mn = 1e9;
  18. while (r >= l) {
  19. while (r - ls(r) < l && r >= l) {
  20. mx = max(mx, arr[r]);
  21. mn = min(mn, arr[r]);
  22. --r;
  23. }
  24. if (r >= l)
  25. mx = max(mx, inter[1][r]), mn = min(mn, inter[0][r]);
  26. r -= ls(r);
  27. }
  28. return mx - mn;
  29. }
  30. int main() {
  31. #ifndef ONLINE_JUDGE
  32. freopen("a.in", "r", stdin);
  33. #endif
  34. scanf("%d %d", &n, &q);
  35. memset(inter[0], 127, sizeof(int) * (n + 1));
  36. for (int i = 1; i <= n; ++i)
  37. scanf("%d", &arr[i]), update(i, arr[i]);
  38. while (q--) {
  39. scanf("%d %d", &l, &r);
  40. if (l == r) {
  41. puts("0");
  42. continue;
  43. }
  44. printf("%d\n", get(l, r));
  45. }
  46. return 0;
  47. }
  48.  
Success #stdin #stdout 0s 3724KB
stdin
Standard input is empty
stdout
Standard output is empty