Question de requête sur la plage du CSES : requêtes sur les salaires
J'essaie de résoudre ce problème :https://cses.fi/problemset/task/1144/
Étant donné un tableau de jusqu'à 200000
éléments, ma tâche consiste à traiter jusqu'à des 200000
requêtes, qui me demandent soit de mettre à jour une seule valeur dans le tableau, soit de trouver le nombre d'éléments entre a et b qui se trouvent dans une plage donnée (par exemple, une requête demanderait combien d'éléments des indices 1
à 5
sont dans la plage [2, 3]
).
Mon idée actuelle est d'utiliser d'abord la compression d'index sur les valeurs du tableau donné (puisque les valeurs peuvent aller jusqu'à 10^9
, donc conserver un tableau d'occurrence simple dépasserait les limites de stockage), puis conserver un autre tableau contenant le nombre d'occurrences de chaque compressé Numéro. Ensuite, le traitement et la mise à jour des requêtes pourraient être effectués à l'aide d'un arbre de segments de somme.
Cependant, j'ai rencontré un problème en essayant de mettre en œuvre cette approche. J'ai réalisé que la mise à jour d'une seule valeur de tableau m'obligerait à changer le tableau compressé.
Par exemple, étant donné un array [1, 5, 3, 3, 2]
, je définirais une fonction de compression C
telle que
C[1] = 0;
C[2] = 1;
C[3] = 2;
C[5] = 3;
Ensuite, le tableau d'occurrences serait [1, 1, 2, 1]
, et le traitement des requêtes de somme serait efficace. Cependant, si on me demandait de mettre à jour une valeur, par exemple, de changer le troisième élément en 4
, cela déséquilibrerait tout. La fonction de compression devrait changer pour
C[1] = 0;
C[2] = 1;
C[3] = 2;
C[4] = 3;
C[5] = 4;
ce qui m'obligerait à reconstruire mon tableau d'occurrences, ce qui entraînerait un temps de mise à O(N)
jour.
Étant donné que N
peut aller jusqu'à 200000
, mon approche actuelle ne fonctionnera pas assez efficacement pour résoudre le problème, bien que je pense avoir la bonne idée avec la compression d'index. Quelqu'un peut-il s'il vous plaît me diriger dans la bonne direction avec ma méthode?
Réponses
Vous avez eu la bonne idée d'utiliser la compression d'index - une excellente idée ! Comme N
c'est uniquement jusqu'à 200000
, conserver un tableau d'occurrences nécessitera tout au plus des 200000
éléments pour les valeurs initiales du tableau donné, au lieu d' 10^9
indices de tableau.
Selon vous, le problème que vous rencontrez est lorsque vous rencontrez de nouvelles valeurs lors du traitement des requêtes. Tu as raison; cela déséquilibrerait le tableau d'occurrences et obligerait les mises à jour à s'exécuter à O(N)
temps. La solution à ce problème est juste une petite modification de votre méthode actuelle.
Pour résoudre le problème de rencontrer de nouvelles valeurs, nous pouvons simplement nous assurer que nous ne rencontrerons jamais de nouvelles valeurs. Nous pouvons le faire en lisant toutes les requêtes avant de construire l'arborescence des segments de somme. Cela se traduira par un maximum de N + 2*Q
valeurs uniques, ou 600000
dans le pire des cas, ce qui est suffisant pour construire un tableau d'occurrences avec la limite de stockage de 512 Mo du problème. Après cela, un arbre de segment de somme sera en mesure de répondre efficacement à ces requêtes.
Donc, en fin de compte, une stratégie pour résoudre ce problème serait d'entrer chaque nombre unique, puis de construire une fonction de compression d'index, puis d'utiliser un arbre de segments de somme pour traiter efficacement les requêtes de somme.
À l'avenir, rappelez-vous que dans ce genre de questions de type requête-réponse, il pourrait être utile de lire TOUTES les entrées avant le précalcul . Bonne chance avec votre programme.
Tout d'abord, considérez le naïf : pour chaque mise à jour, mettez à jour le tableau. Pour chaque requête, parcourez l'ensemble du tableau et recueillez votre réponse. La complexité de cette solution a des O(n)
mises à jour, des O(n)
requêtes. Pas bien.
Nous pouvons proposer une solution différente avec une complexité temporelle sans doute pire, mais cela nous donne un indice sur le résultat final. Maintenez le tableau source à tout moment, mais conservez également une carte de hachage de valeur-> fréquence. Ensuite, lorsque vous mettez à jour, décrémentez la fréquence à l'ancienne valeur et incrémentez-la à la nouvelle valeur. Maintenant, pour les requêtes, parcourez toutes les valeurs de cette plage de requêtes et additionnez-les pour votre réponse. Cela entraîne O(1)
des mises à jour et des O(r-l)
requêtes, nous avons donc d'excellentes mises à jour mais des requêtes affreuses. Cependant, ce résultat peut être amélioré si nous pouvons simplement accélérer ces requêtes ! Entrez dans l' arborescence des segments .
Traditionnellement, vous construisiez une arborescence de segments jusqu'à ses feuilles lors de la création. Cependant, nous aimerions théoriquement un arbre de segments allant de 0-10^9
, donc il n'y a absolument aucun moyen de générer autant de mémoire (et nous perdrions du temps en le faisant). Cependant, que se passe-t-il si nous créons un arbre de segments, mais pour chaque nœud, ses enfants sont implicites s'ils n'ont jamais été utilisés. Autrement dit, ne créez pas de nœuds enfants s'ils ne contiennent pas d'éléments . Cette structure est nommée, à juste titre, l' arbre de segment implicite. L'idée ici est d'implémenter votre arborescence de segments comme d'habitude, sauf que vous ignorez la partie du constructeur où vous initialisez vos enfants gauche et droit. Désormais, lorsque vous devez vous plonger dans vos enfants en raison d'une requête de plage partielle, vérifiez s'ils existent et, s'ils n'existent pas, créez-les. Sinon, puisque vous n'avez jamais eu besoin de les créer, supposez que la somme des valeurs de ces nœuds est 0 !
La solution finale est la suivante : créez une arborescence de segments de la valeur maximale interrogeable (si vous n'avez pas à répondre de manière interactive, envisagez d'enregistrer et d'analyser vos requêtes pour trouver la valeur r maximale, mais vous n'êtes pas obligé de le faire). Remarque pour en faire une arborescence de segments implicite . Maintenez le tableau source après chaque mise à jour et faites également des mises à jour ponctuelles sur votre arbre qui sera O(log(max value))
. Les requêtes sont des requêtes de plage d'arborescence de segments régulières, elles seront donc O(log(max value))
. Et ça y est !
Vous pouvez utiliser une structure de données basée sur des règles, qui contient des méthodes utiles telles que order_of_key() - qui renvoie un nombre d'éléments inférieur au nombre donné. Nous pouvons appeler cela deux fois comme getcnt(b+1) - getcnt(a) - qui donne le nombre d'éléments entre la plage donnée. Pour plus d'informations à ce sujet - vous pouvez consulter -https://codeforces.com/blog/entry/11080et aussihttps://gcc.gnu.org/onlinedocs/libstdc++/manual/policy_data_structures.html
Après de nombreuses recherches, j'ai trouvé que cette STL est très utile lors de l'utilisation de structures arborescentes.
J'ai testé le code ci-dessous et il passe tous les cas de test.
#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;
}