fork download
copy 
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3. //
  4. const int mx = 100000;
  5. const int S = 30;
  6. //
  7. int n, q, A[mx], B[mx];
  8. long long ans[mx];
  9. tuple<int, int, int, int> query[mx];
  10. vector<tuple<int, int, bool>> P[mx / S + 5];
  11. //
  12. namespace Fenwick_Tree
  13. {
  14.     pair<int, long long> bit[mx + 5];
  15.     //
  16.     void update (int idx, int val, bool inc)
  17.     {
  18.         for (; idx <= n; idx += idx & -idx)
  19.             bit[idx].first += inc ? 1 : -1,
  20.             bit[idx].second += inc ? val : -val;
  21.     }
  22.     pair<int, long long> get (int l, int r)
  23.     {
  24.         pair<int, long long> res(0, 0);
  25.         //
  26.         if (l > r)
  27.             return res;
  28.         --l;
  29.         for (int idx = l; idx > 0; idx -= idx & -idx)
  30.             res.first -= bit[idx].first,
  31.             res.second -= bit[idx].second;
  32.         for (int idx = r; idx > 0; idx -= idx & -idx)
  33.             res.first += bit[idx].first,
  34.             res.second += bit[idx].second;
  35.         return res;
  36.     }
  37. }
  38. //
  39. long long calc (int a, int b, int c, int d)
  40. {
  41.     long long res = 0;
  42.     pair<int, long long> p1, p2;
  43.     //
  44.     if (a == b || c == d)
  45.         return 0;
  46.     for (int i = a; i < b; ++i)
  47.         Fenwick_Tree::update(B[i], A[i], 1);
  48.     for (int i = c; i < d; ++i)
  49.     {
  50.         p1 = Fenwick_Tree::get(1, B[i] - 1);
  51.         p2 = Fenwick_Tree::get(B[i] + 1, n);
  52.         res += (1LL * p1.first * A[i] - p1.second) + (p2.second - 1LL * p2.first * A[i]);
  53.     }
  54.     for (int i = a; i < b; ++i)
  55.         Fenwick_Tree::update(B[i], A[i], 0);
  56.     return res;
  57. }
  58. void prepare (void)
  59. {
  60.     vector<int> V(A, A + n);
  61.     //
  62.     auto func = [&](int idx, bool inc, int x, int y) -> void
  63.     {
  64.         int u = x / S * S, v = y / S * S;
  65.         //
  66.         if (u == 0)
  67.             if (v == 0)
  68.                 ans[idx] += inc ? calc(0, x, 0, y) : -calc(0, x, 0, y);
  69.             else
  70.                 P[v / S].emplace_back(x, idx, inc),
  71.                 ans[idx] += inc ? calc(0, x, v, y) : -calc(0, x, v, y);
  72.         else
  73.             if (v == 0)
  74.                 P[u / S].emplace_back(y, idx, inc),
  75.                 ans[idx] += inc ? calc(u, x, 0, y) : -calc(u, x, 0, y);
  76.             else
  77.                 P[u / S].emplace_back(y, idx, inc),
  78.                 P[v / S].emplace_back(x, idx, inc),
  79.                 P[v / S].emplace_back(u, idx, inc ^ 1),
  80.                 ans[idx] += inc ? calc(u, x, v, y) : -calc(u, x, v, y);
  81.     };
  82.     //
  83.     sort(V.begin(), V.end());
  84.     V.erase(unique(V.begin(), V.end()), V.end());
  85.     for (int i = 0; i < n; ++i)
  86.         B[i] = upper_bound(V.begin(), V.end(), A[i]) - V.begin();
  87.  
  88.     for (int i = 0; i < n; ++i)
  89.     {
  90.         int a, b, c, d;
  91.         //
  92.         tie(a, b, c, d) = query[i];
  93.         func(i, 1, b, d);
  94.         if (a > 0)
  95.             func(i, 0, a, d);
  96.         if (c > 0)
  97.             func(i, 0, b, c);
  98.         if (a > 0 && c > 0)
  99.             func(i, 1, a, c);
  100.     }
  101. }
  102. void calculate (void)
  103. {
  104.     vector<int32_t> cnt(n + 5);
  105.     vector<int64_t> sum(n + 5);
  106.     //
  107.     auto get = []<typename T>(vector<T> &V, int l, int r) -> long long
  108.     {
  109.         return V[r] - V[l - 1];
  110.     };
  111.     //
  112.     for (int k = 1; k <= n / S; ++k)
  113.     {
  114.         fill(cnt.begin(), cnt.end(), 0);
  115.         fill(sum.begin(), sum.end(), 0);
  116.         for (int i = 0; i < min(n, k * S); ++i)
  117.             cnt[B[i]]++,
  118.             sum[B[i]] += A[i];
  119.         for (int i = 1; i <= n; ++i)
  120.             cnt[i] += cnt[i - 1],
  121.             sum[i] += sum[i - 1];
  122.         //
  123.         int i = -1;
  124.         long long res = 0;
  125.         //
  126.         sort(P[k].begin(), P[k].end());
  127.         for (auto [d, idx, inc] : P[k])
  128.         {
  129.             while (i + 1 < d)
  130.             {
  131.                 ++i;
  132.                 res += (get(cnt, 1, B[i] - 1) * A[i] - get(sum, 1, B[i] - 1))
  133.                      + (get(sum, B[i] + 1, n) - get(cnt, B[i] + 1, n) * A[i]);
  134.             }
  135.             ans[idx] += inc ? res : -res;
  136.         }
  137.     }
  138. }
  139. //
  140. void process (void)
  141. {
  142.     cin >> n >> q;
  143.     for (int i = 0; i < n; ++i)
  144.         cin >> A[i];
  145.     for (int i = 0; i < q; ++i)
  146.     {
  147.         int a, b, c, d;
  148.         //
  149.         cin >> a >> b >> c >> d;
  150.         query[i] = make_tuple(--a, b, --c, d);
  151.     }
  152.  
  153.     prepare();
  154.     calculate();
  155.  
  156.     for (int i = 0; i < q; ++i)
  157.         cout << ans[i] << '\n';
  158. }
  159. //
  160. signed main (void)
  161. {
  162.     ios_base::sync_with_stdio(false);
  163.     cin.tie(nullptr), cout.tie(nullptr);
  164.     process();
  165. }
Success #stdin #stdout 0s 5588KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Standard output is empty
https://ideone.com/fJBPF0
https://m...content-available-to-author-only...j.com/problem/266
language:
C++14 (gcc 8.3)
created:
17 hours 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!