fork download
copy 
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3.  
  4. // Structure to store differences applied to the Fenwick Trees
  5. struct Event {
  6.     int type; // 0 for Vertical, 1 for Diagonal
  7.     int pos;
  8.     long long val;
  9. };
  10.  
  11. // Structure for offline prefix queries
  12. struct Query {
  13.     int X;
  14.     int sign;
  15.     int id;
  16. };
  17.  
  18. // Binary Indexed Tree designed using __int128_t to completely prevent large sum overflows
  19. struct BIT {
  20.     int n;
  21.     vector<__int128_t> tree;
  22.     BIT(int n) : n(n), tree(n + 1, 0) {}
  23.  
  24.     void add(int i, __int128_t delta) {
  25.         if (i <= 0) return;
  26.         for (; i <= n; i += i & -i) tree[i] += delta;
  27.     }
  28.  
  29.     __int128_t query(int i) {
  30.         if (i <= 0) return 0;
  31.         i = min(i, n);
  32.         __int128_t sum = 0;
  33.         for (; i > 0; i -= i & -i) sum += tree[i];
  34.         return sum;
  35.     }
  36. };
  37.  
  38. // Safely queues the boundary events ensuring they are added within valid time T bounds
  39. void add_seg(int type, int pos, long long V, long long Ts, long long Te, vector<vector<Event>>& evs, int N) {
  40.     Ts = max(0LL, Ts);
  41.     Te = min((long long)N, Te);
  42.     if (Ts <= Te) {
  43.         evs[Ts].push_back({type, pos, V});
  44.         if (Te + 1 <= N) {
  45.             evs[Te + 1].push_back({type, pos, -V});
  46.         }
  47.     }
  48. }
  49.  
  50. int main() {
  51.     // Fast I/O
  52.     ios_base::sync_with_stdio(false);
  53.     cin.tie(NULL);
  54.  
  55.     int N, Q;
  56.     if (!(cin >> N >> Q)) return 0;
  57.  
  58.     vector<long long> S(N + 1);
  59.     for (int i = 1; i <= N; ++i) {
  60.         cin >> S[i];
  61.     }
  62.  
  63.     // P[i]: largest j < i such that S[j] > S[i]
  64.     vector<int> P(N + 1);
  65.     vector<int> st;
  66.     for (int i = 1; i <= N; ++i) {
  67.         while (!st.empty() && S[st.back()] <= S[i]) st.pop_back();
  68.         P[i] = st.empty() ? -1e9 : st.back();
  69.         st.push_back(i);
  70.     }
  71.  
  72.     // N_idx[i]: smallest j > i such that S[j] >= S[i]
  73.     vector<int> N_idx(N + 1);
  74.     st.clear();
  75.     for (int i = N; i >= 1; --i) {
  76.         while (!st.empty() && S[st.back()] < S[i]) st.pop_back();
  77.         N_idx[i] = st.empty() ? N + 1 : st.back();
  78.         st.push_back(i);
  79.     }
  80.  
  81.     vector<vector<Event>> evs(N + 2);
  82.     for (int i = 1; i <= N; ++i) {
  83.         long long p = P[i];
  84.         long long n = N_idx[i];
  85.         long long v = S[i];
  86.  
  87.         // Generate the 4 boundary segments for the geometric region mapped to this S[i]
  88.         // Pos 1 (Vertical):  Starts immediately, stops when it hits diagonal overlap
  89.         add_seg(0, i, v, 0, i - p - 1, evs, N);
  90.         // Pos 2 (Diagonal):  Takes over after vertical overlap finishes
  91.         add_seg(1, p + 1, v, i - p, n - p - 2, evs, N);
  92.  
  93.         // Neg 1 (Diagonal):  Maintains bounded window sliding rightward
  94.         add_seg(1, i + 1, -v, 0, n - i - 1, evs, N);
  95.         // Neg 2 (Vertical):  Cutoff segment if a greater/equal element takes rightward dominance
  96.         add_seg(0, n, -v, n - i, n - p - 2, evs, N);
  97.     }
  98.  
  99.     // Subdividing range queries into prefix summations
  100.     vector<vector<Query>> queries(N + 2);
  101.     for (int j = 0; j < Q; ++j) {
  102.         int T, L, R;
  103.         cin >> T >> L >> R;
  104.         queries[T].push_back({R, 1, j});
  105.         queries[T].push_back({L - 1, -1, j});
  106.     }
  107.  
  108.     BIT bit_V(N + 2), bit_yV(N + 2);
  109.     BIT bit_D(N + 2), bit_CD(N + 2);
  110.     vector<long long> ans(Q, 0);
  111.  
  112.     // Sweep-line passing over time intervals T
  113.     for (int T = 0; T <= N; ++T) {
  114.         for (auto& ev : evs[T]) {
  115.             if (ev.type == 0) {
  116.                 bit_V.add(ev.pos, ev.val);
  117.                 bit_yV.add(ev.pos, (__int128_t)ev.pos * ev.val);
  118.             } else {
  119.                 bit_D.add(ev.pos, ev.val);
  120.                 bit_CD.add(ev.pos, (__int128_t)ev.pos * ev.val);
  121.             }
  122.         }
  123.  
  124.         // Answer all sub-queries offline at the current T 
  125.         for (auto& q : queries[T]) {
  126.             if (q.X == 0) continue;
  127.             long long X = q.X;
  128.             __int128_t res = 0;
  129.  
  130.             // Prefix formulas factoring (X + 1) * V - y * V offsets
  131.             __int128_t sum_V = bit_V.query(X);
  132.             __int128_t sum_yV = bit_yV.query(X);
  133.             res += (X + 1) * sum_V - sum_yV;
  134.  
  135.             if (X - T >= 1) {
  136.                 __int128_t sum_D = bit_D.query(X - T);
  137.                 __int128_t sum_CD = bit_CD.query(X - T);
  138.                 res += (X + 1 - T) * sum_D - sum_CD;
  139.             }
  140.  
  141.             if (q.sign == 1) ans[q.id] += (long long)res;
  142.             else ans[q.id] -= (long long)res;
  143.         }
  144.     }
  145.  
  146.     for (int j = 0; j < Q; ++j) {
  147.         cout << ans[j] << "\n";
  148.     }
  149.  
  150.     return 0;
  151. }
Success #stdin #stdout 0s 5308KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Standard output is empty
https://ideone.com/GXNixI
language:
C++14 (gcc 8.3)
created:
1 hour 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!