de algorismoKratui++
IMOS Method II : มิติที่สูงกว่า
  • หลังจากที่รู้วิธีการเขียน IMOS ในหนึ่งมิติแล้ว สำหรับมิติที่สูงกว่าล่ะ? มาเริ่มกันด้วยปัญหาจริงดีกว่า

    ปัญหาจาก OTOG.org ข้อ 434 : IMOS - Insert Many Of Sack

     - รับจํานวนเต็ม 2 ตัว แทน Row <= 4,000 และ Col <= 4000
     - ต่อมา รับจํานวนเต็ม 1 ตัว แทน Query <= 1,000,000
     - อีก Query บรรทัดรับ r1, c1, r2, c2, val โดย
      - r1,r2 <= Row
      - c1,c2 <= Col
      - 1 <= val <= 500
    ทุกๆช่อง i,j ที่ r1 <= i <= r2 และ c1 <= j <= c2 ให้เพิ่มค่า val ลงไป

    (ตำแหน่งที่จะใช้ในที่นี้เป็น Half-Open คือ [rn, cn) เพื่อที่จะไม่เป็นการสปอยโจทย์จนเกินไป เนื่องจากโจทย์ถามเป็นช่วง [rn, cn] ฉะนั้นแล้วจงไปประยุกต์เอาเอง



    การแก้ปัญหาสุดบ้านนอกคือไล่บวกมันทุกตัว: ซึ่งมี O(Query x Row x Col)
    1. for (int y = 0; y < Row; y++)
    2. for (int x = 0; x < Col; x++)
    3. arr[y][x] = 0;

    4. for (int i = 0; i < Query; i++)
    5. // Read note 1
    6. for (int y = r1[i]; y < r2[i]; y++)
    7. for (int x = c1[i]; x < c2[i]; x++)
    8. arr[y][x]+=val;
    Note 1 บวกค่า val เพิ่มไปในทุก ๆ ช่องที่อยู่ในช่วงสี่เหลี่ยม [r1c1, r2c2)
    ทีนี้ลองดูโจทย์
    Query x Row x Col = 1,000,000 x 4000 x 4000 = 16,000,000,000,000 (16 ล้านล้าน) คำสั่งเนาะ ๆ เกรดเดอร์ที่ไหนจะคิดให้คุณได้ในหนึ่งวิฯ (แม้คอมพิวเตอร์แรง ๆ ยังทำไม่ได้เลย !)

    การประยุกต์ใช้ IMOS
    จะทำการบวกค่าในมุมซ้ายบนของพื้นที่ที่ต้องการจะเพิ่มค่า (1.) และบวกค่าในตำแหน่งขวาล่างของพื้นที่ (2.) จากนั้นลบค่าเดียวกันออกจากมุมขวาบน (4.) และซ้ายล่าง (3.)

      1. + ค่าที่ตำแหน่ง (r1, c1)
      2. + ค่าที่ตำแหน่ง (r2, c2)
      3. - ค่าที่ตำแหน่ง (r2, c1)
      4. - ค่าที่ตำแหน่ง (r1, c2)
      5. เอา Quick sum เกลี่ย

    วิธีการนี้มี O(Query + (Row x Col))
    ซึ่งจากโจทย์เดียวกัน จะต้องคำนวนเพียง 1,000,000 + 4000 x 4000 = 17,000,000 (17 ล้าน) คำสั่ง
    ซึ่งคอมพิวเตอร์ตาสีตาสาที่ไหนก็คำนวนในเวลา 1 วิฯ ได้สบาย ๆ

    1. for (int y = 0; y < Row; y++)
    2. for (int x = 0; x < Col; x++)
    3. arr[y][x] = 0;

    4. // 1. - 4. (fig. 3)
    5. for (int i = 0; i < N; i++) {
    6. arr[r1[i]][c1[i]]+=val;
    7. arr[r2[i]][c2[i]]+=val;
    8. arr[r1[i]][c2[i]]-=val;
    9. arr[r2[i]][c1[i]]-=val;
    10. }
    11. // Read note 1 (fig. 4, 5)
    12. for (int y = 0; y < Row; y++)
    13. for (int x = 1; x < Col; x++)
    14. arr[y][x] += arr[y][x - 1];

    15. // Read note 2 (fig. 6, 7)
    16. for (int y = 1; y < Row; y++)
    17. for (int x = 0; x < Col; x++)
    18. arr[y][x] += arr[y - 1][x];
    Note 1 เกลี่ยในแนวแกน x (รูป 4, 5)
    Note 2 เกลี่ยในแนวแกน y (รูป 6, 7)

    รูป 3 : ดูสี่เหลี่ยมซ้ายบน
      แถวบนสุด : +1 ที่ช่อง (r1, c1) และ -1 ออกที่ช่อง (r1, c2)
      แถวล่างสุด : -1 ที่ช่อง (r2, c1) และ +1 เข้าที่ช่อง (r2, c2)
    สังเกตุว่าการบวกนี้ไม่รวม r2 และ c2

    รูป 4

    รูป 5
    รูป 6

    รูป 7 : ผล

    อ้างอิงจาก moz.jp/algorithms/imos_method.html
    ได้รับอนุญาติจาก @imos เจ้าของเว็บอ้างอิงเพื่อใช้ในการศึกษา

Views

เข้าสู่ระบบเพื่อแสดงความคิดเห็น

Log in