programming.in.th · ข้อ 2030

พิสัยของลำดับย่อย: เงื่อนไขอยู่ระหว่าง เขียนเป็นผลต่างของสองคำถามด้านเดียว

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

★★★☆☆ two pointersstackcounting อ่าน 12 นาที 9 กันยายน 2026

โจทย์ · นับลำดับย่อยที่พิสัยตกอยู่ในช่วงที่กำหนด

ให้ลำดับจำนวนเต็ม N ตัว พิสัยของลำดับย่อยคือค่ามากสุดลบค่าน้อยสุด ของลำดับย่อยนั้น งานของเราคือนับว่ามีลำดับย่อยที่ต่อเนื่องกันกี่ชุด ที่พิสัยของมันอยู่ระหว่าง p ถึง q

ตัวอย่างในโจทย์ใช้ลำดับ 1, 7, 4, 3, 9, 6, 8 แล้วถามช่วงพิสัย 4 ถึง 6 คำตอบคือ 13 ชุด

อินพุต / ขอบเขต / เอาต์พุต

อินพุต: บรรทัดแรกคือ N, p และ q จากนั้นอีก N บรรทัด บรรทัดละหนึ่งจำนวนคือสมาชิกของลำดับ
ขอบเขต: 1 ≤ N ≤ 1,000,000, 0 ≤ p ≤ q ≤ 10,000,000 และสมาชิกแต่ละตัวอยู่ระหว่าง 0 ถึง 10,000,000 เวลา 0.4 วินาที หน่วยความจำ 64 เมกะไบต์
เอาต์พุต: จำนวนลำดับย่อยที่พิสัยอยู่ในช่วง [p, q]
ให้คะแนน: ชุดทดสอบมูลค่าไม่เกิน 40 คะแนนมี N ไม่เกิน 1,000 และมูลค่าไม่เกิน 70 คะแนนมี N ไม่เกิน 100,000

EXAMPLE
Input	Output
7 4 6 1 7 4 3 9 6 8	13

ใบ้

ที่ N เท่ากับหนึ่งล้าน จำนวนช่วงย่อยทั้งหมดคือราวห้าแสนล้านช่วง แค่ไล่ดูทีละช่วงก็ไม่ไหวแล้ว เราจึงต้องนับเป็นก้อน ไม่ใช่นับทีละอัน

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

ลองเอง · หาช่วงที่ผ่านเงื่อนไขให้ครบ

เริ่มจากชุดเล็กก่อน ให้ชินกับการนับช่วงหนึ่งช่วงว่าพิสัยเท่าไร

กดตัวซ้ายสุดของช่วง แล้วกดตัวขวาสุด ระบบจะบอกว่าช่วงนั้นผ่านเงื่อนไขไหม

หาได้แล้ว 0 ช่วง

ช่วงยาวหนึ่งตัวก็นับ ถ้าขอบล่างของพิสัยเป็นศูนย์ เพราะค่ามากสุดกับน้อยสุดของมันคือตัวเดียวกัน

เล่นไปสักพักจะเริ่มรู้สึกว่า พอตรึงขอบขวาไว้แล้วเลื่อนขอบซ้ายออกไปทางซ้ายเรื่อย ๆ พิสัยจะโตขึ้นอย่างเดียว ไม่มีเล็กลง ความรู้สึกนั้นคือสิ่งที่ทั้งเฉลยยืนอยู่บนมัน

เฉลย ตอนที่ 1 · เงื่อนไขสองด้าน แปลงเป็นสองคำถามด้านเดียว

ที่มาของแนวคิดนี้

ผมเริ่มจากท่ามาตรฐานที่ควรลองก่อนเสมอ คือตรึงขอบขวาแล้วถามว่าขอบซ้ายอยู่ได้ถึงไหน และมันก็สะดุดทันทีตรงเงื่อนไข p เพราะสองด้านนี้ไม่ได้ทำงานทางเดียวกัน การขยายช่วงทำให้พิสัยโตขึ้นอย่างเดียว ดังนั้นเงื่อนไข "พิสัยไม่เกิน q" เป็นจริงบนช่วงที่แคบและพังเมื่อกว้างพอ ซึ่งใช้หน้าต่างเลื่อนได้ตรง ๆ แต่เงื่อนไข "พิสัยอย่างน้อย p" กลับกัน คือเป็นจริงเมื่อกว้างพอ

พอสองด้านสวนทางกัน ช่วงของขอบซ้ายที่ใช้ได้จึงเป็นช่วงตรงกลาง ซึ่งเดินตัวชี้ตัวเดียวไม่พอ ตรงนี้ผมมีสองทางให้เลือก คือเดินตัวชี้สองตัวพร้อมกัน หรือแยกโจทย์ออกเป็นสองโจทย์ แล้วลบกัน ผมเลือกทางหลังเพราะมันทำให้ผมเขียนโค้ดชุดเดียวแล้วเรียกสองครั้ง ซึ่งแปลว่าโอกาสพลาดลดลงครึ่งหนึ่งไปด้วย

บทเรียนที่ยกไปข้ออื่นได้คือ เวลาเจอเงื่อนไขแบบอยู่ระหว่าง ให้ถามทันทีว่าฟังก์ชันที่วัดอยู่มันโตทางเดียวหรือเปล่า ถ้าใช่ ให้เขียนเป็นผลต่างของสองคำถามด้านเดียว ซึ่งมักมีท่ามาตรฐานรออยู่แล้ว

ให้ f(x) คือจำนวนช่วงย่อยที่พิสัยไม่เกิน x เซตของช่วงที่พิสัยไม่เกิน p ลบหนึ่ง เป็นสับเซตของเซตที่พิสัยไม่เกิน q เสมอ คำตอบจึงเท่ากับ f(q) ลบ f(p - 1) ตรง ๆ

หัวใจของทั้งข้อ

// เงื่อนไขสองด้าน แปลงเป็นสองคำถามด้านเดียวที่ลบกันได้
// เพราะเซตของช่วงที่พิสัยไม่เกิน p-1 เป็นสับเซตของช่วงที่พิสัยไม่เกิน q เสมอ
printf("%lld\n", countAtMost(q) - countAtMost(p - 1));

ช่วงย่อยทั้ง 28 ช่วงของลำดับตัวอย่าง จัดกลุ่มตามพิสัยของมัน แถบฟ้าคือช่วงที่พิสัยไม่เกิน 6 ส่วนแถบแดงคือช่วงที่พิสัยไม่เกิน 3 ซึ่งซ้อนอยู่ข้างในทั้งก้อน คำตอบคือส่วนที่เหลือหลังหักออก คือ 25 ลบ 12 เท่ากับ 13

เฉลย ตอนที่ 2 · นับช่วงที่พิสัยไม่เกิน x ด้วยหน้าต่างเลื่อน

ตรึงขอบขวาไว้ที่ r แล้วถามว่าขอบซ้ายเลื่อนไปทางซ้ายได้ไกลสุดแค่ไหน โดยที่พิสัยยังไม่เกิน x เรียกตำแหน่งนั้นว่า l ช่วงที่จบที่ r และใช้ได้ จึงมีทั้งหมด r - l + 1 ช่วงพอดี

สิ่งที่ทำให้เดินตัวชี้ได้คือ l ไม่มีวันถอยกลับ เพราะถ้าหน้าต่างที่จบตรงตำแหน่งก่อนหน้ายังกว้างเกินไป การขยับขอบขวาไปทางขวา มีแต่จะทำให้พิสัยโตขึ้นอีก ตัวชี้สองตัวจึงเดินไปข้างหน้าอย่างเดียว รวมกันไม่เกิน 2N ก้าว

เหลือเรื่องเดียวคือค่ามากสุดกับน้อยสุดของหน้าต่างปัจจุบัน ซึ่งเก็บด้วยคิวสองหัวแบบลดหลั่น อันหนึ่งเก็บดัชนีที่ค่าลดหลั่นลง หัวคิวจึงเป็นค่ามากสุดเสมอ อีกอันเก็บกลับกัน ทุกดัชนีเข้าและออกคิวอย่างละครั้ง ราคาจึงเป็นเส้นตรง

พอขอบซ้ายไม่มีวันถอยกลับ ทั้งอาเรย์จึงถูกเดินแค่สองรอบ ไม่ว่าจะมีช่วงย่อยกี่แสนล้านช่วงก็ตาม

