คำถามแบบสอบถามช่วง CSES: แบบสอบถามเงินเดือน

Aug 18 2020

ฉันกำลังพยายามแก้ปัญหานี้: 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ได้แนวทางปัจจุบันของฉันจะไม่ทำงานได้อย่างมีประสิทธิภาพเพียงพอที่จะแก้ปัญหาแม้ว่าฉันคิดว่าฉันมีความคิดที่ถูกต้องในการบีบอัดดัชนี ใครช่วยชี้ทางที่ถูกต้องด้วยวิธีการของฉันได้ไหม

คำตอบ

6 Telescope Aug 18 2020 at 06:09

คุณมีความคิดที่ถูกต้องในการใช้การบีบอัดดัชนี - ความคิดที่ดี! ตามที่Nมีอยู่เท่านั้นการ200000เก็บอาร์เรย์เหตุการณ์ส่วนใหญ่จะต้องใช้200000องค์ประกอบสำหรับค่าเริ่มต้นของอาร์เรย์ที่กำหนดแทนที่จะเป็น10^9ดัชนีอาร์เรย์

ตามตัวคุณเองปัญหาที่คุณเผชิญคือเมื่อคุณพบค่าใหม่ในระหว่างการประมวลผลคำค้นหา คุณถูก; สิ่งนี้จะทำให้อาร์เรย์ของเหตุการณ์ไม่สมดุลและทำให้การอัปเดตต้องทำงานO(N)ทันเวลา วิธีแก้ปัญหานี้เป็นเพียงการปรับเปลี่ยนวิธีการปัจจุบันของคุณเล็กน้อย

เพื่อแก้ปัญหาการพบค่าใหม่เราสามารถตรวจสอบให้แน่ใจว่าเราจะไม่พบค่าใหม่ใด ๆ เราสามารถทำได้โดยการอ่านในแบบสอบถามทั้งหมดก่อนที่จะสร้างต้นไม้ส่วนผลรวม ซึ่งจะส่งผลให้มีN + 2*Qค่าที่ไม่ซ้ำกันสูงสุดหรือ600000ในกรณีที่แย่ที่สุดซึ่งไกลพอที่จะสร้างอาร์เรย์เหตุการณ์ที่มีขีด จำกัด พื้นที่เก็บข้อมูล 512MB ของปัญหา หลังจากนั้นต้นไม้ส่วนผลรวมจะสามารถตอบคำถามเหล่านี้ได้อย่างมีประสิทธิภาพ

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

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

3 JacobSteinebronn Aug 18 2020 at 01:41

ขั้นแรกให้พิจารณาความไร้เดียงสา: สำหรับการอัปเดตแต่ละครั้งให้อัปเดตอาร์เรย์ สำหรับแต่ละคำถามให้สแกนอาร์เรย์ทั้งหมดและรวบรวมคำตอบของคุณ ความซับซ้อนของโซลูชันนี้มีO(n)การอัปเดตO(n)แบบสอบถาม ไม่ดี.

เราสามารถหาวิธีแก้ปัญหาอื่นที่มีความซับซ้อนของเวลาที่แย่ลงได้ แต่มันให้คำใบ้ว่าผลลัพธ์สุดท้ายของเราคืออะไร รักษาอาร์เรย์ต้นทางตลอดเวลา แต่ยังเก็บแผนที่แฮชของค่า -> ความถี่ จากนั้นเมื่อคุณอัปเดตให้ลดความถี่ที่ค่าเดิมและเพิ่มขึ้นที่ค่าใหม่ ตอนนี้สำหรับข้อความค้นหาให้วนซ้ำค่าทั้งหมดของช่วงการสืบค้นนั้นและรวมเป็นคำตอบของคุณ สิ่งนี้ส่งผลให้เกิดการO(1)อัปเดตและการO(r-l)ค้นหาดังนั้นเราจึงมีการอัปเดตที่ยอดเยี่ยม แต่มีคำถามที่น่ากลัว อย่างไรก็ตามผลนี้จะดีขึ้นเมื่อถ้าเราสามารถเพียงแค่เพิ่มความเร็วในคำสั่งเหล่านั้น! ใส่Segment ต้นไม้

ตามเนื้อผ้าคุณจะต้องสร้างต้นไม้ส่วนลงไปจนถึงใบไม้เมื่อสร้างขึ้น อย่างไรก็ตามเราเรียกได้ว่าเป็นเหมือนต้นไม้เซกเมนต์ที่มีระยะ0-10^9ดังนั้นจึงไม่มีทางที่เราจะสร้างความทรงจำได้มากขนาดนั้น (และเราจะหมดเวลาในการทำเช่นนั้น) อย่างไรก็ตามจะเกิดอะไรขึ้นถ้าเราสร้างต้นไม้เซกเมนต์ แต่สำหรับทุกโหนดลูกของมันจะเป็นนัยถ้าไม่เคยใช้ นั่นคือไม่ได้สร้างโหนดลูกถ้าหากไม่มีองค์ประกอบในพวกเขาโครงสร้างนี้ได้รับการตั้งชื่อตามความเหมาะสมซึ่งเป็นต้นไม้เซกเมนต์โดยนัย. แนวคิดในที่นี้คือใช้โครงสร้างเซ็กเมนต์ของคุณตามปกติยกเว้นข้ามส่วนในตัวสร้างที่คุณเริ่มต้นลูกทางซ้ายและขวาของคุณ ตอนนี้เมื่อคุณต้องการเจาะลึกบุตรหลานของคุณเนื่องจากแบบสอบถามช่วงบางส่วนให้ตรวจสอบว่ามีอยู่หรือไม่และหากไม่มีให้สร้างขึ้น มิฉะนั้นเนื่องจากคุณไม่จำเป็นต้องสร้างให้ถือว่าผลรวมของค่าในโหนดเหล่านั้นเป็น 0!

วิธีแก้ไขขั้นสุดท้ายมีดังนี้: สร้างโครงสร้างกลุ่มของค่าสูงสุดที่สามารถสืบค้นได้ (หากคุณไม่จำเป็นต้องตอบแบบโต้ตอบให้พิจารณาบันทึกและสแกนคำค้นหาของคุณเพื่อค้นหาค่า r สูงสุด แต่คุณไม่จำเป็นต้องทำ) หมายเหตุนี้เพื่อให้ต้นไม้ส่วนโดยปริยาย O(log(max value))รักษาอาร์เรย์แหล่งที่มาทุกครั้งหลังจากการปรับปรุงและยังทำจุดการปรับปรุงเกี่ยวกับต้นไม้ของคุณซึ่งจะเป็น O(log(max value))การสืบค้นข้อมูลเป็นปกติคำสั่งช่วงต้นไม้ส่วนเหล่านี้จึงจะเป็น และนั่นเอง!

1 rootkonda Aug 18 2020 at 03:21

คุณสามารถใช้โครงสร้างข้อมูลตามนโยบายซึ่งมีวิธีการที่มีประโยชน์เช่น 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;
}