E - ストレスメーター / Stress Meter Editorial by admin
gpt-5.5-xhighOverview
For each query, we want to find the limit-reached count \(C\) and the final stress value \(G\) when processing only the tasks in the interval \([L,R]\) starting from \(G=0, C=0\).
The key insight is that since \(K \leq 300\) is small, we can precompute “how an input stress value \(G\) changes when processing a certain interval” for all possible states.
Analysis
First, let’s revisit the processing of task \(i\).
Task processing consists of:
- \(G \leftarrow G + A_i\)
- \(G \leftarrow \max(0, G - B_i)\)
- If \(G \geq K\), increment \(C\) by \(1\) and set \(G \leftarrow 0\)
Combining steps 1 and 2, we get:
\[ G \leftarrow \max(0, G + A_i - B_i) \]
Therefore, the effect of task \(i\) does not require looking at \(A_i\) and \(B_i\) individually; it is determined solely by:
\[ D_i = A_i - B_i \]
If the current stress value is \(g\), then after task \(i\):
- If \(g + D_i \geq K\), the limit is reached, \(C\) increases by \(1\), and \(g=0\)
- If \(g + D_i \leq 0\), then \(g=0\)
- Otherwise, \(g \leftarrow g + D_i\)
The important observation here is that after processing each task, the following always holds:
\[ 0 \leq G < K \]
This is because whenever \(G \geq K\), it is immediately reset to \(0\).
In other words, the processing of each interval can be represented as a “function” that, for an input \(G \in \{0,1,\dots,K-1\}\), determines:
- How many times the limit-reached count increases
- What the final value of \(G\) becomes
If we naively simulate from \(L\) to \(R\) for each query, the worst case is:
\[ O(NQ) \]
Given the constraints \(N,Q \leq 6 \times 10^4\), this is too slow.
Instead, we precompute the “transformation function” for each interval and compose them to answer queries efficiently.
Algorithm
1. Store the difference for each task
For each task, compute:
\[ D_i = A_i - B_i \]
The process of applying a single task looks like this:
x = g + D_i;
if (x >= K) {
c++;
g = 0;
} else if (x <= 0) {
g = 0;
} else {
g = x;
}
2. Divide into blocks
Divide the task sequence into small blocks of length around \(16\).
For each block, precompute the result of processing the entire block for all initial values:
\[ g = 0,1,\dots,K-1 \]
Specifically, for block \(b\):
nxt[b][g]: the stress value after processing the block when the initial stress value is \(g\)add[b][g]: the number of limit-reached count increases within the block when the initial stress value is \(g\)
3. Build a segment tree on top of the block sequence
Build a segment tree with blocks as leaves.
Each node holds the transformation corresponding to its entire contiguous range of blocks.
Suppose a node consists of a left part \(L\) and a right part \(R\).
Given an initial value \(g\):
- Process the left part
- The limit-reached count increases by
add[L][g] - The stress value becomes
nxt[L][g]
- The limit-reached count increases by
- Use that result as input to process the right part
Therefore, the composition is as follows:
\[ mid = nxt_L[g] \]
\[ add[g] = add_L[g] + add_R[mid] \]
\[ nxt[g] = nxt_R[mid] \]
In this way, we compute the values for all \(g\) at each node of the segment tree.
4. Answering queries
For a query interval \([L,R]\), first look at the blocks that \(L\) and \(R\) belong to.
- The partial portion of the leftmost block
- The partial portion of the rightmost block
have at most block-size elements, so we simulate them directly.
For the complete blocks fully contained in between, we use the segment tree to apply them all at once.
An important note is that the order of processing matters.
Since function composition is generally not commutative, the nodes obtained from the segment tree must be applied in left-to-right order.
In the code, nodes coming from the right side are temporarily stored in an array and then applied in reverse order at the end, preserving the overall left-to-right order.
Complexity
Let the block size be \(B\). In the code, \(B=16\).
Precomputation:
- Simulating \(K\) initial values for each block: \(O(NK)\)
- Building the segment tree: \(O\left(\frac{N}{B}K\right)\)
Per query:
- Directly processing the partial portions at both ends: \(O(B)\)
- Traversing segment tree nodes: \(O\left(\log \frac{N}{B}\right)\)
Therefore, the overall complexity is:
- Time complexity: \(O\left(NK + Q\left(B + \log \frac{N}{B}\right)\right)\)
- Space complexity: \(O\left(\frac{N}{B}K\right)\)
Since \(B=16\) is a constant, this is approximately:
- Time complexity: \(O(NK + Q\log N)\)
- Space complexity: \(O(NK/B)\)
Implementation Notes
For each task, only \(A_i - B_i\) is needed.
Since \(0 \leq G < K\) always holds after processing each task, the number of states is only \(K\).
nxtstores the final \(G\), andaddstores the increase in the limit-reached count.When composing segment tree nodes, the stress value after processing the left part is used as input for the right part.
In range queries, the processing order must always be maintained from left to right.
Since \(K \leq 300\) and the limit-reached count is at most \(N \leq 60000\),
uint16_tis sufficient in the code.Source Code
#include <bits/stdc++.h>
using namespace std;
static inline void apply_delta(int d, int K, int &g, int &c) {
int x = g + d;
if (x >= K) {
++c;
g = 0;
} else if (x <= 0) {
g = 0;
} else {
g = x;
}
}
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
int N, K, Q;
cin >> N >> K >> Q;
vector<int> D(N);
for (int i = 0; i < N; ++i) {
int A, B;
cin >> A >> B;
D[i] = A - B;
}
constexpr int BS = 16;
int nb = (N + BS - 1) / BS;
int SZ = 1;
while (SZ < nb) SZ <<= 1;
int nodes = 2 * SZ;
vector<uint16_t> nxt((size_t)nodes * K);
vector<uint16_t> add((size_t)nodes * K, 0);
for (int b = 0; b < SZ; ++b) {
size_t base = (size_t)(SZ + b) * K;
for (int g = 0; g < K; ++g) {
nxt[base + g] = (uint16_t)g;
}
}
for (int b = 0; b < nb; ++b) {
int s = b * BS;
int e = min(N, s + BS);
size_t base = (size_t)(SZ + b) * K;
for (int g0 = 0; g0 < K; ++g0) {
int g = g0, c = 0;
for (int i = s; i < e; ++i) {
apply_delta(D[i], K, g, c);
}
nxt[base + g0] = (uint16_t)g;
add[base + g0] = (uint16_t)c;
}
}
for (int v = SZ - 1; v >= 1; --v) {
size_t base = (size_t)v * K;
size_t lb = (size_t)(v << 1) * K;
size_t rb = (size_t)((v << 1) | 1) * K;
for (int g0 = 0; g0 < K; ++g0) {
int mid = nxt[lb + g0];
add[base + g0] = (uint16_t)(add[lb + g0] + add[rb + mid]);
nxt[base + g0] = nxt[rb + mid];
}
}
auto apply_node = [&](int v, int &g, int &c) {
size_t idx = (size_t)v * K + g;
c += add[idx];
g = nxt[idx];
};
while (Q--) {
int L, R;
cin >> L >> R;
--L;
--R;
int g = 0, c = 0;
int bl = L / BS;
int br = R / BS;
if (bl == br) {
for (int i = L; i <= R; ++i) {
apply_delta(D[i], K, g, c);
}
} else {
int left_end = min(N, (bl + 1) * BS);
for (int i = L; i < left_end; ++i) {
apply_delta(D[i], K, g, c);
}
int ql = bl + 1;
int qr = br;
if (ql < qr) {
int l = ql + SZ;
int r = qr + SZ;
int rights[64];
int rc = 0;
while (l < r) {
if (l & 1) apply_node(l++, g, c);
if (r & 1) rights[rc++] = --r;
l >>= 1;
r >>= 1;
}
while (rc > 0) {
apply_node(rights[--rc], g, c);
}
}
int right_start = br * BS;
for (int i = right_start; i <= R; ++i) {
apply_delta(D[i], K, g, c);
}
}
cout << c << ' ' << g << '\n';
}
return 0;
}
This editorial was generated by gpt-5.5-xhigh.
posted:
last update: