結果
| 問題 | No.3330 Many Point Chmax Range Sum |
| ユーザー |
👑  ArcAki
|
| 提出日時 | 2025-06-03 10:54:20 |
| 言語 | C++23 (gcc 13.3.0 + boost 1.87.0) |
| 結果 |
AC
|
| 実行時間 | 643 ms / 3,500 ms |
| コード長 | 7,602 bytes |
| コンパイル時間 | 4,005 ms |
| コンパイル使用メモリ | 310,084 KB |
| 実行使用メモリ | 88,720 KB |
| 最終ジャッジ日時 | 2025-11-03 20:50:52 |
| 合計ジャッジ時間 | 18,384 ms |
|
ジャッジサーバーID （参考情報） |
judge1 / judge7 |
（要ログイン）
| ファイルパターン | 結果 |
|---|---|
| sample | AC * 2 |
| other | AC * 21 |
ソースコード
// GPT-o4-mini-highによる生成コード
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
struct Event {
int R, pos;
ll delta;
};
struct Query {
int idx;
int R, D, U;
};
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
int N, K, Q;
cin >> N >> K >> Q;
vector<ll> B(N + 1);
for (int i = 1; i <= N; i++) {
cin >> B[i];
}
// Prefix sums of B
vector<ll> P(N + 1, 0);
for (int i = 1; i <= N; i++) {
P[i] = P[i - 1] + B[i];
}
vector<int> p(K + 1);
vector<ll> X(K + 1);
for (int k = 1; k <= K; k++) {
cin >> p[k] >> X[k];
}
// Compute d[k] = X[k] - B[p[k]]; only keep if positive
vector<ll> d(K + 1, 0);
vector<vector<pair<int,ll>>> updList(N + 1);
for (int k = 1; k <= K; k++) {
ll diff = X[k] - B[p[k]];
if (diff > 0) {
d[k] = diff;
updList[p[k]].push_back({k, diff});
}
}
// For each position, compute prev/next greater among its updates
// We'll collect primitive events: at certain L, (R,pos,delta)
vector<vector<Event>> event_list(K + 2); // L from 1..K+1
for (int i = 1; i <= N; i++) {
auto &vec = updList[i];
int m = (int)vec.size();
if (m == 0) continue;
vector<int> times(m);
vector<ll> vals(m);
for (int j = 0; j < m; j++) {
times[j] = vec[j].first;
vals[j] = vec[j].second;
}
vector<int> prev_greater(m, -1), next_greater(m, m);
// prev greater: nearest j' < j with vals[j'] > vals[j]
{
vector<int> st;
for (int j = 0; j < m; j++) {
while (!st.empty() && vals[st.back()] <= vals[j]) {
st.pop_back();
}
if (!st.empty()) prev_greater[j] = st.back();
else prev_greater[j] = -1;
st.push_back(j);
}
}
// next greater: nearest j' > j with (vals[j'] > vals[j]) OR (vals[j'] == vals[j])
// i.e., nearest with vals[j'] >= vals[j]
{
vector<int> st;
for (int j = m - 1; j >= 0; j--) {
while (!st.empty() && vals[st.back()] < vals[j]) {
st.pop_back();
}
if (!st.empty()) next_greater[j] = st.back();
else next_greater[j] = m;
st.push_back(j);
}
}
// For each j, compute L_low, L_high, R_low, R_high, generate events
for (int j = 0; j < m; j++) {
int T_j = times[j];
int T_prev = (prev_greater[j] == -1 ? 0 : times[prev_greater[j]]);
int T_next = (next_greater[j] == m ? K + 1 : times[next_greater[j]]);
int L_low = T_prev + 1;
int L_high = T_j;
int R_low = T_j;
int R_high = T_next - 1;
ll delta = vals[j];
// At L = L_low: add +delta on [R_low, R_high] at pos=i
// At L = L_high+1: add -delta on [R_low, R_high] at pos=i
// Decompose range update on R into two point updates: at R_low: +delta; at R_high+1: -delta
// Activation at L_low:
if (L_low <= K) {
// +delta at R_low
event_list[L_low].push_back({R_low, i, +delta});
// -delta at R_high+1 (i.e., at R = R_high+1)
if (R_high + 1 <= K + 1) {
event_list[L_low].push_back({R_high + 1, i, -delta});
}
}
// Deactivation at L_high + 1:
int L_off = L_high + 1;
if (L_off <= K + 1) {
// -delta at R_low
event_list[L_off].push_back({R_low, i, -delta});
// +delta at R_high+1
if (R_high + 1 <= K + 1) {
event_list[L_off].push_back({R_high + 1, i, +delta});
}
}
}
}
// Read queries, group by L_q
vector<vector<Query>> query_list(K + 2);
vector<ll> ans_extra(Q, 0);
vector<int> qL(Q), qR(Q), qD(Q), qU(Q);
for (int j = 0; j < Q; j++) {
int Lq, Rq, Dq, Uq;
cin >> Lq >> Rq >> Dq >> Uq;
qL[j] = Lq;
qR[j] = Rq;
qD[j] = Dq;
qU[j] = Uq;
if (Lq <= K) {
query_list[Lq].push_back({j, Rq, Dq, Uq});
}
}
// Build BIT-of-BIT structure over R in [1..K+1], pos in [1..N]
int Rmax = K + 1;
vector<vector<int>> BIT_nodes(Rmax + 1);
// Collect all (R,pos) from primitive events
for (int L = 1; L <= K + 1; L++) {
for (auto &e : event_list[L]) {
int R = e.R;
int pos = e.pos;
for (int i = R; i <= Rmax; i += (i & -i)) {
BIT_nodes[i].push_back(pos);
}
}
}
// Also, for queries, we need to query pos up to qU and qD-1; no need to add pos here,
// as BIT_nodes only stores pos that appear in updates.
// Sort & deduplicate BIT_nodes, and create BIT_vals
vector<vector<ll>> BIT_vals(Rmax + 1);
for (int i = 1; i <= Rmax; i++) {
auto &vec = BIT_nodes[i];
if (!vec.empty()) {
sort(vec.begin(), vec.end());
vec.erase(unique(vec.begin(), vec.end()), vec.end());
BIT_vals[i].assign(vec.size() + 1, 0LL);
}
}
// BIT-of-BIT update: add delta at (R,pos)
auto bit_update = [&](int R, int pos, ll delta) {
for (int i = R; i <= Rmax; i += (i & -i)) {
auto &nodes = BIT_nodes[i];
if (nodes.empty()) continue;
int idx = int(lower_bound(nodes.begin(), nodes.end(), pos) - nodes.begin()) + 1;
auto &vals = BIT_vals[i];
int sz = (int)nodes.size();
for (int t = idx; t <= sz; t += (t & -t)) {
vals[t] += delta;
}
}
};
// BIT-of-BIT query: sum of values for R' ≤ R_q and pos' ≤ x
auto bit_query = [&](int R, int x) {
ll res = 0;
for (int i = R; i > 0; i -= (i & -i)) {
auto &nodes = BIT_nodes[i];
if (nodes.empty()) continue;
int idx = int(upper_bound(nodes.begin(), nodes.end(), x) - nodes.begin());
if (idx <= 0) continue;
auto &vals = BIT_vals[i];
for (int t = idx; t > 0; t -= (t & -t)) {
res += vals[t];
}
}
return res;
};
// Sweep L from 1 to K+1
for (int L = 1; L <= K + 1; L++) {
// Process all primitive events at this L
for (auto &e : event_list[L]) {
int R = e.R;
int pos = e.pos;
ll delta = e.delta;
if (R >= 1 && R <= Rmax) {
bit_update(R, pos, delta);
}
}
// Process queries with L_q = L
if (L <= K) {
for (auto &q : query_list[L]) {
int j = q.idx;
int Rq = q.R;
int Dq = q.D;
int Uq = q.U;
if (Rq > Rmax) Rq = Rmax;
ll sumU = bit_query(Rq, Uq);
ll sumD_1 = bit_query(Rq, Dq - 1);
ans_extra[j] = sumU - sumD_1;
}
}
}
// Compute final answers
vector<ll> ans(Q, 0);
for (int j = 0; j < Q; j++) {
ll base = P[qU[j]] - P[qD[j] - 1];
ans[j] = base + ans_extra[j];
}
// Output
ostringstream oss;
for (int j = 0; j < Q; j++) {
oss << ans[j] << '\n';
}
cout << oss.str();
return 0;
}