Overview

For each observation site, we are given temperature data of length \(M\). The goal is to find the maximum value of “the difference between the maximum and minimum values in a continuous \(K\)-day window” (temperature fluctuation score), and count the number of sites where this score is at least the threshold \(T\).

Analysis

First, we can see that we can calculate the “temperature fluctuation score” for each observation site independently. The essence of the problem is to efficiently find the maximum and minimum values in all continuous intervals of length \(K\) (sliding windows) for a single sequence.

Limitations of a Naive Approach

If we naively calculate the maximum and minimum values for each interval, it takes \(O(K)\) per interval. Since there are approximately \(M\) intervals, it takes \(O(MK)\) per site. For all sites, the total time complexity would be \(O(NMK)\). With the constraints \(N \times M \leq 2 \times 10^6\) and \(K\) up to \(10^5\), this will easily exceed the time limit.

Key Idea

This is where the sliding window maximum/minimum technique comes in handy. When we slide the window from left to right one step at a time, at each step, “one new element enters, and one old element leaves.” Utilizing this property, we can find the maximum and minimum values of all intervals in linear time.

The key observations are as follows:

• When finding the maximum value, if a value \(b\) (where \(b \geq a\)) appears after some element \(a\) within the window, \(a\) can never be the maximum again (because \(b\) is newer and larger).
• Therefore, we only need to maintain the candidates by discarding such “useless in the future” elements.

We can use a double-ended queue (deque) to manage this.

Algorithm

We prepare separate deques for the maximum and minimum values. The deques will store indices.

Deque for Maximums (maintained in monotonically decreasing order of values)

When adding each new element \(j\): 1. As long as the value of the element at the back of the deque is less than or equal to \(S_j\), remove it from the back (they become useless once \(j\) is added). 2. Add \(j\) to the back. 3. If the index at the front of the deque is before the left end of the window (\(j - K + 1\)), remove it.

Consequently, the front of the deque will always point to the maximum value of the current window.

Deque for Minimums (maintained in monotonically increasing order of values)

By reversing the direction of the inequalities, the front of the deque will similarly point to the minimum value.

For each site, once \(j \geq K-1\) (the window is fully filled), we calculate maximum - minimum and update the maximum value (score) for that site. Finally, we check if the score of each site is at least \(T\) and count them.

Example

For the sequence \(S = [3, 1, 4, 1, 5]\) and \(K = 3\): - Interval \([3, 1, 4]\): max \(4\), min \(1\), difference \(3\) - Interval \([1, 4, 1]\): max \(4\), min \(1\), difference \(3\) - Interval \([4, 1, 5]\): max \(5\), min \(1\), difference \(4\)

The score is \(\max(3,3,4) = 4\). By using a deque, we can find these values with a single scan from left to right.

Complexity

Since each element is pushed to and popped from the deque at most once, the processing time per site is \(O(M)\).

• Time Complexity: \(O(N \times M)\) (since the overall complexity is \(O(NM) \leq 2 \times 10^6\), this is very fast)
• Space Complexity: \(O(M)\) (the sequence and the deques can be reused for each site)

Implementation Details

• Beware of Overflow: The temperature values are in the range \(-10^9 \leq S_{i,j} \leq 10^9\), so the difference between the maximum and minimum values can be up to \(2 \times 10^9\), which is close to the limit of a signed 32-bit int. Thus, the scores, differences, and the threshold \(T\) should be handled using long long (64-bit integer).

• Implementing Deque with an Array: While you can use the standard std::deque, this code optimizes performance by implementing a deque using a vector<int> with head and tail indices, resetting maxHead, maxTail, etc., for each site. Since the maximum number of elements is \(M\), an array size of \(M\) is sufficient.

• Fast I/O: Since \(N \times M\) can be up to \(2 \times 10^6\), the input size is quite large. To speed up, we read the input in bulk using fread and parse integers with a custom parser. Using standard cin without optimization might cause a Time Limit Exceeded (TLE) due to I/O overhead.

• Timing of Window Completion: The window size only reaches \(K\) once \(j \geq K-1\), so we should only update the score from that point onward.

  Source Code

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

int main(){
    int N, M, K;
    long long T;
    
    // fast input
    static char buf[1 << 25];
    int len = fread(buf, 1, sizeof(buf), stdin);
    int pos = 0;
    auto readInt = [&]() -> long long {
        while(pos < len && (buf[pos] < '0' || buf[pos] > '9') && buf[pos] != '-') pos++;
        bool neg = false;
        if(pos < len && buf[pos] == '-'){ neg = true; pos++; }
        long long x = 0;
        while(pos < len && buf[pos] >= '0' && buf[pos] <= '9'){
            x = x * 10 + (buf[pos] - '0');
            pos++;
        }
        return neg ? -x : x;
    };
    
    N = (int)readInt();
    M = (int)readInt();
    K = (int)readInt();
    T = readInt();
    
    vector<long long> S(M);
    // deque storing indices
    vector<int> maxDq(M), minDq(M);
    
    int count = 0;
    for(int i = 0; i < N; i++){
        for(int j = 0; j < M; j++) S[j] = readInt();
        
        long long score = LLONG_MIN;
        int maxHead = 0, maxTail = 0; // [maxHead, maxTail)
        int minHead = 0, minTail = 0;
        
        for(int j = 0; j < M; j++){
            // add j to max deque (decreasing)
            while(maxTail > maxHead && S[maxDq[maxTail-1]] <= S[j]) maxTail--;
            maxDq[maxTail++] = j;
            // add j to min deque (increasing)
            while(minTail > minHead && S[minDq[minTail-1]] >= S[j]) minTail--;
            minDq[minTail++] = j;
            
            // remove out of window from front
            int windowStart = j - K + 1;
            while(maxTail > maxHead && maxDq[maxHead] < windowStart) maxHead++;
            while(minTail > minHead && minDq[minHead] < windowStart) minHead++;
            
            if(j >= K - 1){
                long long diff = S[maxDq[maxHead]] - S[minDq[minHead]];
                if(diff > score) score = diff;
            }
        }
        
        if(score >= T) count++;
    }
    
    printf("%d\n", count);
    return 0;
}

---

This editorial was generated by claude4.8opus-high.