Home » 国际竞赛 » Details

USACO 2021 February Contest, Platinum Problem 1. No Time to Dry

Category: 国际竞赛, 计算机国际竞赛 Date: 2022年7月4日下午4:42

USACO 2021 February Contest, Platinum Problem 1. No Time to Dry

Bessie has recently received a painting set, and she wants to paint the long fence at one end of her pasture. The fence consists of $N$ consecutive 1-meter segments ( $1 \leq N \leq 2 \cdot 10^{5}$ ). Bessie has $N$ different colors available, which she labels with the letters $1$ through $N$ in increasing order of darkness ( $1$ is a very light color, and $N$ is very dark). She can therefore describe the desired color she wants to paint each fence segment as an array of $N$ integers.

Initially, all fence segments are uncolored. Bessie can color any contiguous range of segments with a single color in a single brush stroke as long as she never paints a lighter color over a darker color (she can only paint darker colors over lighter colors).

For example, an initially uncolored segment of length four can be colored as follows:

0000 -> 1110 -> 1122 -> 1332

Unfortunately, Bessie doesn't have time to waste watching paint dry. Thus, Bessie thinks she may need to leave some fence segments unpainted! Currently, she is considering $Q$ candidate ranges ( $1 \leq Q \leq 2 \cdot 10^{5}$ ), each described by two integers $(a, b)$ with $1 \leq a \leq b \leq N$ giving the indices of endpoints of the range $a \dots b$ of segments to be painted.

For each candidate range, what is the minimum number of strokes needed to paint every fence segment inside the range with its desired color while leaving all fence segments outside the range uncolored? Note that Bessie does not actually do any painting during this process, so the answers for each candidate range are independent.

INPUT FORMAT (input arrives from the terminal / stdin):

The first line contains $N$ and $Q$ .The next line contains an array of $N$ integers representing the desired color for each fence segment.

The next $Q$ lines each contain two space-separated integers $a$ and $b$ representing a candidate range to possibly paint.

OUTPUT FORMAT (print output to the terminal / stdout):

For each of the $Q$ candidates, output the answer on a new line.

SAMPLE INPUT:

8 4
1 2 2 1 1 2 3 2
4 6
3 6
1 6
5 8

SAMPLE OUTPUT:

In this example, the sub-range corresponding to the desired pattern

1 1 2

requires two strokes to paint. The sub-range corresponding to the desired pattern

2 1 1 2

requires three strokes to paint. The sub-range corresponding to the desired pattern

1 2 2 1 1 2

requires three strokes to paint. The sub-range corresponding to the desired pattern

1 2 3 2

requires three strokes to paint.

SCORING:

Test cases 1-2 satisfy $N, Q \leq 100$ .
Test cases 3-5 satisfy $N, Q \leq 5000$ .
In test cases 6-10, the input array contains no integer greater than $10$ .
Test cases 11-20 satisfy no additional constraints.

Problem credits: Andi Qu, Brian Dean, and Benjamin Qi

USACO 2021 February Contest, Platinum Problem 1. No Time to Dry 题解(翰林国际教育提供，仅供参考)

题解请注册或登录查看

[/hide]

(Analysis by Benjamin Qi)

This is a harder version of a problem from last month's Silver contest.

Let $A_{a}$ denote the color of fence segment $a$ for each $a \in [1, N]$ .

Approach 1:

The minimum number of strokes required to paint a subrange $[a, b]$ is equal to $b - a + 1$ minus the number of indices $(l, r)$ such that $A_{l} = A_{r} < min_{l < i < r} A_{i}$ (similarly as Modern Art from the Gold contest).

In the sample case, the pairs of indices are $(1, 4)$ , $(2, 3)$ , $(4, 5)$ , and $(6, 8)$ .

To generate all such pairs of indices (there are $O (N)$ of them), we can use a monotonic stack (as alluded to by the analysis for the silver problem). The diagram below displays which elements are in the stack at what times for the sample case ( $1$ and $2$ remain in the stack at the end):

            3
  2-2     2---2- ...
1-----1-1------- ...

Computing the number of intervals contained within some query interval can be done offline in $O (\log N)$ per query; answer queries in increasing order of right endpoint and store a BIT for the left endpoints.

Time Complexity: $O ((N + Q) \log N)$

