คำถามแบบสอบถามช่วง CSES: แบบสอบถามเงินเดือน
ฉันกำลังพยายามแก้ปัญหานี้: https://cses.fi/problemset/task/1144/
ด้วยอาร์เรย์ของ200000
องค์ประกอบสูงสุดงานของฉันคือการประมวลผลการ200000
สืบค้นซึ่งขอให้ฉันอัปเดตค่าเดียวภายในอาร์เรย์หรือขอให้ฉันหาจำนวนองค์ประกอบระหว่าง a และ b ที่อยู่ในช่วงที่กำหนด (สำหรับ ตัวอย่างเช่นแบบสอบถามจะถามว่ามีกี่องค์ประกอบจากดัชนี1
ที่5
อยู่ในช่วง[2, 3]
)
แนวคิดปัจจุบันของฉันคือการใช้การบีบอัดดัชนีกับค่าในอาร์เรย์ที่กำหนดก่อน (เนื่องจากค่าอาจสูงถึง10^9
ดังนั้นการเก็บอาร์เรย์ที่เกิดขึ้นอย่างง่ายจะเกินขีด จำกัด ของพื้นที่จัดเก็บ) จากนั้นเก็บอาร์เรย์อื่นที่มีจำนวนครั้งที่เกิดขึ้นของการบีบอัด จำนวน. จากนั้นการประมวลผลและการอัปเดตแบบสอบถามสามารถทำได้โดยใช้โครงสร้างส่วนผลรวม
อย่างไรก็ตามฉันพบปัญหาขณะพยายามใช้แนวทางนี้ ฉันรู้ว่าการอัปเดตค่าอาร์เรย์เดียวจะบังคับให้ฉันเปลี่ยนอาร์เรย์ที่บีบอัด
ตัวอย่างเช่นเมื่อได้รับอาร์เรย์[1, 5, 3, 3, 2]
ฉันจะกำหนดฟังก์ชันการบีบอัดC
เช่นนั้น
C[1] = 0;
C[2] = 1;
C[3] = 2;
C[5] = 3;
จากนั้นอาร์เรย์ที่เกิดขึ้นจะเป็น[1, 1, 2, 1]
และการประมวลผลแบบสอบถามผลรวมจะมีประสิทธิภาพ อย่างไรก็ตามหากฉันได้รับคำสั่งให้อัปเดตค่าให้พูดว่าเปลี่ยนองค์ประกอบที่สามเป็นสิ่ง4
นั้นจะทำให้ทุกอย่างไม่สมดุล ฟังก์ชันการบีบอัดจะต้องเปลี่ยนเป็น
C[1] = 0;
C[2] = 1;
C[3] = 2;
C[4] = 3;
C[5] = 4;
ซึ่งจะบังคับให้ฉันสร้างอาร์เรย์เหตุการณ์ของฉันขึ้นใหม่ส่งผลให้O(N)
เวลาอัปเดต
เนื่องจากN
อาจเป็นไป200000
ได้แนวทางปัจจุบันของฉันจะไม่ทำงานได้อย่างมีประสิทธิภาพเพียงพอที่จะแก้ปัญหาแม้ว่าฉันคิดว่าฉันมีความคิดที่ถูกต้องในการบีบอัดดัชนี ใครช่วยชี้ทางที่ถูกต้องด้วยวิธีการของฉันได้ไหม
คำตอบ
คุณมีความคิดที่ถูกต้องในการใช้การบีบอัดดัชนี - ความคิดที่ดี! ตามที่N
มีอยู่เท่านั้นการ200000
เก็บอาร์เรย์เหตุการณ์ส่วนใหญ่จะต้องใช้200000
องค์ประกอบสำหรับค่าเริ่มต้นของอาร์เรย์ที่กำหนดแทนที่จะเป็น10^9
ดัชนีอาร์เรย์
ตามตัวคุณเองปัญหาที่คุณเผชิญคือเมื่อคุณพบค่าใหม่ในระหว่างการประมวลผลคำค้นหา คุณถูก; สิ่งนี้จะทำให้อาร์เรย์ของเหตุการณ์ไม่สมดุลและทำให้การอัปเดตต้องทำงานO(N)
ทันเวลา วิธีแก้ปัญหานี้เป็นเพียงการปรับเปลี่ยนวิธีการปัจจุบันของคุณเล็กน้อย
เพื่อแก้ปัญหาการพบค่าใหม่เราสามารถตรวจสอบให้แน่ใจว่าเราจะไม่พบค่าใหม่ใด ๆ เราสามารถทำได้โดยการอ่านในแบบสอบถามทั้งหมดก่อนที่จะสร้างต้นไม้ส่วนผลรวม ซึ่งจะส่งผลให้มีN + 2*Q
ค่าที่ไม่ซ้ำกันสูงสุดหรือ600000
ในกรณีที่แย่ที่สุดซึ่งไกลพอที่จะสร้างอาร์เรย์เหตุการณ์ที่มีขีด จำกัด พื้นที่เก็บข้อมูล 512MB ของปัญหา หลังจากนั้นต้นไม้ส่วนผลรวมจะสามารถตอบคำถามเหล่านี้ได้อย่างมีประสิทธิภาพ
ดังนั้นในท้ายที่สุดกลยุทธ์ในการแก้ปัญหานี้คือการป้อนตัวเลขที่ไม่ซ้ำกันทุกตัวจากนั้นสร้างฟังก์ชันการบีบอัดดัชนีจากนั้นใช้โครงสร้างส่วนผลรวมเพื่อประมวลผลการสืบค้นผลรวมอย่างมีประสิทธิภาพ
ในอนาคตจำได้ว่าในทุกประเภทของคำถามเหล่านี้แบบสอบถามตอบมันอาจจะเป็นประโยชน์ในการอ่านในทุกการป้อนข้อมูลก่อน precomputation ขอให้โชคดีกับโปรแกรมของคุณ
ขั้นแรกให้พิจารณาความไร้เดียงสา: สำหรับการอัปเดตแต่ละครั้งให้อัปเดตอาร์เรย์ สำหรับแต่ละคำถามให้สแกนอาร์เรย์ทั้งหมดและรวบรวมคำตอบของคุณ ความซับซ้อนของโซลูชันนี้มีO(n)
การอัปเดตO(n)
แบบสอบถาม ไม่ดี.
เราสามารถหาวิธีแก้ปัญหาอื่นที่มีความซับซ้อนของเวลาที่แย่ลงได้ แต่มันให้คำใบ้ว่าผลลัพธ์สุดท้ายของเราคืออะไร รักษาอาร์เรย์ต้นทางตลอดเวลา แต่ยังเก็บแผนที่แฮชของค่า -> ความถี่ จากนั้นเมื่อคุณอัปเดตให้ลดความถี่ที่ค่าเดิมและเพิ่มขึ้นที่ค่าใหม่ ตอนนี้สำหรับข้อความค้นหาให้วนซ้ำค่าทั้งหมดของช่วงการสืบค้นนั้นและรวมเป็นคำตอบของคุณ สิ่งนี้ส่งผลให้เกิดการO(1)
อัปเดตและการO(r-l)
ค้นหาดังนั้นเราจึงมีการอัปเดตที่ยอดเยี่ยม แต่มีคำถามที่น่ากลัว อย่างไรก็ตามผลนี้จะดีขึ้นเมื่อถ้าเราสามารถเพียงแค่เพิ่มความเร็วในคำสั่งเหล่านั้น! ใส่Segment ต้นไม้
ตามเนื้อผ้าคุณจะต้องสร้างต้นไม้ส่วนลงไปจนถึงใบไม้เมื่อสร้างขึ้น อย่างไรก็ตามเราเรียกได้ว่าเป็นเหมือนต้นไม้เซกเมนต์ที่มีระยะ0-10^9
ดังนั้นจึงไม่มีทางที่เราจะสร้างความทรงจำได้มากขนาดนั้น (และเราจะหมดเวลาในการทำเช่นนั้น) อย่างไรก็ตามจะเกิดอะไรขึ้นถ้าเราสร้างต้นไม้เซกเมนต์ แต่สำหรับทุกโหนดลูกของมันจะเป็นนัยถ้าไม่เคยใช้ นั่นคือไม่ได้สร้างโหนดลูกถ้าหากไม่มีองค์ประกอบในพวกเขาโครงสร้างนี้ได้รับการตั้งชื่อตามความเหมาะสมซึ่งเป็นต้นไม้เซกเมนต์โดยนัย. แนวคิดในที่นี้คือใช้โครงสร้างเซ็กเมนต์ของคุณตามปกติยกเว้นข้ามส่วนในตัวสร้างที่คุณเริ่มต้นลูกทางซ้ายและขวาของคุณ ตอนนี้เมื่อคุณต้องการเจาะลึกบุตรหลานของคุณเนื่องจากแบบสอบถามช่วงบางส่วนให้ตรวจสอบว่ามีอยู่หรือไม่และหากไม่มีให้สร้างขึ้น มิฉะนั้นเนื่องจากคุณไม่จำเป็นต้องสร้างให้ถือว่าผลรวมของค่าในโหนดเหล่านั้นเป็น 0!
วิธีแก้ไขขั้นสุดท้ายมีดังนี้: สร้างโครงสร้างกลุ่มของค่าสูงสุดที่สามารถสืบค้นได้ (หากคุณไม่จำเป็นต้องตอบแบบโต้ตอบให้พิจารณาบันทึกและสแกนคำค้นหาของคุณเพื่อค้นหาค่า r สูงสุด แต่คุณไม่จำเป็นต้องทำ) หมายเหตุนี้เพื่อให้ต้นไม้ส่วนโดยปริยาย O(log(max value))
รักษาอาร์เรย์แหล่งที่มาทุกครั้งหลังจากการปรับปรุงและยังทำจุดการปรับปรุงเกี่ยวกับต้นไม้ของคุณซึ่งจะเป็น O(log(max value))
การสืบค้นข้อมูลเป็นปกติคำสั่งช่วงต้นไม้ส่วนเหล่านี้จึงจะเป็น และนั่นเอง!
คุณสามารถใช้โครงสร้างข้อมูลตามนโยบายซึ่งมีวิธีการที่มีประโยชน์เช่น order_of_key () ซึ่งส่งคืนจำนวนรายการที่น้อยกว่าจำนวนที่กำหนด เราสามารถเรียกสิ่งนี้สองครั้งเช่น getcnt (b + 1) - getcnt (a) - ซึ่งจะให้จำนวนรายการระหว่างช่วงที่กำหนด สำหรับข้อมูลเพิ่มเติมเกี่ยวกับเรื่องนี้ - คุณสามารถอ้างอิง -https://codeforces.com/blog/entry/11080 และนอกจากนี้ยังมี https://gcc.gnu.org/onlinedocs/libstdc++/manual/policy_data_structures.html
หลังจากการวิจัยมากมายฉันพบว่า STL นี้มีประโยชน์มากในขณะที่ใช้โครงสร้างที่อิงจากต้นไม้
ฉันทดสอบโค้ดด้านล่างและผ่านทุกกรณีการทดสอบ
#include<bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp> // Common file
#include <ext/pb_ds/tree_policy.hpp> // Including tree_order_statistics_node_update
using namespace std;
using namespace __gnu_pbds;
template<class T> using cust_set = tree<
T,
null_type,
less<T>,
rb_tree_tag,
tree_order_statistics_node_update>;
cust_set<array<int,2>> freq;
int getcnt(int x)
{
return freq.order_of_key({x,0});
}
int main()
{
int n,q;
scanf("%d%d",&n,&q);
vector<int> emp(n);
int sal;
for(int i=0;i<n;i++)
{
cin >> emp[i];
freq.insert({emp[i],i});
}
char c;
int x,a,b;
while(q--)
{
cin>> c;
int ans=0;
if(c=='?')
{
cin>>a>>b;
cout << getcnt(b+1) - getcnt(a)<<"\n";
}
else
{
cin>>a>>b;
--a;
freq.erase({emp[a],a});
emp[a] = b;
freq.insert({emp[a],a});
}
}
return 0;
}