fork download
copy 
  1. #include <bits/stdc++.h>
  2. #define ll long long
  3. #define ft first
  4. #define sc second
  5. #define el '\n'
  6. #define FOR(i,a,b) for (int i = (a), _b = (b); i <= _b; i ++)
  7. #define FORD(i,b,a) for (int i = (b), _a = (a); i >= _a; i --)
  8. #define boost ios::sync_with_stdio(0); cin.tie(0); cout.tie(0)
  9. #define file(name) freopen(name".inp", "r", stdin); freopen(name".out", "w", stdout)
  10. #define pb push_back
  11. #define all(x) (x).begin(),(x).end()
  12. using namespace std;
  13. const ll N = 2e5;
  14. ll n, q, block = 0, sum = 0, a[N + 1], Ans[N + 1]; 
  15. ll linkLeft[N + 1], linkRight[N + 1], linkCheck[N + 1];
  16.  
  17. vector<pair<ll, ll>> b;
  18.  
  19. struct QUERY {
  20.     ll x, y, z;
  21. };
  22.  
  23. vector<QUERY> query;
  24. struct HIS {
  25.     ll x, y, z, t;
  26. };
  27.  
  28. vector<HIS> history;
  29.  
  30. ll binaryL(ll tg) {
  31.     ll l = 1, r = b.size() - 1, ans = -1;
  32.  
  33.     while(l <= r) {
  34.         ll mid = (l + r) >> 1;
  35.  
  36.         if(b[mid].ft >= tg) {
  37.             r = mid - 1;
  38.             ans = mid;
  39.         } else {
  40.             l = mid + 1;
  41.         }
  42.     }
  43.  
  44.     return ans;
  45. }
  46.  
  47. ll binaryR(ll tg) {
  48.     ll l = 1, r = b.size() - 1, ans = -1;
  49.  
  50.     while(l <= r) {
  51.         ll mid = (l + r) >> 1;
  52.  
  53.         if(b[mid].ft <= tg) {
  54.             l = mid + 1;
  55.             ans = mid;
  56.         } else {
  57.             r = mid - 1;
  58.         }
  59.     }
  60.  
  61.     return ans;
  62. }
  63.  
  64. void read() {
  65.     cin >> n >> q;
  66.     b.pb({0, 0});
  67.  
  68.     FOR(i, 1, n) {
  69.         cin >> a[i];
  70.         b.pb({a[i], i});
  71.     }
  72.  
  73.     sort(b.begin() + 1, b.end());
  74.  
  75.     FOR(i, 1, q) {
  76.         ll x, y; cin >> x >> y;
  77.  
  78.         x = binaryL(x);
  79.         y = binaryR(y);
  80.  
  81.         if(x == -1 || y == -1) Ans[i] = 0;
  82.         else {
  83.             query.pb({x, y, i});
  84.         }
  85.     }
  86.  
  87.     block = sqrt(n);
  88.  
  89.     sort(all(query), [](const QUERY &x, const QUERY &y) {
  90.         ll rx = x.x / block, ry = y.x / block;
  91.  
  92.         if(rx != ry) return rx < ry;
  93.         return x.y > y.y;
  94.     });
  95. }
  96.  
  97. void remove(ll k, bool roll) {
  98.     k = b[k].sc;
  99.  
  100.     ll left = linkLeft[k];
  101.     ll right = linkRight[k];
  102.  
  103.     if(roll) {
  104.         history.pb({left, right, k, sum});
  105.     }
  106.  
  107.     if(left != -1 && right != -1) {
  108.         sum += abs(a[left] - a[right]);
  109.         sum -= abs(a[left] - a[k]);
  110.         sum -= abs(a[right] - a[k]);
  111.         linkRight[left] = right;
  112.         linkLeft[right] = left;
  113.     } else if(left != -1) {
  114.         sum -= abs(a[left] - a[k]);
  115.         linkRight[left] = right;
  116.     } else if(right != -1) {
  117.         sum -= abs(a[right] - a[k]);
  118.         linkLeft[right] = left;
  119.     }
  120. }
  121.  
  122. void rollback() {
  123.     while(!history.empty()) {
  124.         auto [x, y, z, t] = history.back();
  125.         history.pop_back();
  126.  
  127.         linkLeft[z] = x;
  128.         linkRight[z] = y;
  129.         if(x != -1) linkRight[x] = z;
  130.         if(y != -1) linkLeft[y] = z;
  131.         sum = t;
  132.     }
  133. }
  134.  
  135. void solve() {
  136.     ll l = 0;
  137.  
  138.     FOR(i, 0, n / block) {
  139.         ll r = l;
  140.         while(r < query.size() && (query[r].x / block) == i) {
  141.             r ++;
  142.         }
  143.  
  144.         r --;
  145.         ll curL = max(1LL, i * block), curR = query[l].y;
  146.  
  147.         FOR(j, 1, n) {
  148.             linkLeft[j] = 0;
  149.             linkRight[j] = 0;
  150.             linkCheck[j] = 0;
  151.         }
  152.  
  153.         FOR(j, curL, curR) {
  154.             linkCheck[b[j].sc] = 1;
  155.         }
  156.  
  157.         sum = 0;
  158.         ll cur = 0;
  159.         FOR(j, 1, n) {
  160.             if(linkCheck[j]) {
  161.                 if(cur == 0) {
  162.                     cur = j;
  163.                     linkLeft[j] = -1;
  164.                 }
  165.                 else {
  166.                     sum += abs(a[j] - a[cur]);
  167.                     linkLeft[j] = cur;
  168.                     linkRight[cur] = j;
  169.                     cur = j;
  170.                 }
  171.             }
  172.         }
  173.  
  174.         linkRight[cur] = -1;
  175.  
  176.         FOR(j, l, r) {
  177.             while(curR > query[j].y) remove(curR --, 0);
  178.  
  179.             FOR(k, curL, query[j].x - 1) {
  180.                 remove(k, 1);
  181.             }
  182.  
  183.             Ans[query[j].z] = sum;
  184.             rollback();
  185.         }
  186.  
  187.         l = r + 1;
  188.     }
  189. }
  190.  
  191. void write() {
  192.     FOR(i, 1, q) cout << Ans[i] << el;
  193. }
  194.  
  195. int main() {
  196.     boost;
  197.     //file();
  198.     read();
  199.     solve();
  200.     write();
  201.     return 0;
  202. }
Success #stdin #stdout 0.01s 9816KB
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/abkLay
language:
C++14 (gcc 8.3)
created:
3 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!