제출 #1042521

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1042521		juicy	Fire (JOI20_ho_t5)	C++17	100 / 100	151 ms	45380 KiB

ho_t5

#include <bits/stdc++.h>

using namespace std;

#ifdef LOCAL
#include "debug.h"
#else
#define debug(...) 42
#endif

const int N = 2e5 + 5;

int n, q;
int a[N], lt[N];
long long res[N];
vector<array<int, 3>> events[N], Queries[N];

struct Fenwick {
  long long s[2 * N];

  void upd(int i, long long x) {
    for (; i <= 2 * n; i += i & -i) {
      s[i] += x;
    }
  }
  
  long long qry(int i) {
    long long res = 0;
    for (; i; i -= i & -i) {
      res += s[i];
    }
    return res;
  }
} ft[4];

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

long long qry(int i, int t) {
  i += n;
  auto A = ft[0].qry(i - t), B = ft[1].qry(i), C = ft[2].qry(i - t), D = ft[3].qry(i);
  return (A + B) * (i - t) + C + D + B * t;
}

void add(int l, int r, int h, int x) {
  l += n, r += n;
  events[0].push_back({l, r, x});
  if (h <= n) {
    events[h].push_back({l, r, -x});
  }
}

int main() {
  ios::sync_with_stdio(false); cin.tie(nullptr);

  cin >> n >> q;
  for (int i = 1; i <= n; ++i) {
    cin >> a[i];
  }
  for (int i = 1; i <= q; ++i) {
    int l, r, t; cin >> t >> l >> r;
    Queries[t].push_back({l, r, i});
  }
  vector<int> st = {-n};
  for (int i = 1; i <= n; ++i) {
    while (st.size() > 1 && a[st.back()] <= a[i]) {
      st.pop_back();
    }
    lt[i] = st.back();
    st.push_back(i);
  }
  st.clear();
  st.push_back(n + 1);
  for (int i = n; i > 0; --i) {
    while (st.size() > 1 && a[st.back()] < a[i]) {
      st.pop_back();
    }
    int r = st.back();
    if (lt[i] + 1 < i) {
      add(lt[i] + 1, i - 1, i - lt[i] - 1, -a[i]);
    }
    if (i < r - 1) {
      add(i + 1, r - 1, r - i - 1, -a[i]);
    }
    add(lt[i] + 1, r - 1, r - lt[i] - 1, a[i]);
    st.push_back(i);
  }
  for (int t = 0; t <= n; ++t) {
    for (auto [l, r, x] : events[t]) {
      upd(l, r, x);
    }
    for (auto [l, r, id] : Queries[t]) {
      res[id] = qry(r, t) - qry(l - 1, t);
    }
  }
  for (int i = 1; i <= q; ++i) {
    cout << res[i] << "\n";
  }
  return 0;
}

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