この問題は尺取法により解くことができます。

2つの条件について、次の問題をそれぞれ独立に考えます。

• 問題★： 各 \(r=1,\dots,N\) に対して、区間 \([l,r]\) が条件を満たすような最小の \(l\) を求めよ

これは後述する尺取法により求めることができます。条件1,2それぞれについての答えを \(l_{1.r},l_{2,r}\) とすると、条件1,2を共に満たす区間の個数は \(\sum_r \left(r-\max(l_{1,r},l_{2,r})+1\right)\) と求めることができます。

尺取法

尺取法とは、以下のようなアルゴリズムです。 区間に対する条件であって、単調性を持つものが与えられたとき、問題★を解くことができます。

素朴な擬似コード

l = 1
for r in 1..N:
  while not is_ok(l, r):
    l += 1
  // [l, r] に関する処理

この is_ok の判定を高速に行うため、区間に関する情報の差分更新も同時に行います

擬似コード

l = 1
status = 空の区間に関する情報
for r in 1..N:
  status.add(a[r])  // a[r] の追加
  while not is_ok(status):
    status.remove(a[l])  // a[l] の削除
    l +=1
  // [l, r] に関する処理

このアルゴリズムでは区間への要素の追加・削除および条件を満たすかどうかの判定をそれぞれ\(O(N)\) 回行うため、これらが高速に行える場合には尺取法全体も高速に動作します。

今回の問題

条件1

区間の状態として、値の種類数と、どの値が何個あるかの(連想)配列を持ちます。 要素の追加・削除を行うときは、まず個数の配列を更新し、それにより種類数の変更があるかどうかを判断します。

条件2

スライド最小値・最大値問題なので、deque を用いることで適切に処理することができます。

実装例 (C++)

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

int main(){
  int n, m;
  long long k;
  cin >> n >> k >> m;
  vector<int> a(n), b(n);
  for(int i=0; i<n; i++) cin >> a[i];
  for(int i=0; i<n; i++) cin >> b[i];
  
  long long ans = 0;
  int al = 0, bl = 0;
  int num_kind = 0;
  vector<int> count(n+1);
  deque<array<int,2>> mq, Mq;
  
  for(int r=0; r<n; r++){
    // Aの処理
    count[a[r]]++;
    if(count[a[r]] == 1){
      num_kind++;
    }
    while((long long)num_kind * (r-al+1) > k){
      count[a[al]]--;
      if(count[a[al]] == 0){
        num_kind--;
      }
      al++;
    }
    // Bの処理
    while(Mq.size() > 0 && Mq.back()[0] <= b[r]){
      Mq.pop_back();
    }
    Mq.push_back({b[r], r});
    while(mq.size() > 0 && mq.back()[0] >= b[r]){
      mq.pop_back();
    }
    mq.push_back({b[r], r});
    while(Mq[0][0] - mq[0][0] > m){
      if(Mq[0][1] == bl){
        Mq.pop_front();
      }
      if(mq[0][1] == bl){
        mq.pop_front();
      }
      bl++;
    }
    ans += r - max(al, bl) + 1;
  }
  cout << ans << endl;
}

実装例 (Python)

from collections import deque
N, K, M = map(int, input().split())
A = list(map(int, input().split()))
B = list(map(int, input().split()))

ans = 0
al = 0
bl = 0
num_kind = 0
count = [0] * (N+1)
mq = deque()
Mq = deque()
for r in range(N):
  # Aの処理
  count[A[r]] += 1
  if count[A[r]] == 1:
    num_kind += 1
  while num_kind * (r-al+1) > K:
    count[A[al]] -= 1
    if count[A[al]] == 0:
      num_kind -= 1
    al += 1
  # Bの処理
  while len(Mq) > 0 and Mq[-1][0] <= B[r]:
    Mq.pop()
  Mq.append((B[r], r))
  while len(mq) > 0 and mq[-1][0] >= B[r]:
    mq.pop()
  mq.append((B[r], r))
  while Mq[0][0] - mq[0][0] > M:
    if Mq[0][1] == bl:
      Mq.popleft()
    if mq[0][1] == bl:
      mq.popleft()
    bl += 1
  ans += r - max(al, bl) + 1

print(ans)