ในปัญหานี้ เราได้รับจำนวน N ซึ่งเป็นขนาดของอาร์เรย์ที่ประกอบด้วยแต่ศูนย์ และ Q queries แต่ละอันมีรูปแบบดังนี้:
update(s, e, val) → query นี้จะอัปเดตสมาชิกทั้งหมดจาก s ถึง e (รวมทั้งสองข้าง) ให้เป็นค่า val
งานของเราคือ การหาจำนวนตัวเลขที่ต่างกันในอาร์เรย์หลังจากทำ operation q ครั้ง
ตัวอย่างเพื่อความเข้าใจ
Input : N = 6, Q = 2 Q1 = update(1, 4, 3) Q2 = update(0, 2, 4) Output : 2
คำอธิบาย
อาร์เรย์เริ่มต้น: arr[] = {0, 0, 0, 0, 0, 0}
Query 1 − update(1, 4, 3) → arr[] = {0, 3, 3, 3, 3, 0}
Query 2 − update(0, 2, 4) → arr[] = {4, 4, 4, 3, 3, 0}
แนวทางแก้ปัญหา
วิธีง่ายคือทำ query ทีละอันบนอาร์เรย์ แล้วนับค่าที่ไม่ซ้ำกัน แต่วิธีนี้ช้า
วิธีที่มีประสิทธิภาพกว่า: ใช้ Lazy Propagation
บน Segment Tree เพื่อเพิ่มประสิทธิภาพการทำ range update เราจะใช้ lazy propagation เพื่ออัปเดตโหนดเมื่อมี operation แล้ว query เพื่อหาจำนวนค่าที่ไม่ซ้ำกันตัวอย่างโค้ด
#include <bits/stdc++.h>
using namespace std;
#define N 100005
int lazyST[4 * N];
set<int> diffNo;
void update(int s, int e, int val, int idx, int l, int r) {
if (s >= r || l >= e)
return;
if (s <= l && r <= e) {
lazyST[idx] = val;
return;
}
int mid = (l + r) / 2;
if (lazyST[idx])
lazyST[2 * idx] = lazyST[2 * idx + 1] = lazyST[idx];
lazyST[idx] = 0;
update(s, e, val, 2 * idx, l, mid);
update(s, e, val, 2 * idx + 1, mid, r);
}
void query(int idx, int l, int r) {
if (lazyST[idx]) {
diffNo.insert(lazyST[idx]);
return;
}
if (r - l < 2)
return;
int mid = (l + r) / 2;
query(2 * idx, l, mid);
query(2 * idx + 1, mid, r);
}
int main() {
int n = 6, q = 3;
update(1, 3, 5, 1, 0, n);
update(4, 5, 1, 1, 0, n);
update(0, 2, 9, 1, 0, n);
query(1, 0, n);
cout << "The number of different numbers in the array after operation is " << diffNo.size();
return 0;
}
ผลลัพธ์
The number of different numbers in the array after operation is 3
