ในปัญหานี้ เราได้รับตัวเลข N ซึ่งเป็นขนาดของอาร์เรย์ที่ประกอบด้วยศูนย์ทั้งหมดและแบบสอบถาม Q แต่ละประเภทต่อไปนี้ -
อัปเดต (s, e, val ) -> แบบสอบถามนี้จะอัปเดตองค์ประกอบทั้งหมดจาก s เป็น e (รวมทั้งสอง) เป็น val
งานของเราคือ ค้นหาจำนวนตัวเลขที่แตกต่างกันในอาร์เรย์หลังจากใช้การดำเนินการที่กำหนด 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}
แบบสอบถาม 1 - อัปเดต (1, 4, 3) -> arr[] ={0, 3, 3, 3, 3, 0}
แบบสอบถาม 2 - อัปเดต (0, 2, 4) -> arr[] ={4, 4, 4, 3, 3, 0}
แนวทางการแก้ปัญหา
วิธีแก้ปัญหาอย่างง่ายคือดำเนินการค้นหาแต่ละรายการในอาร์เรย์ แล้วนับจำนวนค่าที่ไม่ซ้ำในอาร์เรย์และใช้อาร์เรย์พิเศษ แล้วคืนค่าจำนวนอาร์เรย์ที่ไม่ซ้ำ
วิธีแก้ปัญหานี้ดีแต่วิธีแก้ปัญหาที่มีประสิทธิภาพมากกว่าคือการใช้แนวคิดของ การแพร่กระจายแบบขี้เกียจ เพื่อเพิ่มประสิทธิภาพการทำงานของช่วงที่ดำเนินการในแบบสอบถาม เราจะใช้การเรียกแบบ lazy propagation เพื่อดำเนินการค้นหาเพื่อค้นหาจำนวนตัวเลขที่ไม่ซ้ำในอาร์เรย์ สำหรับสิ่งนี้ เราจะใช้แผนผังเซ็กเมนต์และอัปเดตโหนดเมื่อดำเนินการและเริ่มต้นทรีด้วยค่า 0 ที่อัปเดตในการดำเนินการจะส่งกลับค่าที่ต้องการ นี่คือโปรแกรมที่จะอธิบายวิธีแก้ปัญหาให้ดียิ่งขึ้น
ตัวอย่าง
โปรแกรมเพื่อแสดงการทำงานของโซลูชันของเรา
#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 or 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
