Overview

For each observation site, we need to find the maximum difference between the maximum and minimum temperatures over any continuous \(K\) days (the temperature fluctuation score), and count the number of sites where this score is at least the threshold \(T\).

Analysis

The key point of this problem is “how to efficiently find the maximum and minimum values in intervals of length \(K\) for each site.”

In a naive approach, we would search for the maximum and minimum values for all intervals of length \(K\) in a brute-force manner. Since we need \(K\) comparisons per interval and there are \(M - K + 1\) intervals, the time complexity per site would be \(O(M \times K)\). Under the constraints of \(N \times M \leq 2 \times 10^6\) and \(K \leq M \leq 10^5\), the worst-case time complexity becomes \(O(N \times M \times K)\), which results in TLE (Time Limit Exceeded).

To solve this, we can use the sliding window algorithm. When sliding the window one day at a time, by cleverly utilizing the relationship between the newly entering element and the old elements, we can update the maximum and minimum values in \(O(1)\) time, reducing the time complexity per site to \(O(M)\).

Algorithm

We can efficiently find the maximum and minimum values for each interval of length \(K\) using a sliding window. We will use a double-ended queue (deque).

Steps to find the maximum value: 1. Prepare a deque to store the indices of the elements. 2. Iterate through the elements of the array from the beginning. 3. If the temperature pointed to by the index at the back of the deque is less than or equal to the current temperature, that index can never become the maximum in any future window. Thus, we remove it from the back of the deque (repeat this until the current temperature is less than the temperature at the back of the deque). 4. Push the current index to the back of the deque. 5. If the index at the front of the deque is out of the range of the current window (width \(K\)), remove it. 6. Once the window width reaches \(K\), the temperature pointed to by the index at the front of the deque will be the maximum value for that interval.

The steps to find the minimum value are similar, with the difference being that we remove indices from the back of the deque if the temperature they point to is greater than or equal to the current temperature.

Once we obtain the maximum values array max_vals and the minimum values array min_vals for each interval of length \(K\) at each site, we calculate the difference max_vals[j] - min_vals[j] for each interval, and find the maximum of these differences as the temperature fluctuation score. If this score is greater than or equal to the threshold \(T\), we increment the count.

Complexity

• Time Complexity: \(O(N \times M)\) At each observation site, the sliding window process for finding the maximum and minimum values takes \(O(M)\) time. Since there are \(N\) sites in total, the overall time complexity is \(O(N \times M)\).
• Space Complexity: \(O(M)\) We allocate arrays of size \(M\) to store the temperature data for each site and the maximum/minimum values for intervals of length \(K\). Since we can process one site at a time and reuse the memory, the overall space complexity is \(O(M)\).

Implementation Points

• The temperature range is \(-10^9 \leq S_{i,j} \leq 10^9\), which means the difference between the maximum and minimum values can be up to \(2 \times 10^9\). Since this value is very close to or can potentially exceed the maximum limit of a 32-bit signed integer (int, which is about \(2.1 \times 10^9\)), it is necessary to use 64-bit integers (long long in C++) for storing temperature data and calculating scores.

• The threshold \(T\) can also be up to \(2 \times 10^9\), so it should be read as a long long type as well.

• Due to the large amount of input/output, it is safer to speed up I/O operations using cin.tie(0); ios::sync_with_stdio(false); in C++.

  Source Code

#include <iostream>
#include <vector>
#include <deque>
#include <algorithm>

using namespace std;

int main() {
    cin.tie(0);
    ios::sync_with_stdio(false);
    
    int N, M, K;
    long long T;
    if (!(cin >> N >> M >> K >> T)) return 0;
    
    int ans = 0;
    for (int i = 0; i < N; i++) {
        vector<long long> S(M);
        for (int j = 0; j < M; j++) {
            cin >> S[j];
        }
        
        vector<long long> max_vals(M - K + 1);
        {
            deque<int> dq;
            for (int j = 0; j < M; j++) {
                while (!dq.empty() && S[dq.back()] <= S[j]) dq.pop_back();
                dq.push_back(j);
                if (dq.front() <= j - K) dq.pop_front();
                if (j >= K - 1) max_vals[j - K + 1] = S[dq.front()];
            }
        }
        
        vector<long long> min_vals(M - K + 1);
        {
            deque<int> dq;
            for (int j = 0; j < M; j++) {
                while (!dq.empty() && S[dq.back()] >= S[j]) dq.pop_back();
                dq.push_back(j);
                if (dq.front() <= j - K) dq.pop_front();
                if (j >= K - 1) min_vals[j - K + 1] = S[dq.front()];
            }
        }
        
        long long score = 0;
        for (int j = 0; j < M - K + 1; j++) {
            score = max(score, max_vals[j] - min_vals[j]);
        }
        
        if (score >= T) {
            ans++;
        }
    }
    
    cout << ans << endl;
    
    return 0;
}

This editorial was generated by or-glm5.2-high.