Submission #1168162

#	Time	Username	Problem	Language	Result	Execution time	Memory
1168162		fryingduc	Fire (JOI20_ho_t5)	C++20	100 / 100	183 ms	39988 KiB

ho_t5

#include "bits/stdc++.h"

using namespace std;

#ifdef duc_debug
#include "bits/debug.h"
#else
#define debug(...)
#endif

const int maxn = 2e5 + 5;
const int N = 4e5 + 5;
const int LG = 19;
int n, q;
int a[maxn];
long long res[maxn];
int le[maxn], ri[maxn];

vector<tuple<int, int, int>> ev[maxn];
vector<tuple<int, int, int>> que[maxn];

struct fenwick_tree {
  long long bit[N];
  
  void update(int i, long long val) {
    for (; i < N; i += i & (-i)) {
      bit[i] += val;
    }
  }
  
  long long get(int i) {
    long long ans = 0;
    for (; i > 0; i -= i & (-i)) {
      ans += bit[i];
    }
    return ans;
  }
} fen[4];

void update(int l, int r, long long x) {
  fen[0].update(l, x);
  fen[1].update(r + 1, -x);
  fen[2].update(l, -1ll * (l - 1) * x);
  fen[3].update(r + 1, 1ll * r * x);
}

long long get(int i, int t) {
  i += n;
  // stable cases
  long long res = fen[3].get(i) + fen[2].get(i - t); 
  // handling expansion cases
  res += 1ll * (fen[1].get(i) + fen[0].get(i - t)) * (i - t);
  return res + fen[1].get(i) * t;
}

void solve() {
  cin >> n >> q;
  for (int i = 1; i <= n; ++i) {
    cin >> a[i];
  }
  for (int i = 1; i <= q; ++i) {
    int t, l, r; cin >> t >> l >> r;
    que[t].emplace_back(l, r, i);
  }
  stack<int> st;
  for (int i = 1; i <= n; ++i) {
    while (!st.empty() and a[st.top()] <= a[i]) st.pop();
    le[i] = (st.empty() ? -n : st.top());
    st.push(i);
  }
  st = stack<int>();
  for (int i = n; i; --i) {
    while (!st.empty() and a[st.top()] < a[i]) st.pop();
    ri[i] = (st.empty() ? n + 1 : st.top());
    st.push(i);
    auto add = [&](int l, int r, int x, int v) {
      l += n, r += n;
      ev[0].emplace_back(l, r, v);
      if (x <= n) {
        ev[x].emplace_back(l, r, -v);
      }
    };
    if (le[i] + 1 < i) {
      // expand
      add(le[i] + 1, i - 1, i - le[i] - 1, -a[i]);
    }
    if (i + 1 < ri[i]) {
      // expand
      add(i + 1, ri[i] - 1, ri[i] - i - 1, -a[i]);
    }
    // decay
    add(le[i] + 1, ri[i] - 1, ri[i] - le[i] - 1, a[i]);
  }
  for (int i = 0; i <= n; ++i) {
    for (auto [l, r, x] : ev[i]) {
      update(l, r, x);
    }
    for (auto [l, r, id] : que[i]) {
      res[id] = get(r, i) - get(l - 1, i);
    }
  }
  for (int i = 1; i <= q; ++i) {
    cout << res[i] << '\n';
  }
}

signed main() {
  ios_base::sync_with_stdio(0);
  cin.tie(0);
  
  solve();

  return 0;
}

• Subtask 1: 1 / 1
• Subtask 2: 6 / 6
• Subtask 3: 7 / 7
• Subtask 4: 6 / 6
• Subtask 5: 80 / 80