fork download
  1. //Solution by Tima
  2. #include <bits/stdc++.h>
  3.  
  4. #define f first
  5. #define s second
  6. #define ll long long
  7. #define ull unsigned long long
  8. #define mp make_pair
  9. #define pb push_back
  10. #define vi vector <int>
  11. #define ld long double
  12. #define pii pair<int, int>
  13. #define y1 sda
  14.  
  15. using namespace std;
  16. const int N = int(3e5) + 12, mod = int(1e9) + 7, K = 450;
  17.  
  18. ll ans[N], d[K + 5][K + 5];
  19. int n, m, a[N], b[N],c[N], cn, L[N], R[N];
  20. int lastq[N], Nx[N], Pv[N], first[K + 5][K + 5], last[K + 5][K + 5];
  21. int p[N], pn;
  22.  
  23. pair<int, int> A[N], B[N];
  24.  
  25. int nxt[N], prv[N];
  26.  
  27. vector <int> del[N];
  28.  
  29. void calc(int l,int r){
  30. pn = 0;
  31.  
  32. for(int i = l; i <= r; i++){
  33. p[++pn] = a[i];
  34. }
  35. sort(p + 1, p + pn + 1);
  36. pn = unique(p + 1, p + pn + 1) - p - 1;
  37. for(int i = l; i <= r; i++){
  38. b[i] = lower_bound(p + 1, p + pn + 1, a[i]) - p;
  39. del[b[i]].pb(i);
  40. }
  41. p[pn + 1] = cn + 1;
  42. memset(d, 0, sizeof(d));
  43. memset(last, 0, sizeof(last));
  44. memset(first, 0, sizeof(first));
  45. for(int x = 1, ls; x <= pn; x++){
  46. int y = pn;
  47. ls = 0;
  48. ll cur = 0;
  49. for(int i = l; i <= r; i++){
  50. if(p[x] <= a[i] && a[i] <= p[y]){
  51. nxt[ls] = i;
  52. prv[i] = ls;
  53. if(ls){
  54. cur += abs(a[i] - a[ls]);
  55. }
  56. ls = i;
  57. }
  58. }
  59. nxt[ls] = n + 1, prv[n + 1] = ls;
  60. d[x][y] = cur;
  61. if(ls != 0) {
  62. first[x][y] = a[nxt[0]];
  63. last[x][y] = a[ls];
  64. }
  65. while(y > x){
  66. for(int i : del[y]){
  67. int l = prv[i],r = nxt[i];
  68. if(l > 0) cur -= (a[i] - a[l]);
  69. if(r <= n) cur -= (a[i] - a[r]);
  70. if(l > 0 && r <= n) cur += abs(a[l] - a[r]);
  71. nxt[l] = r, prv[r] = l;
  72. }
  73. y--;
  74. d[x][y] = cur;
  75. first[x][y] = a[nxt[0]], last[x][y] = a[prv[n + 1]];
  76. }
  77. }
  78. int it = pn + 1;
  79. for (int i = m; i >= 1; --i) {
  80. while (it - 1 > 0 && p[it - 1] >= A[i].first) --it;
  81. Nx[A[i].second] = it;
  82. }
  83. it = 0;
  84. for (int i = 1; i <= m; ++i) {
  85. while (it + 1 <= pn && p[it + 1] <= B[i].first) ++it;
  86. Pv[B[i].second] = it;
  87. }
  88. for(int i = 1,x,y; i <= m; i++){
  89. x = Nx[i], y = Pv[i];
  90. ans[i] += d[x][y];
  91. if(last[x][y] != 0){
  92. if(lastq[i] != 0){
  93. ans[i] += abs(lastq[i] - first[x][y]);
  94. }
  95. lastq[i] = last[x][y];
  96. }
  97. }
  98. for(int i = 1; i <= pn; i++) del[i].clear();
  99. }
  100.  
  101. int main () {
  102. scanf("%d%d", &n, &m);
  103.  
  104. for(int i = 1; i <= n; i++){
  105. scanf("%d", &a[i]);
  106. }
  107.  
  108. for(int i = 1; i <= m; i++){
  109. scanf("%d%d", &L[i], &R[i]);
  110. A[i] = {L[i], i}, B[i] = {R[i], i};
  111. }
  112. sort(A + 1, A + m + 1);
  113. sort(B + 1, B + m + 1);
  114.  
  115. for(int i = 1; i <= n; i += K){
  116. calc(i, min(i + K - 1,n));
  117. }
  118.  
  119. for(int i = 1; i <= m; i++){
  120. printf("%lld\n", ans[i]);
  121. }
  122.  
  123. return 0;
  124. }
Success #stdin #stdout 0s 14072KB
stdin
10 10
2 4 7 10 6 8 6 2 6 4
3 4
2 6
3 6
3 4
8 8
1 9
6 10
3 5
4 4
3 8
stdout
0
14
4
0
0
20
11
0
0
10