โน้ต · ทำไม f(p - 1) ถึงใช้โค้ดตัวเดียวกันได้

เพราะ f ไม่รู้จักโจทย์เลย มันรับแค่ตัวเลข x ตัวเดียว กรณี p เท่ากับศูนย์จะได้ x เป็นลบหนึ่ง ซึ่งต้องตอบศูนย์ เพราะไม่มีช่วงไหนที่พิสัยติดลบได้ โค้ดจึงกันไว้ด้วยบรรทัดเดียวที่ต้นฟังก์ชัน

เดินหน้าต่างให้ดูหนึ่งรอบ

ขั้น 0

เดินขอบขวาทีละตำแหน่ง ตอนนับช่วงที่พิสัยไม่เกิน 6

การนับ f(6) ของลำดับตัวอย่าง
ขอบขวา	ค่า	ขอบซ้าย	มากสุด	น้อยสุด	นับเพิ่ม	รวมสะสม
1	1	1	1	1	1	1
2	7	1	7	1	2	3
3	4	1	7	1	3	6
4	3	1	7	1	4	10
5	9	2	9	3	4	14
6	6	2	9	3	5	19
7	8	2	9	3	6	25

รอบนี้ได้ f(6) เท่ากับ 25 พอเดินอีกรอบด้วย x เท่ากับ 3 จะได้ 12 คำตอบคือ 25 ลบ 12 เท่ากับ 13 ตรงกับที่โจทย์บอก และตรงกับจำนวนช่วงที่ตัวตรวจไล่เจอจริง คือ 13 ช่วง

โค้ด

ดูโค้ดเต็ม

spread.cpp

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
static char buf[1 << 16]; static size_t bl = 0, bp = 0;
static inline int gc(){ if(bp == bl){ bl = fread(buf, 1, sizeof buf, stdin); bp = 0; if(!bl) return -1; } return buf[bp++]; }
static inline ll readInt(){
    int c = gc(); while(c != -1 && (c < '0' || c > '9') && c != '-') c = gc();
    int sg = 1; if(c == '-'){ sg = -1; c = gc(); }
    ll x = 0; while(c >= '0' && c <= '9'){ x = x * 10 + (c - '0'); c = gc(); }
    return x * sg;
}
int n; vector<int> a; vector<int> qmax, qmin;

// จำนวนช่วงย่อยที่พิสัยไม่เกิน x  หน้าต่างเลื่อนพร้อมคิวสองอันที่เก็บค่าสูงสุดกับต่ำสุด
ll countAtMost(ll x){
    if(x < 0) return 0;
    int hMax = 0, tMax = 0, hMin = 0, tMin = 0, l = 0; ll res = 0;
    for(int r = 0; r < n; r++){
        while(tMax > hMax && a[qmax[tMax-1]] <= a[r]) tMax--;   // คิวค่าสูงสุด ลดหลั่นลง
        qmax[tMax++] = r;
        while(tMin > hMin && a[qmin[tMin-1]] >= a[r]) tMin--;   // คิวค่าต่ำสุด ไล่ขึ้น
        qmin[tMin++] = r;
        while(a[qmax[hMax]] - a[qmin[hMin]] > x){               // กว้างเกินไป ดันขอบซ้าย
            if(qmax[hMax] == l) hMax++;
            if(qmin[hMin] == l) hMin++;
            l++;
        }
        res += r - l + 1;                                       // ช่วงที่จบที่ r และเริ่มได้ตั้งแต่ l
    }
    return res;
}

int main(){
    n = (int)readInt(); ll p = readInt(), q = readInt();
    a.resize(n); for(int i = 0; i < n; i++) a[i] = (int)readInt();
    qmax.resize(n); qmin.resize(n);
    printf("%lld\n", countAtMost(q) - countAtMost(p - 1));
}

ที่ต้องเขียนตัวอ่านเลขเอง เพราะอินพุตมีถึงหนึ่งล้านบรรทัดในลิมิต 0.4 วินาที การอ่านทีละก้อนด้วย fread แล้วแยกตัวเลขเองเร็วกว่าการอ่านทีละตัวมาก

ดูตัวตรวจที่ใช้เทียบ

brute_spread.cpp

