โจทย์ข้อนี้เป็นแนว Dynamic Programming

เราจะนิยามให้ $Cannon(i)$ คือจำนวนปืนใหญ่ตั้งแต่ช่องที่ $1$ ถึงช่องที่ $i$

สังเกตว่าจำนวนปืนใหญ่ตั้งแต่ช่องที่ $1$ ถึง $i$ เท่ากับจำนวนปืนใหญ่ตั้งแต่ช่องที่ $1$ ถึง $i - 1$ บวกด้วยปืนใหญ่ในช่องที่ $i$ หรือสามารถเขียนได้ว่า $Cannon(i) = Cannon(i - 1) + val_{i}$ ซึ่ง $val_{i}$ จะเท่ากับ 0 ถ้าช่องที่ $i$ ไม่มีปืนใหญ่ และเท่ากับ 1 ถ้าช่องที่ $i$ มีปืนใหญ่

ถ้าตำแหน่งจัดวางจุดลำเลียงกระสุนอยู่ที่ $m$ และความยาวครึ่งหนึ่งของรางลำเลียงเท่ากับ $L$ แปลว่ารางลำเลียงกระสุนจะอยู่ตั้งแต่ $m - L$ ถึง $m + L$

เราสามารถคำนวนจำนวนปืนใหญ่ตั้งแต่ $m - L$ ถึง $m + L$ ได้จาก จำนวนปืนใหญ่ตั้งแต่ $1$ ถึง $m + L$ ลบด้วยจำนวนปืนใหญ่ตั้งแต่ $1$ ถึง $m - L - 1$ หรือก็คือ $Cannon(m + L) - Cannon(m - L - 1)$

ปัญหาของข้อนี้

เนื่องจากจุดลำเลียงกระสุนอาจมีมากกว่า $1$ จุดได้ แสดงว่าอาจมีรางที่ทับซ้อนกันได้

สมมติให้รางที่ $i$ อยู่ที่ $[l_{i}, r_{i}]$ และรางที่ $j$ อยู่ที่ $[l_{j}, r_{j}]$ โดยโจทย์รับประกันว่าถ้า $i < j$ แล้ว $l_{i} \leq l_{j}$

เราจะสามารถแยกได้ 2 กรณี

กรณีที่ 1 รางที่ $i$ และ $j$ มีช่วงที่ทับกัน

กรณีนี้จะเกิดถ้า $r_{i} \geq l_{j}$ กรณีนี้จะเห็นว่าเราจะนับปืนใหญ่ในช่วงที่ซ้ำกัน 2 ครั้ง ซึ่งเราจะต้องหาทางในการคำนวนจำนวนปืนใหญ่ที่จะอธิบายหลังจากพูดถึงกรณีที่ 2

กรณีที่ 2 รางที่ $i$ และ $j$ ไม่มีช่วงที่ทับกัน

กรณีนี้จะเกิดถ้า $r_{i} < l_{j}$ ตรงนี้สามารถคำนวนจำนวนปืนใหญ่โดยวิธีข้างต้นได้เลย

การแก้ปัญหากรณีที่ 1

หลักการแก้ปัญหาคือ ถ้ารางมีที่ส่วนทับกัน เราจะรวมให้เป็นรางเดียว เช่น รางที่ 1 $[0 , 10]$ , รางที่ 2 $[3 , 13]$ , รางที่ 3 $[5 , 15]$ เวลาเราคำนวนจำนวนปืนใหญ่จะคำนวนเป็นรางใหญ่ $[0 , 15]$ เลย

ดังนั้นเราจะเริ่มพิจารณาตั้งแต่รางที่ $1$ ถึงช่วงที่ $M$ โดยที่เราจะสมมติให้รางที่ $1$ เป็นรางหลัก แล้วเมื่อเราพิจารณารางถัดไป ก็พิจารณาว่ามีส่วนทับกับรางหลักหรือไม่ ถ้ามีให้รวมเข้ากับรางหลักแล้วเลื่อนไปพิจารณารางถัดไป ถ้าไม่ทับกันให้คำนวนจำนวนปืนใหญ่ของรางหลักโดยวิธีที่ได้กล่าวไปข้างต้น แล้วให้รางนี้เป็นรางหลัก

ยกตัวอย่าง

ตำแหน่งจุดลำเลียงกระสุนอยู่ที่ $199 , 1000 , 1100 , 1500$ และความยาวครึ่งรางเท่ากับ $100$

เราจะได้ช่วงของรางลำเลียงคือ $[99 , 299] , [900 , 1100] , [1000 , 1200] , [1400 , 1600]$

1. เริ่มจากให้รางที่ $1$ $([99 , 299])$ เป็นรางหลัก
2. พิจารณารางที่ $2$ $([900 , 1100])$ จะเห็นว่าไม่มีช่วงที่ทับกับรางหลัก $([99 , 299])$ ดังนั้นเราจะคำนวนจำนวนปืนใหญ่ของรางหลัก $[99 , 299]$ แล้วให้ $[900 , 1100]$ เป็นรางหลัก
3. พิจารณารางที่ $3$ $([1000 , 1200])$ จะเห็นว่ามีช่วงที่ทับกับรางหลัก $([900 , 1100])$ เราก็จะเอารางที่ $3$ รวมกับรางหลักกลายเป็น $[900 , 1200]$
4. พิจารณารางที่ $4$ $([1400 , 1600])$ จะเห็นว่าไม่มีช่วงที่ทับกับรางหลัก $([900 , 1200])$ ดังนั้นเราจะคำนวนจำนวนปืนใหญ่ของรางหลัก $([900 , 1200])$ แล้วให้ $([1400 , 1600])$ เป็นช่วงหลัก
5. คำนวนจำนวนปืนใหญ่ของรางหลักสุดท้าย $([1400 , 1600])$

โค้ดตัวอย่างในภาษา C++

#include <bits/stdc++.h>

using namespace std;
const int MXN = 1e7 + 1;

int cannon[MXN];

int main() {
  int n, m, k, l;
  scanf("%d %d %d %d", &n, &m, &k, &l);
  for (int i = 0; i < n; i++) {
    int x;
    scanf("%d", &x);
    x++; //บวกเพื่อป้องกันกรณีคิดตั้งแต่ช่องที่ 0
    cannon[x]++;
  }
  for (int i = 1; i < MXN; i++) {
    cannon[i] += cannon[i - 1];
  }
  for (int i = 0; i < k; i++) {
    int now_low = -1, now_up = -1, ans = 0;
    for (int j = 0; j < m; j++) {
      int now, lower, upper;
      scanf("%d", &now);
      now++; //บวกเพื่อป้องกันกรณีที่คิดตั้งแต่ช่องที่ 0
      lower = max(1, now - l);
      upper = min(MXN - 1, now + l);
      if (now_low == -1) {
        now_low = lower;
        now_up = upper;
      } else if (now_up >= lower) {
        now_up = upper;
      } else {
        ans += cannon[now_up] - cannon[now_low - 1];
        now_low = lower;
        now_up = upper;
      }
    }
    ans += cannon[now_up] - cannon[now_low - 1];
    printf("%d\n", ans);
  }
}

ข้อสังเกต: วิธีนี้เราต้องประกาศ Array INT32 จำนวน $10^{7}$ ช่องจะใช้ Memory ประมาณ $4 * 10^{7}$ Bytes = $40$ MB

Challenge: ลองคิดวิธีที่สามารถลดการใช้ Memory ลงได้

Time Complexity $\mathcal{O}(N_{max} + KM)$