Colored Rectangle Queries
National Olympiad — National round (2017 season)
Submission name: row.cpp
Problem summary
N rectangles stand next to one another on a common baseline. Rectangle r has base b, height h, and a color from 1 through 5. Baseline boundaries are P0 through PN. For each query i,j,c, find the total area of color-c rectangles between Pi and Pj.
Input
N; N triples base, height, color; Q; then Q triples i,j,c.
Output
One total area per query.
Constraints
2 < N < 300000; 0 < Q < 50000; positive integer sides < 30; 1 ≤ color ≤ 5; 0 ≤ i < j ≤ N.
Worked example
An independently prepared example for this explanation.
Input
6 2 5 2 1 4 4 3 6 2 2 7 4 4 4 2 1 9 2 5 0 1 2 0 6 2 1 4 4 0 4 2 3 6 1
Output
10 53 18 28 0
Solution analysis
- Make a separate prefix sum for each of the five colors. prefix[r][c] stores the area of color c among the first r rectangles, with prefix[0][c] = 0.
- For each new rectangle, copy the preceding five totals and add base·height only to its color. The query boundaries Pi and Pj enclose rectangles i+1 through j, so answer prefix[j][c] − prefix[i][c].
- In the sample, color 2 has areas 10,18,16,9 at rectangles 1,3,5,6. Query (0,6,2) returns 53; query (0,4,2) includes only the first two of these areas and returns 28.
Why it works
By induction, each prefix total contains exactly the matching-colored areas in the first r rectangles. Subtracting the first i rectangles from the first j cancels precisely the rectangles outside the queried interval, leaving the required sum.
Watch out. Pi is a boundary, not rectangle i: subtract prefix[i], not prefix[i−1]. An absent color has sum zero.
Commented C++17 solution
An independently written complete program with standard headers.
#include <algorithm>
#include <array>
#include <iostream>
#include <numeric>
#include <string>
#include <vector>
using namespace std;
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
int n;
cin >> n;
vector<array<int, 6>> prefix(n + 1);
for (int r = 1; r <= n; ++r) {
int base, height, color;
cin >> base >> height >> color;
// Copy every color total, then change only the current rectangle color.
prefix[r] = prefix[r - 1];
prefix[r][color] += base * height;
}
int q;
cin >> q;
while (q-- > 0) {
int i, j, color;
cin >> i >> j >> color;
cout << prefix[j][color] - prefix[i][color] << '\n';
}
}