// ตัวตรวจ ไล่ทุกช่วง วัดพิสัยตรง ๆ ไม่มีเทคนิคใด ๆ
#include <bits/stdc++.h>
using namespace std;
int main(){
    long long n, p, q; scanf("%lld %lld %lld", &n, &p, &q);
    vector<long long> a(n); for(auto &x : a) scanf("%lld", &x);
    long long c = 0;
    for(int i = 0; i < n; i++){
        long long mx = a[i], mn = a[i];
        for(int j = i; j < n; j++){
            mx = max(mx, a[j]); mn = min(mn, a[j]);
            long long r = mx - mn; if(r >= p && r <= q) c++;
        }
    }
    printf("%lld\n", c);
}

ตัวตรวจไล่ทุกช่วงแล้ววัดพิสัยตรง ๆ ไม่มีเรื่องคิวหรือการลบกันอยู่ในนั้นเลย ผมสุ่มลำดับยาวไม่เกิน 12 ตัว โดยจงใจให้ค่าซ้ำกันเยอะในบางชุด รวม 2,000 เคส แล้วเทียบกัน ตรงกันหมด หน้าเว็บนี้ก็รันด่านตรวจเดียวกันตอนบิลด์ 600 ชุด

เวลาที่วัดได้บนเครื่องผม ลำดับ 1,000,000 ตัวที่ค่ากระจายเต็มสิบล้าน และถามช่วงพิสัยทั้งหมด ใช้เวลา 0.05 วินาที ส่วนชุดที่ค่าซ้ำกันหนา คือค่าอยู่ระหว่าง 0 ถึง 20 ใช้เวลา 0.06 วินาที จากลิมิต 0.4 วินาที

ท่าที่ติดมือกลับไป

ท่าของข้อนี้มีสองชั้น ชั้นแรกคือเปลี่ยนเงื่อนไขอยู่ระหว่าง ให้เป็นผลต่างของสองเงื่อนไขด้านเดียว ซึ่งใช้ได้ทุกครั้งที่ค่าที่วัดโตทางเดียวเมื่อขยายของ ชั้นที่สองคือคิวสองหัวแบบลดหลั่น ที่ตอบค่ามากสุดและน้อยสุดของหน้าต่างในราคาเฉลี่ยคงที่

ทบทวนพื้นฐาน · ทำไมคิวลดหลั่นถึงถูก

ถ้ามีดัชนี i อยู่ก่อน j และ a[i] ไม่มากกว่า a[j] แล้ว i จะไม่มีวันเป็นค่ามากสุดของหน้าต่างไหนอีกเลย เพราะหน้าต่างใดที่มี i อยู่และยังไม่หลุด ก็ต้องมี j อยู่ด้วยเสมอ เราจึงทิ้ง i ได้ทันทีตอนที่ j เข้ามา

เรื่องนี้มีบทปูพื้นเต็ม ๆ อยู่ที่ สองตัวชี้กับหน้าต่างเลื่อน ซึ่งอธิบายทั้งเงื่อนไขที่ใช้ท่านี้ได้และที่ใช้ไม่ได้

บิลค่าใช้จ่าย
ทาง	ขอบเขตที่มันไหว	งานคร่าว ๆ
ไล่ทุกช่วงแล้ววัดพิสัยตรง ๆ	N ไม่เกินราวหนึ่งพัน	1,000,000 ยกกำลังสองหารสอง คือห้าแสนล้าน
สองคำถามด้านเดียว แต่ละคำถามใช้หน้าต่างเลื่อน	N ถึง 1,000,000	ราว 4,000,000 ครั้ง

สองแถวนี้นับจำนวนครั้งที่ต้องแตะสมาชิกหนึ่งตัวเหมือนกัน แถวบนโตตามจำนวนช่วงย่อย ซึ่งเป็นกำลังสองของความยาว ส่วนแถวล่างเดินอาเรย์สี่รอบ คือสองรอบต่อหนึ่งคำถาม และมีสองคำถาม

สรุปบรรทัดเดียว

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

แหล่งที่มา

โจทย์ พิสัยของลำดับย่อย บน programming.in.th ข้อ 2030 programming.in.th/tasks/2030 (สืบค้น 9 กันยายน 2026)
โจทย์โดยอาภาพงศ์ จันทร์ทอง ที่มา TOI.C:05-2009