概要

一列に並んだ \(N\) 本の花から、「品種の多様さ」と「高さのバランス」に関する2つの条件を同時に満たす連続区間 \([l, r]\) の個数を数える問題です。尺取り法（two-pointer）を2回使って効率的に解きます。

考察

重要な気づき：単調性

固定した左端 \(l\) に対して、右端 \(r\) を増やしていくとき：

• 条件1 の \(D \times (r - l + 1)\)：\(D\)（異なる品種数）は非減少、区間長 \((r-l+1)\) は単調増加なので、積全体も非減少
• 条件2 の \(\max B_i - \min B_i\)：区間が広がると最大値は増え最小値は減るので、差は非減少

つまり、各 \(l\) に対して「条件1を満たす最大の \(r\)」と「条件2を満たす最大の \(r\)」がそれぞれ存在し、両方を満たす \(r\) の範囲は \([l, \min(r_1[l], r_2[l])]\) となります。

素朴なアプローチの問題点

全ての区間を調べると \(O(N^2)\) 個あり、各区間で条件判定に \(O(N)\) かかると \(O(N^3)\) で TLE になります。

解決策

単調性を利用して、\(l\) を左から右に動かしたとき、\(r_1[l]\) と \(r_2[l]\) も右方向にしか動かないことを利用し、尺取り法で \(O(N)\) で各 \(r_1[l], r_2[l]\) を求めます。

アルゴリズム

ステップ1：条件2の尺取り法

• 区間の最大値・最小値を効率的に管理するため、単調デック（deque） を2本使います。
  • max_deq：値が単調減少となるようにインデックスを保持（先頭が最大値のインデックス）
  • min_deq：値が単調増加となるようにインデックスを保持（先頭が最小値のインデックス）
• \(l\) を固定して \(r\) を伸ばし、\(\max - \min > M\) になったら停止。そのときの \(r-1\) が \(r_2[l]\) です。

ステップ2：条件1の尺取り法

• 区間内の異なる品種数 \(D\) を管理するため、品種ごとの出現頻度を辞書で管理します。
• \(r\) を伸ばすとき、新しい要素の追加で \(D\) が増えるかを確認し、\(D \times (r - l + 1) > K\) になったら停止。

ステップ3：答えの集計

各 \(l\) に対して： $\(\text{ans} += \min(r_1[l],\, r_2[l]) - l + 1\)$

（ただし \(\min(r_1[l], r_2[l]) \ge l\) の場合のみ加算）

計算量

• 時間計算量: \(O(N)\)
  • 各尺取り法で左端・右端ともに合計 \(O(N)\) 回しか動かないため
• 空間計算量: \(O(N)\)
  • デック、頻度辞書、配列 \(r_1, r_2\) に \(O(N)\)

実装のポイント

• デックの管理：\(l\) を右に進めるとき、デックの先頭が \(l\) と等しければ除去する必要があります。

• right の初期化：\(l\) が \(right\) を追い越した場合（\(right < l\) になった場合）、データ構造をリセットして \(right = l - 1\) から再スタートします。

• オーバーフロー注意：\(K\) が最大 \(10^{18}\) なので、\(D \times (r-l+1)\) の計算で大きな値を扱います。Python では整数オーバーフローがないため問題ありませんが、C++ などでは注意が必要です。

• 2つの尺取り法を独立に行う：条件1と条件2は独立に最大 \(r\) を求められるため、別々に処理してから最後に \(\min\) を取る設計がシンプルです。

  ソースコード

import sys
from collections import defaultdict

def solve():
    input_data = sys.stdin.buffer.read().split()
    idx = 0
    N = int(input_data[idx]); idx += 1
    K = int(input_data[idx]); idx += 1
    M = int(input_data[idx]); idx += 1
    A = [int(input_data[idx + i]) for i in range(N)]; idx += N
    B = [int(input_data[idx + i]) for i in range(N)]; idx += N

    # For each l, we need to find the maximum r such that both conditions hold.
    # Condition 1: D * (r - l + 1) <= K where D = number of distinct values in A[l..r]
    # Condition 2: max(B[l..r]) - min(B[l..r]) <= M
    
    # Neither condition is simply monotone in a way that allows a single two-pointer,
    # because condition 1 involves D * length which can increase non-monotonically
    # (D increases at certain points, length increases always).
    
    # However, for a fixed l, as r increases:
    # - D is non-decreasing
    # - (r - l + 1) is strictly increasing
    # - max - min is non-decreasing
    # So D * (r-l+1) is non-decreasing, and max-min is non-decreasing.
    # Both conditions define a prefix of valid r values for each l.
    # So the set of valid r for each l is [l, min(r1, r2)] where r1 is max r for cond1, r2 for cond2.
    
    # Condition 2 can be handled with two-pointer + deques for min/max.
    # Condition 1: D * (r - l + 1) <= K. As r increases, D*(r-l+1) is non-decreasing,
    # so we can use two-pointer for this too.
    
    # Two separate two-pointers, then for each l, answer += min(r1_limit, r2_limit) - l + 1
    
    # But we need to be careful: when l moves right, the right pointer for each condition
    # can only move right or stay (standard two-pointer property).
    
    # Let's compute for each l, the maximum r satisfying condition 1 (r1[l])
    # and condition 2 (r2[l]), then answer = sum of max(0, min(r1[l], r2[l]) - l + 1).
    
    # Condition 2: two-pointer with deques
    from collections import deque
    
    r2 = [0] * N  # max r (inclusive) for condition 2
    max_deq = deque()  # decreasing deque of indices
    min_deq = deque()  # increasing deque of indices
    right = -1
    for l in range(N):
        if right < l:
            right = l - 1
            max_deq.clear()
            min_deq.clear()
        while right + 1 < N:
            nr = right + 1
            # Check if adding nr keeps condition 2
            new_max = B[nr] if not max_deq else max(B[max_deq[0]], B[nr])
            new_min = B[nr] if not min_deq else min(B[min_deq[0]], B[nr])
            if new_max - new_min <= M:
                while max_deq and B[max_deq[-1]] <= B[nr]:
                    max_deq.pop()
                max_deq.append(nr)
                while min_deq and B[min_deq[-1]] >= B[nr]:
                    min_deq.pop()
                min_deq.append(nr)
                right += 1
            else:
                break
        r2[l] = right
        # Remove l from deques
        if max_deq and max_deq[0] == l:
            max_deq.popleft()
        if min_deq and min_deq[0] == l:
            min_deq.popleft()
    
    # Condition 1: two-pointer with frequency count for distinct
    r1 = [0] * N
    freq = defaultdict(int)
    distinct = 0
    right = -1
    for l in range(N):
        if right < l:
            right = l - 1
            freq.clear()
            distinct = 0
        while right + 1 < N:
            nr = right + 1
            new_distinct = distinct + (1 if freq[A[nr]] == 0 else 0)
            length = nr - l + 1
            if new_distinct * length <= K:
                if freq[A[nr]] == 0:
                    distinct += 1
                freq[A[nr]] += 1
                right += 1
            else:
                break
        r1[l] = right
        # Remove l
        freq[A[l]] -= 1
        if freq[A[l]] == 0:
            distinct -= 1
    
    ans = 0
    for l in range(N):
        valid_r = min(r1[l], r2[l])
        if valid_r >= l:
            ans += valid_r - l + 1
    
    print(ans)

solve()

---

この解説は claude4.6opus-thinking によって生成されました。