CSES Aralık Sorgu Sorusu: Maaş Sorguları
Bu sorunu çözmeye çalışıyorum: https://cses.fi/problemset/task/1144/
En fazla 200000öğe dizisi verildiğinde , benim görevim 200000ya dizideki tek bir değeri güncellememi ya da belirli bir aralıkta yer alan a ve b arasındaki öğelerin sayısını bulmamı isteyen sorguları işlemektir. endeksleri pek çok parça nasıl örnek, bir sorgu isteyeceğini 1için 5aralığındadır [2, 3]).
Şu anki fikrim, önce verilen dizideki değerlerde dizin sıkıştırması kullanmaktır (değerler en fazla olabilir 10^9, bu nedenle basit bir oluşum dizisi tutmak depolama sınırlarını aşar), ardından sıkıştırılmış her bir dizinin oluşum sayısını içeren başka bir dizi tutmaktır. numara. Ardından, sorguların işlenmesi ve güncellenmesi, bir toplam segment ağacı kullanılarak yapılabilir.
Ancak bu yaklaşımı uygulamaya çalışırken bir sorunla karşılaştım. Tek bir dizi değerini güncellemenin beni sıkıştırılmış diziyi değiştirmeye zorlayacağını fark ettim.
Örneğin, bir dizi verilen [1, 5, 3, 3, 2], bir kompresyon fonksiyonu tanımlamak Cşekilde
C[1] = 0;
C[2] = 1;
C[3] = 2;
C[5] = 3;
Ardından, oluşum dizisi olur [1, 1, 2, 1]ve toplam sorguları işlemek verimli olur. Ancak, bir değeri güncellemem , diyelim ki üçüncü öğeyi olarak değiştirmem istenirse 4, bu her şeyi dengeden çıkarır. Sıkıştırma işlevi şu şekilde değişmelidir:
C[1] = 0;
C[2] = 1;
C[3] = 2;
C[4] = 3;
C[5] = 4;
bu da beni oluşum dizimi yeniden yapılandırmaya zorlayarak O(N)güncelleme zamanına neden olur.
Yana Nkadar olabilir 200000ben endeksi sıkıştırma ile doğru fikri var, ancak benim şimdiki yaklaşım, sorunu çözmek için yeterince verimli çalışmaz. Biri lütfen yöntemimle beni doğru yöne yönlendirebilir mi?
Yanıtlar
Dizin sıkıştırmayı kullanma konusunda doğru fikre sahipsiniz - harika fikir! NSadece bağlı olduğu gibi , 200000bir oluşum dizisini tutmak, en çok 200000, 10^9dizi indeksleri yerine verilen dizinin ilk değerleri için elemanlar gerektirecektir .
Kendinize göre, karşılaştığınız sorun, sorguları işlerken yeni değerlerle karşılaşmanızdır. Haklısın; bu, oluşum dizisinin dengesini bozar ve güncellemelerin O(N)zamanında çalışmasına neden olur . Bu sorunun çözümü, mevcut yönteminizde sadece küçük bir değişikliktir.
Yeni değerlerle karşılaşma sorununu çözmek için, hiçbir zaman yeni değerlerle karşılaşmayacağımızdan emin olabiliriz . Bunu , toplam segment ağacını oluşturmadan önce tüm sorguları okuyarak yapabiliriz . Bu, maksimum N + 2*Qbenzersiz değerlerle veya 600000en kötü durumda, sorunun 512 MB depolama sınırıyla bir oluşum dizisi oluşturmaya yetecek kadar uzak olmasına neden olur. Bundan sonra, bir toplam segment ağacı bu sorgulara verimli bir şekilde cevap verebilecektir.
Sonuç olarak, bu sorunu çözmek için bir strateji, her benzersiz sayıyı girmek, ardından bir dizin sıkıştırma işlevi oluşturmak ve ardından toplam sorgularını verimli bir şekilde işlemek için bir toplam segment ağacı kullanmak olacaktır.
Gelecekte, bu tür sorgu cevaplama soruları için, ön hesaplamadan önce TÜM girdileri okumanın yararlı olabileceğini unutmayın . Programınızda iyi şanslar.
İlk olarak saflığı düşünün: Her güncelleme için diziyi güncelleyin. Her sorgu için tüm diziyi tarayın ve cevabınızı toplayın. Bu çözümün karmaşıklığında O(n)güncellemeler, O(n)sorgular var. İyi değil.
Muhtemelen daha kötü zaman karmaşıklığına sahip farklı bir çözüm bulabiliriz, ancak bu bize nihai sonucumuzun ne olduğuna dair bir ipucu verir. Kaynak dizisini her zaman koruyun, ancak aynı zamanda değer-> frekansın bir karma haritasını da tutun. Ardından, güncellediğinizde, frekansı eski değerde azaltın ve yeni değerde artırın. Şimdi, sorgular için, o sorgu aralığının tüm değerleri arasında döngü yapın ve cevabınız için bunları toplayın. Bu, O(1)güncellemelere ve O(r-l)sorgulara neden olur, bu nedenle mükemmel güncellemelerimiz var, ancak korkunç sorgularımız var. Ancak, bu sonuç biz eğer üzerine geliştirilebilir sadece bu sorguları hızlandırmak! Segment Ağacına girin .
Geleneksel olarak, oluşturulduktan sonra yapraklarına kadar bir dilim ağacı inşa edersiniz. Bununla birlikte, nominal olarak farklı bir segment ağacını severdik 0-10^9, bu yüzden bu kadar hafıza üretmemizin kesinlikle bir yolu yoktur (ve bunu yaparken zaman aşımına uğrarız). Ancak, bir kesimi ağacı neyi oluşturursanız, ama her düğüm için, birimin altında olan örtülü kullanıldıkları olmamıştım eğer. Yani, içlerinde öğe yoksa alt düğümler oluşturmayın . Bu yapı uygun bir şekilde Örtük Segment Ağacı olarak adlandırılır. Buradaki fikir, yapıcıdaki sol ve sağ çocuklarınızı başlattığınız kısmı atlamak dışında, segment ağacınızı normal şekilde uygulamaktır. Şimdi, kısmi aralık sorgusu nedeniyle çocuklarınızı araştırmanız gerektiğinde, var olup olmadıklarını kontrol edin ve yoksa oluşturun. Aksi takdirde, bunları hiç yapmanız gerekmediğinden, bu düğümlerdeki değerlerin toplamının 0 olduğunu varsayın!
Nihai çözüm şu şekildedir: Sorgulanabilir maksimum değerden bir segment ağacı oluşturun (etkileşimli olarak yanıt vermeniz gerekmiyorsa, maksimum r değerini bulmak için sorgularınızı kaydetmeyi ve taramayı düşünün, ancak buna gerek yoktur). Bunu örtük bir segment ağacı yapmaya dikkat edin . Her güncellemeden sonra kaynak dizisini koruyun ve ayrıca ağacınızda olacak nokta güncellemeleri yapın O(log(max value)). Sorgular, normal segment ağaç aralığı sorgulardır, bu nedenle bunlar olacaktır O(log(max value)). Ve işte orada!
Verilen sayıdan daha az öğe sayısını döndüren order_of_key () gibi bazı yararlı yöntemlere sahip olan politika tabanlı veri yapısını kullanabilirsiniz. Bunu, verilen aralık arasındaki öğelerin sayısını veren getcnt (b + 1) - getcnt (a) gibi iki kez çağırabiliriz. Bununla ilgili daha fazla bilgi için - başvurabilirsiniz -https://codeforces.com/blog/entry/11080 ve ayrıca https://gcc.gnu.org/onlinedocs/libstdc++/manual/policy_data_structures.html
Çok fazla araştırmadan sonra bu STL'nin ağaç temelli yapıları kullanırken çok faydalı olduğunu buldum.
Aşağıdaki kodu test ettim ve tüm test durumlarını geçti.
#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;
}