제출 #1042472

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1042472		juicy	Fire (JOI20_ho_t5)	C++17	1 / 100	76 ms	51392 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;
    }
  }

  void upd(int l, int r, long long x) {
    upd(l, x);
    upd(r + 1, -x);
  }

  long long qry(int i) {
    long long res = 0;
    for (; i; i -= i & -i) {
      res += s[i];
    }
    return res;
  }

  long long qry(int l, int r) {
    return qry(r) - qry(l - 1);
  }
} ft[5];

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

long long qry(int i, int t) {
  i += n;
  long long x = ft[2].qry(i) + ft[3].qry(i - t + 1, i);
  return ft[0].qry(i) + ft[1].qry(i) * t + x * (i + 1 - t) + ft[4].qry(i - t + 1, i);
}

void add(int l, int r, int h, int x) {
  l += n, r += n;
  events[0].push_back({l, r, x});
  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: 0 / 6
• Subtask 3: 0 / 7
• Subtask 4: 0 / 6
• Subtask 5: 0 / 80