ข้อนี้ให้ Array $a_1, a_2, \dots, a_N$ $(N \leq 1000000)$ และให้หาจำนวน Subarray ที่มีพิสัย (ค่ามากสุด - ค่าต่ำสุด) อยู่ในช่วง $[p,q]$

แนวคิด

ข้อนี้เป็นโจทย์ Sliding Window

อย่างแรกสังเกตว่าเราสามารถคำนวณจำนวนลำดับย่อยที่มีพิสัยในช่วง $[p,q]$ เป็น (จำนวนลำดับย่อยที่มีพิสัยไม่เกิน $q$) - (จำนวนลำดับย่อยที่มีพิสัยไม่เกิน $p-1$) ดังนั้นสำหรับข้อนี้เราจะพิจารณาการหาจำนวนลำดับย่อยที่มีพิสัยไม่เกิน $q$

ในจำนวนลำดับย่อยที่มีพิสัยไม่เกิน $q$ เราสามารถพิจารณาจำนวนลำดับย่อยที่เข้าข่ายที่จบที่แต่ละ $a_i$ หากนำจำนวนนี้มาบวกกันสำหรับทุก $a_i$ จะได้คำตอบที่ต้องการ

สังเกตว่าสำหรับ $m <n$ ถ้า Subarray $a_m, a_{m+1}, \dots, a_i$ มีพิสัยไม่เกิน $q$ จะได้ว่า $a_n, a_{n+1}, \dots, a_i$ มีพิสัยไม่เกิน $q$ เช่นกัน (เพราะค่ามากสุดจะไม่เกินและค่าต่ำสุดจะไม่น้อยกว่าของ Subarray ที่เริ่มที่ $m$) ดังนั้นสำหรับแต่ละ $i$ เราเพียวต้องหาค่า $m_i$ ที่เป็นค่าที่ต่ำสุดที่ทำให้ $a_{m_i}, \dots, a_i$ มีพิสัยไม่เกิน $q$ กล่าวอีกแบบคือ $\max(a_{m_i}, \dots, a_i) - \min(a_{m_i}, \dots, a_i) \leq q$

สังเกตได้อีกว่าสำหรับ $i<j$ จะได้ว่า $m_i \leq m_j$ ทั้งนี้เพราะถ้า $a_m, a_{m+1}, \dots, a_j$ มีพิสัยไม่เกิน $q$ $a_m, a_{m+1}, \dots, a_i$ ซึ่งเป็น Subarray จะต้องมีพิสัยในช่วงนั้นเช่นกัน

แนวคิดหลักของข้อนี้คือเราสามารถใช้วิธี Sliding Window ในการหาแต่ละ $m_i$ โดยจะใช้ Sliding Window สำหรับค่า max หนึ่งอันและ Sliding Window สำหรับ min อีกอัน (ผู้ที่ไม่คุ้นกับ Sliding Window สามารถอ่านได้จาก https://programming.in.th/tasks/1157/solution) โดย Sliding Window จะสามารถช่วยเราหาค่า max และ min ใน Window ที่เลื่อนไปทางขวาเรื่อยๆ ได้ในเวลา Amortized $\mathcal{O}(N)$ สำหรับทั้ง $N$ ช่องใน Array

เราจะ Initialize $l$ ซึ่งแทนจะ $m_i$ ในแต่ละขั้นเป็น 0 จากนั้นสำหรับแต่ละ $i=1$ ถึง $i=N$ ในแต่ละขั้นจะเริ่มจากการ push ดัชนี $i$ เข้าไปใน Window ทั้งสอง เพิ่ม $l$ และ pop ดัชนีใน Sliding Window ที่อยู่ก่อน $l$ จน $\max(a_{l}, \dots, a_i) - \min(a_{l}, \dots, a_i) \leq q$ เมื่อได้ $m_i=l$ ที่ถูกต้องแล้วจะได้ว่าจำนวน Subarray ที่มีพิสัยไม่เกิน $q$ ที่จบที่ $a_i$ คือ $i-l+1$

เนื่องจากการ Iterate ทุกค่าและใช้ Sliding Window ทั้งสองจะใช้เวลา $\mathcal{O}(N)$ ข้อนี้จึงใช้เวลาทั้งหมด $\mathcal{O}(N)$

ตัวอย่างโค้ด

long long range_leq_q(int q, const vector<int> &a) {
  deque<int> d_max;
  deque<int> d_min;

  long long res = 0;
  long long l = 0;
  for (int i = 0; i < a.size(); i++) {
    while (d_max.size() > 0 && a[d_max.back()] <= a[i])
      d_max.pop_back();
    d_max.push_back(i);

    while (d_min.size() > 0 && a[d_min.back()] >= a[i])
      d_min.pop_back();
    d_min.push_back(i);

    while (l <= i && a[d_max[0]] - a[d_min[0]] > q) {
      l++;

      while (d_max.size() > 0 && d_max[0] < l)
        d_max.pop_front();

      while (d_min.size() > 0 && d_min[0] < l)
        d_min.pop_front();
    }
    res += (i - l + 1);
  }
  return res;
}

นี่คือโค้ดตัวอย่างสำหรับการหาจำนวน Subarray ที่มีพิสัยไม่เกิน $q$

เราจะเก็บ Sliding Window สองอันคือ d_min กับ d_max และเก็บค่า $l$ ที่อธิบายไดว้

ในแต่ละขั้นจะ push $i$ เข้า Sliding Window ทั้งสองโดยเอาข้อมูลที่สำคัญแล้วออก (ต่ำกว่าค่าปัจจุบันสำหรับ d_max หรือ สูงกว่าค่าปัจจุบันสำหรับ d_min)

จากนั้นจะเพิ่มค่า $l$ และ pop ค่าที่อยู่ก่อน $l$ ในแต่ละ Window จนพิสัยไม่เกิน $q$