Pertanyaan CSES Range Query: Pertanyaan Gaji
Saya mencoba untuk memecahkan masalah ini: https://cses.fi/problemset/task/1144/
Diberikan array hingga 200000
elemen, tugas saya adalah memproses hingga 200000
kueri, yang meminta saya untuk memperbarui satu nilai dalam array atau meminta saya untuk menemukan jumlah elemen antara a dan b yang terletak dalam rentang tertentu (untuk misalnya, permintaan akan bertanya berapa banyak elemen dari indeks 1
ke 5
dalam kisaran [2, 3]
).
Ide saya saat ini adalah menggunakan kompresi indeks terlebih dahulu pada nilai-nilai dalam larik yang diberikan (karena nilainya dapat mencapai 10^9
, jadi menjaga larik kejadian sederhana akan melebihi batas penyimpanan), kemudian simpan larik lain yang berisi jumlah kemunculan masing-masing yang dikompresi jumlah. Kemudian, pemrosesan dan pembaruan kueri dapat dilakukan dengan menggunakan pohon segmen penjumlahan.
Namun, saya mengalami masalah saat mencoba menerapkan pendekatan ini. Saya menyadari bahwa memperbarui nilai array tunggal akan memaksa saya untuk mengubah array yang dikompresi.
Misalnya, jika diberikan sebuah array [1, 5, 3, 3, 2]
, saya akan mendefinisikan fungsi kompresi C
seperti itu
C[1] = 0;
C[2] = 1;
C[3] = 2;
C[5] = 3;
Kemudian, array kejadian akan menjadi [1, 1, 2, 1]
, dan pemrosesan kueri jumlah akan menjadi efisien. Namun, jika saya diinstruksikan untuk memperbarui nilai, katakanlah, ubah elemen ketiga menjadi 4
, maka itu akan membuat semuanya menjadi tidak seimbang. Fungsi kompresi harus diubah menjadi
C[1] = 0;
C[2] = 1;
C[3] = 2;
C[4] = 3;
C[5] = 4;
yang akan memaksa saya untuk merekonstruksi susunan kejadian saya, menghasilkan O(N)
waktu pembaruan.
Karena N
bisa sampai 200000
, pendekatan saya saat ini tidak akan bekerja cukup efisien untuk menyelesaikan masalah, meskipun saya pikir saya punya ide yang tepat dengan kompresi indeks. Bisakah seseorang menunjukkan arah yang benar dengan metode saya?
Jawaban
Anda memiliki ide yang tepat dalam menggunakan kompresi indeks - pemikiran yang bagus! Seperti N
hanya sampai 200000
, mempertahankan array kejadian paling banyak akan membutuhkan 200000
elemen untuk nilai awal dari array yang diberikan, bukan 10^9
indeks array.
Menurut diri Anda, masalah yang Anda hadapi adalah saat Anda menemukan nilai baru selama memproses kueri. Kamu benar; ini akan membuat array kejadian tidak seimbang dan menyebabkan pembaruan harus berjalan O(N)
tepat waktu. Solusi untuk masalah ini hanyalah sedikit modifikasi pada metode Anda saat ini.
Untuk mengatasi masalah menemukan nilai-nilai baru, kita bisa memastikan bahwa kita tidak akan pernah menemukan nilai-nilai baru. Kita bisa melakukan ini dengan membaca semua query sebelum membangun pohon sum segment. Ini akan menghasilkan maksimum N + 2*Q
nilai unik, atau 600000
dalam kasus terburuk, yang cukup jauh untuk membuat larik kejadian dengan batas penyimpanan masalah sebesar 512MB. Setelah itu, pohon segmen penjumlahan akan dapat menjawab pertanyaan ini secara efisien.
Jadi pada akhirnya, strategi untuk memecahkan masalah ini adalah dengan memasukkan setiap nomor unik, kemudian membuat fungsi kompresi indeks, kemudian menggunakan pohon segmen penjumlahan untuk memproses kueri penjumlahan secara efisien.
Di masa mendatang, ingatlah bahwa dalam jenis pertanyaan penjawab-kueri ini, mungkin berguna untuk membaca SEMUA masukan sebelum prakomputasi . Semoga berhasil dengan program Anda.
Pertama, pertimbangkan yang naif: Untuk setiap pembaruan, perbarui larik. Untuk setiap kueri, pindai seluruh larik dan kumpulkan jawaban Anda. Kompleksitas solusi ini memiliki O(n)
pembaruan, O(n)
kueri. Tidak baik.
Kita dapat menemukan solusi berbeda dengan kompleksitas waktu yang bisa dibilang lebih buruk, tetapi ini memberi kita petunjuk tentang apa hasil akhir kita. Pertahankan array sumber setiap saat, tetapi juga pertahankan peta hash nilai-> frekuensi. Kemudian, saat Anda memperbarui, turunkan frekuensi pada nilai lama dan tingkatkan pada nilai baru. Sekarang, untuk kueri, ulangi semua nilai dari rentang kueri itu dan jumlahkan untuk jawaban Anda. Ini menghasilkan O(1)
pembaruan dan O(r-l)
kueri, jadi kami memiliki pembaruan yang sangat baik tetapi kueri yang buruk. Namun, hasil ini dapat diperbaiki jika kita dapat hanya mempercepat query mereka! Masuk ke Segment Tree .
Secara tradisional, Anda akan membangun pohon segmen sampai ke daunnya saat pembuatan. Namun, kami secara nominal menyukai pohon segmen yang berkisar dari 0-10^9
, jadi sama sekali tidak mungkin kami dapat menghasilkan banyak memori (dan kami akan kehabisan waktu untuk melakukannya). Namun, bagaimana jika kita membuat pohon segmen, tetapi untuk setiap node, turunannya implisit jika belum pernah digunakan. Artinya, jangan buat node turunan jika tidak ada elemen di dalamnya . Struktur ini dinamai, tepat, Pohon Segmen Implisit. Idenya di sini adalah mengimplementasikan pohon segmen Anda seperti biasa kecuali melewatkan bagian dalam konstruktor tempat Anda menginisialisasi anak kiri dan kanan Anda. Sekarang, ketika Anda perlu mempelajari anak-anak Anda karena kueri rentang parsial, periksa apakah mereka ada, dan jika tidak, buatlah. Jika tidak, karena Anda tidak pernah perlu membuatnya, asumsikan jumlah nilai di node tersebut adalah 0!
Solusi terakhirnya adalah sebagai berikut: Buat pohon segmen dari nilai maksimal yang dapat dikueri (jika Anda tidak harus menjawab secara interaktif, pertimbangkan untuk menyimpan dan memindai kueri Anda untuk menemukan nilai r maksimal, tetapi Anda tidak perlu melakukannya). Perhatikan untuk menjadikan ini pohon segmen implisit . Pertahankan larik sumber setelah setiap pembaruan, dan juga lakukan pembaruan titik pada pohon Anda yang akan O(log(max value))
. Kueri adalah kueri rentang pohon segmen reguler, jadi ini akan menjadi O(log(max value))
. Dan itu dia!
Anda dapat menggunakan struktur data berbasis kebijakan, yang memiliki beberapa metode berguna seperti order_of_key () - yang mengembalikan jumlah item kurang dari jumlah yang diberikan. Kita dapat memanggil ini dua kali seperti getcnt (b + 1) - getcnt (a) - yang memberikan jumlah item antara rentang yang diberikan. Untuk info lebih lanjut tentang ini - Anda dapat merujuk -https://codeforces.com/blog/entry/11080 dan juga https://gcc.gnu.org/onlinedocs/libstdc++/manual/policy_data_structures.html
Setelah banyak penelitian, saya menemukan bahwa STL ini sangat berguna saat menggunakan struktur berbasis pohon.
Saya menguji kode di bawah ini dan melewati semua kasus uji.
#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;
}