#include <bits/stdc++.h>
using namespace std;
 
#define f first
#define s second

const int MX = 2e5+5;

int N,Q;
vector<pair<int,int>> query[MX];

struct {
	int bit[MX];
	int sum(int i) {
		int sum = 0;
		for (;i;i-=i&-i) sum += bit[i];
		return sum;
	}
	int query(int l, int r) { return sum(r)-sum(l-1); }
	void inc(int i) { for (;i<MX;i+=i&-i) ++bit[i]; }
} BIT;

int main() {
	cin >> N >> Q; 
	vector<int> A(N), ans(Q); 
	for (int& t: A) cin >> t;
	for (int i = 0; i < Q; ++i) {
		int l,r; cin >> l >> r; --l,--r;
		query[r].push_back({l,i});
	}
	vector<int> stk;
	for (int i = 0; i < N; ++i) {
		while (!stk.empty() && A[stk.back()] > A[i]) stk.pop_back();
		if (!stk.empty() && A[stk.back()] == A[i]) { // consider pair (stk.back(),i)
			BIT.inc(1+stk.back());
			stk.back() = i;
		} else stk.push_back(i);
		for (pair<int,int> q: query[i])
			ans[q.s] = i-q.f+1-BIT.query(q.f+1,i+1);
	}
	for (int t: ans) cout << t << "\n";
}

Approach 2 (courtesy of Spencer Compton):

The pairs of indices above join the segments into several connected components. For example, the connected components in the sample case are $[1, 4, 5], [2, 3], [6, 8], [7]$ . Define $is_last [i]$ to be true if $i$ is the last number in its group and there exists some $j > i$ such that $A_{j} < A_{i}$ . So for the sample case, $is_last [3]$ and $is_last [7]$ are both true. As in the above solution, we can generate all such indices $i$ with a monotonic stack.

The answer for a query $[l, r]$ is equal to the number of $i \in [l, r]$ such that $is_last [i]$ is true (which we can compute in $O (1)$ using prefix sums), plus some additional contribution by connected components that continue past $r$ , if the greatest index included in such a component that is at most $r$ is at least $l$ .

For example, the answer to the query $(3, 6)$ in the sample case is $3$ because

$is_last [3]$ is true
The component starting at index $1$ continues past index $6$ , greatest index at most $6$ is $5 \geq 3$ .
The component starting at index $6$ continues past index $6$ , greatest index at most $6$ is $6 \geq 3$ .

We can maintain these indices in a stack $last_found$ . For every query, binary search on the stack to count the number of indices at least $l$ . The time complexity remains the same.

#include <bits/stdc++.h>
using namespace std;

const int MX = 2e5+5;

#define f first
#define s second
#define sz(x) (int)(x).size()

int N,Q;
vector<pair<int,int>> query[MX];

int main() {
	cin >> N >> Q;
	vector<int> A(N);
	for (int& t: A) cin >> t;
	for (int i = 0; i < Q; ++i) {
		int l,r; cin >> l >> r; --l,--r;
		query[r].push_back({l,i});
	}
	vector<bool> is_last(N);
	vector<pair<int,int>> stk;
	for (int i = 0; i < N; ++i) {
		while (!stk.empty() && stk.back().f > A[i]) {
			is_last[stk.back().s] = true;
			stk.pop_back();
		}
		if (!stk.empty() && stk.back().f == A[i]) stk.back().s = i;
		else stk.push_back({A[i],i});
	}
	vector<int> cum_last{0}, last_found;
	vector<int> ans(Q);
	for (int r = 0; r < N; ++r) {
		cum_last.push_back(cum_last.back());
		if (!last_found.empty() && A[r] == A[last_found.back()]) 
			last_found.pop_back();
		last_found.push_back(r);
		if (is_last[r]) {
			++cum_last.back();
			last_found.pop_back();
		}
		for (pair<int,int> p: query[r]) {
			int lo = 0, hi = sz(last_found);
			while (lo < hi) {
				int mid = (lo+hi)/2;
				if (p.f <= last_found[mid]) hi = mid;
				else lo = mid+1;
			}
			ans[p.s] = cum_last[r+1]-cum_last[p.f]+sz(last_found)-lo;
		}
	}
	for (int t: ans) cout << t << "\n";
}

[/hide]