fork download
copy 
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3. typedef long long ll;
  4.  
  5. #define           s     second
  6. #define           f     first
  7. #define           pb    push_back
  8. #define           ep    emplace
  9. #define           eb    emplace_back
  10. #define           lb    lower_bound
  11. #define           ub    upper_bound
  12. #define       all(x)    x.begin(), x.end()
  13. #define      rall(x)    x.rbegin(), x.rend()
  14. #define   uniquev(v)    sort(all(v)), (v).resize(unique(all(v)) - (v).begin())
  15. #define     mem(f,x)    memset(f , x , sizeof(f))
  16. #define        sz(x)    (int)(x).size()
  17. #define  __lcm(a, b)    (1ll * ((a) / __gcd((a), (b))) * (b))
  18. #define          mxx    *max_element
  19. #define          mnn    *min_element
  20. #define    cntbit(x)    __builtin_popcountll(x)
  21. #define       len(x)    (int)(x.length())
  22.  
  23. const int N = 2e5 + 2;
  24. const int block = 600;
  25.  
  26. vector <pair <int, int>> ask[(int)N / block + 100];
  27. int l[N], r[N], nxt[N], pr[N], a[N], p[N];
  28. ll ans[N];
  29.  
  30. int main() {
  31.     ios_base::sync_with_stdio(0);
  32.     cin.tie(0);
  33.     cout.tie(0);
  34.  
  35.     int n, q;
  36.     cin >> n >> q;
  37.  
  38.     for (int i = 1; i <= q; i++)
  39.         ans[i] = 0;
  40.  
  41.     array <int, 2> _, b[n];
  42.  
  43.     for (int i = 1; i <= n; i++) {
  44.         cin >> a[i];
  45.         b[i - 1] = {a[i], i};
  46.     }
  47.  
  48.     sort(b, b + n);
  49.     for (int i = 0; i < n; i++)
  50.         p[b[i][1]] = i; 
  51.  
  52.     for (int i = 1; i <= q; i++) {
  53.         int qL, qR; cin >> qL >> qR;
  54.         qL = lower_bound(b, b + n, _ = {qL}) - b;
  55.         qR = lower_bound(b, b + n, _ = {qR + 1}) - b - 1;
  56.  
  57.         if(qL <= qR && qL < n && 0 <= qR)
  58.             ask[qL / block].push_back({qR, i});
  59.  
  60.         l[i] = qL;
  61.         r[i] = qR;
  62.     }
  63.  
  64.     for (int id = 0; id * block <= n; id++) {
  65.         if (ask[id].empty())
  66.             continue;
  67.  
  68.         sort(all(ask[id]));
  69.         int st = id * block, cur = ask[id].back().f;
  70.  
  71.         fill(pr, pr + n + 1, 0);
  72.         fill(nxt, nxt + n + 1, 0);
  73.  
  74.         ll sum = 0;
  75.         int lst = 0;
  76.         for (int i = 1; i <= n; i++) {
  77.             if (p[i] >= st && p[i] <= cur) {
  78.                 if (lst) {
  79.                     nxt[lst] = i;  
  80.                     sum += abs(a[i] - a[lst]); 
  81.                 }
  82.                 pr[i] = lst;
  83.                 lst = i;
  84.             }
  85.         }
  86.  
  87.         ll save = 0;
  88.         stack <pair <int, int>> s1, s2;
  89.         for (int i = cur; sz(ask[id]); i--) {
  90.             save = sum;
  91.             while (sz(ask[id]) && ask[id].back().f == i) {
  92.                 pair <int, int> top = ask[id].back();
  93.                 ask[id].pop_back();
  94.                 for (int j = st; j < l[top.s]; j++) {
  95.                     int pos = b[j][1];
  96.                     if (nxt[pos]) {
  97.                         sum -= abs(a[pos] - a[nxt[pos]]);
  98.                     }
  99.  
  100.                     if (pr[pos]) {
  101.                         sum -= abs(a[pos] - a[pr[pos]]);
  102.                     }
  103.  
  104.                     if (nxt[pos] && pr[pos]) {
  105.                         sum += abs(a[nxt[pos]] - a[pr[pos]]);
  106.                     }
  107.  
  108.                     if (pr[pos]) {
  109.                         s1.push({pr[pos], pos});
  110.                         nxt[pr[pos]] = nxt[pos];
  111.                     }
  112.  
  113.                     if (nxt[pos]) {
  114.                         s2.push({nxt[pos], pos});
  115.                         pr[nxt[pos]] = pr[pos];
  116.                     }
  117.                 }
  118.  
  119.                 ans[top.s] = sum;
  120.                 sum = save;
  121.  
  122.                 while (sz(s1)) {
  123.                     pair <int, int> t = s1.top();
  124.                     s1.pop();
  125.                     nxt[t.f] = t.s;
  126.                 }
  127.  
  128.                 while (sz(s2)) {
  129.                     pair <int, int> t = s2.top();
  130.                     s2.pop();
  131.                     pr[t.f] = t.s;
  132.                 }
  133.             }
  134.  
  135.             int pos = b[i][1];
  136.             if (nxt[pos]) {
  137.                 sum -= abs(a[pos] - a[nxt[pos]]);
  138.             }
  139.  
  140.             if (pr[pos]) {
  141.                 sum -= abs(a[pos] - a[pr[pos]]);
  142.             }
  143.  
  144.             if (nxt[pos] && pr[pos]) {
  145.                 sum += abs(a[nxt[pos]] - a[pr[pos]]);
  146.             }
  147.  
  148.             if (pr[pos]) {
  149.                 nxt[pr[pos]] = nxt[pos];
  150.             }
  151.  
  152.             if (nxt[pos]) {
  153.                 pr[nxt[pos]] = pr[pos];
  154.             }
  155.         }
  156.     }
  157.  
  158.     for (int i = 1; i <= q; i++) {
  159.         assert(ans[i] >= 0);
  160.         cout << ans[i] << '\n';
  161.     }
  162.  
  163.     return 0;
  164. }
  165.  
Success #stdin #stdout 0.01s 7712KB
comments (?)
stdin
copy 
5 5
3 1 5 2 4
2 5
1 4
1 3
3 5
4 5
stdout
copy 
7
5
3
3
1
https://ideone.com/7zGojm
language:
C++14 (gcc 8.3)
created:
2 days ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!