35ος ΠΔΠ Γ' Φάση: Νησιά (islands) - Λύση
Επεξήγηση εκφώνησης
Έχουμε \(N\) νησιά διατεταγμένα σε μια γραμμή, στα οποία μπορούμε να ταξιδεύουμε μόνο προς τη μια κατεύθυνση και συγκεκριμένα από κάθε νησί \(i\) στο \(i+1\) (\(1\le i < N\)). Αρχικά όλες οι μετακινήσεις είναι δωρεάν.
Δίνονται \(Q\) ανακοινώσεις και ερωτήματα:
- Όλες οι μετακινήσεις από κάθε νησί \(i\) στο \(i+1\) με \(a \le i < b\) θα απαιτούν εισιτήριο.
- Όλες οι μετακινήσεις από κάθε νησί \(i\) στο \(i+1\) με \(a \le i < b\) θα γίνονται δωρεάν.
- Αν ξεκινήσουμε από το νησί \(i\) με \(b\) εισιτήρια, μέχρι ποιο νησί θα φτάσουμε;
Στην συνέχεια θα παρουσιαστούν:
- Μια λύση brute force για το subtask με \(N,Q\le 1000\).
- Μια λύση με prefix sum που λύνει το subtask όπου καμία ανακοίνωση δεν θα γίνει μετά από ερώτημα.
- Δύο λύσεις με segment tree για το subtask όπου κάθε ανακοίνωση έχει \(b=a+1\) και επεκτείνουν την προηγούμενη λύση των prefix sum.
- Δύο λύσεις με lasy propagation σε segment tree που επεκτείνουν την προηγούμενη λύση και χρόνους \(\mathcal{O}(Q\cdot \log^2{N})\) και \(\mathcal{O}(Q\cdot \log{N})\). Η δεύτερη από αυτές αποτελεί πλήρη λύση.
- Δύο λύσεις με sqrt decomposition που αποτελούν διαφορετική προσέγγιση στην προηγούμενη λύση με χρόνους \(\mathcal{O}(Q\cdot \sqrt{N} \cdot \log{N})\) και \(\mathcal{O}(Q\cdot \sqrt{N})\). Η δεύτερη από αυτές αποτελεί πλήρη λύση.
Παρατήρηση 1
Αν έχουμε δύο διαδοχικά νησιά \(a\) και \(a+1\) και η μετάβαση από το πρώτο στο δεύτερο απαιτεί εισιτήριο,
το εισιτήριο αυτό περιορίζει την πρόσβαση στο \(a+1\) νησί και δεν επηρεάζει την πρόσβαση στο \(a\).
Θα δημιορυργήσουμε έναν πίνακα ακεραίων (ή boolean) με όνομα \(Z\) και θέτουμε στη θέση \(i\)
την τιμή \(1\) αν χρειαζόμαστε εισιτήριο για να φτάσουμε στο νησί \(i\) από το νησί \(i-1\) ή \(0\) αν η μετάβαση είναι δωρεάν.
Στη θέση \(1\) δεν θα χρειαστούμε ποτέ εισιτήριο, οπότε ισχύει πάντα ότι \(Z_1=0\)
Στα ερωτήματα που μας δίνονται, ξεκινώντας από το νησί \(a\), προχωρούμε δεξιότερα στο \(a+1\) έως ότου εξαντλήσουμε τα \(b\) εισιτήρια ή όσο δεν χρειάζεται επιπλέον εισιτήριο ή μέχρι να φτάσουμε στο τελευταίο νησί.
Λύση brute force (10%)
Το subtask με \(N,Q\le 1000\), μπορεί να λυθεί με τη μέθοδο της εξαντλητικής διερεύνησης brute force. Για κάθε ανακοίνωση, θέτουμε \(0\) ή \(1\) σε όλες τις θέσεις του διαστήματος \([a+1,b]\) του πίνακα \(Z\) που επηρεάζει η ανακοίνωση. Ο χρόνος ανά ενημέρωση διαστήματος είναι \(\mathcal{O}(N)\) εφόσον το μήκος του διαστήματος είναι \(\mathcal{O}(N)\). Στα ερωτήματα, ξεκινάμε από την αφετηρία \(a\) που μας δίνεται και προχωρούμε προς το νησί \(N\) έως να το φτάσουμε ή να εξαντλήσουμε τα \(b\) εισιτήρια που έχουμε στη διάθεση μας. Ο χρόνος ανα ερώτημα είναι επίσης \(\mathcal{O}(N)\) εφόσον μπορεί να χρειαστεί να προσπεράσουμε ολόκληρο τον πίνακα εισιτηρίων.
Συνεπώς, ο χρόνος που απαιτείται για τα \(Q\) ερωτήματα είναι της τάξης \(\mathcal{O}(Q \cdot N)\).
#include <cstdio>
#include <vector>
using namespace std;
int main(){
freopen("islands.in","r",stdin);
freopen("islands.out","w",stdout);
long N,Q,ans;
scanf("%ld%ld",&N,&Q);
vector<bool> Z(N+1,false);//Z[i]: αν χρειάζεται εισιτήριο για μετάβαση από νησί i-1 στο i
while(Q--){
char c;long a,b;
scanf(" %c%ld%ld",&c,&a,&b);
switch(c){
case 'D':
case 'B':
for(long i=a+1;i<=b;i++)
Z[i] = (c == 'D');
break;
case 'Q':
ans = a;
while(ans<N && (!Z[ans+1] || b-->0))
ans++;
printf("%ld\n",ans);
break;
}
}
return 0;
}
Λύση subtask με prefix sum (20%)
Η παρακάτω λύση αφορά το subtask συνολικής αξίας 20% όπου καμία ανακοίνωση δεν θα γίνεται μετά από ερώτημα.
Το πρώτο στάδιο της λύσης φροντίζει να αξιοποιεί με αποδοτικό τρόπο τις ενημερώσεις. Η τεχνική που χρησιμοποιείται, αποθηκεύει μόνο την αρχή και το τέλος κάθε διαστήματος που επηρεάζει μια ανακοίνωση (δηλαδή τα γεγονότα έναρξης και λήξης κάθε μιας ανακοίνωσης) σε χρόνο \(\mathcal{O}(Q)\). Στο τέλος όλων των ανακοινώσεων, θα προσπελάσουμε μια φορά γραμμικά τον πίνακα γεγονότων για να φτιάξουμε τον τελικό πίνακα εισιτηρίων \(Z\). Κατά την προσπέλαση του πίνακα γεγονότων, θα χρειαστεί να κρατάμε ένα set με τις ενεργές ανακοινώσεις, ώστε να ξέρουμε ανα πάσα στιγμή ποιά είναι η πιό πρόσφατη. Η προσπέλαση του πίνακα γεγονότων θα χρειαστεί χρόνο της τάξης \(\mathcal{O}(Q \cdot \log{Q} + N)\) καθώς θα είσαγει και θα διαγράψει έως \(Q\) στοιχεία στο set και θα ενημερώσει \(N\) τιμές στους πίνακες \(Z\) και \(PS\).
Το δεύτερο στάδιο της λύσης αφορά την απάντηση των ερωτημάτων. Σε οποιοδήποτε διάστημα \([a+1,b]\)
αθροίζοντας τα αντίστοιχα στοιχεία του \(Z\) βρίσκουμε πόσα εισιτήρια χρειάζονται
για να ταξιδέψουμε από το νησί \(a\) στο \(b\).
Μια μέθοδος για να απαντάμε αθροίσματα διαστημάτων στον πίνακα \(Z\), είναι να δημιουργήσουμε έναν
πίνακα \(PS\) με τα prefix sum του \(Z\). Το prefix sum κάθε θέσης \(i\) είναι το
άθροισμα όλων των στοιχείων \(Z_1+Z_2+\ldots+Z_i\) ή
πιο σύντομα \(PS_i = \sum_{j=1}^i{Z_j}\).
Ο πίνακας \(Z\) δεν είναι απαραίτητο να κρατηθεί, καθώς μπορούμε να υπολογίζουμε κατευθείαν τα prefix sums.
Το μειονέκτημα στο prefix sum είναι ότι δεν είναι αποδοτικό στις ενημερώσεις τιμών
και πρέπει να επανυπολογισθεί. Στο subtask αυτό όμως, όλες οι ανακοινώσεις που
προκαλούν ενημερώσεις τιμών στον πίνακα \(Z\), συμβαίνουν πριν αρχίσουν τα ερωτήματα,
οπότε θα υπολογίσουμε μόνο μια φορά τα prefix sum αφού σταματήσουν οι ανακοινώσεις.
Αν χρειάζονται \(k\) εισιτήρια για να μεταβούμε από το νησί \(a\) στο \(b\) και \(m\) εισιτήρια
για να μεταβούμε από το \(a\) στο \(b+1\), ισχύει \(k\lt m\), άρα ο πίνακας \(PS\) έχει αύξουσα διάταξη.
Με τη χρήση δυαδικής αναζήτησης μπορούμε, έχοντας έναν αριθμό εισιτηρίων \(b\), να βρούμε τη θέση \(i\)
στην οποία αυτά θα έχουν χρησιμοποιηθεί.
Χρησιμοποιώντας την upper_bound η οποία χρησιμοποιεί δυαδική αναζήτηση βρίσκουμε την πρώτη θέση στον πίνακα \(PS\)
(άρα και το αντίστοιχο νησί) που ξεπερνά τα εισιτήρια \(b\) που έχουμε στη διάθεση μας
(ή την θέση \(N+1\) αν εξαντληθεί ο πίνακας \(PS\)),
οπότε απαντάμε με την αμέσως προηγούμενη θέση.
Κάθε ερώτημα χρειάζεται χρόνο τάξης \(\mathcal{O}(\log{N})\) λόγω της δυαδικής
αναζήτησης στα \(N\) στοιχεία του πίνακα \(PS\).
Ο απαιτούμενος χρόνος είναι της τάξης \(\mathcal{O}(Q\cdot \log{Q} + N\cdot \log{N})\).
vector<vector<long>> E(N+1);//γεγονότα (events) έναρξης-λήξης ανακοινώσεων
vector<int> S(Q+1);//είδος ανακοίνωσης (1=έναρξη απεργίας,0=λήξη)
char c;long a,b;
for(qq=1;qq<=Q;qq++){//q=χρονική σειρά της ανακοίνωσης
scanf(" %c%ld%ld",&c,&a,&b);
if(c=='Q')break;//αρχίζουν τα ερωτήματα
S[qq] = (c=='D');
E[a+1].push_back(qq);//εδώ ξεκινά το διάστημα της ανακοίνωσης (βάλε θετικό πρόσιμο)
E[b+1].push_back(-qq);//εδώ έληξε το διάστημα της ανακοίνωσης (βάλε αρνητικό πρόσιμο)
}
set<long> A;//αποθηκεύουμε τις ενεργές ανακοινώσεις
A.insert(0);//Τη χρονική στιγμή 0, οι μετακινήσεις είναι δωρεάν
//προϋπολόγισε τον πίνακα prefix sum
vector<long> PS(N+1,0);
for(long i=1;i<=N;i++){
for(auto ev:E[i]){
if(ev>0)
A.insert(ev);//ξεκινά η ανακοίνωση με αριθμό ev
else
A.erase(-ev);//τελείωσε η ανακοίνωση με αριθμό -ev
}
int z = S[*A.rbegin()];//υπολόγισε το Z[i] από την πιο πρόσφατη ανακοίνωση
PS[i] = PS[i-1] + z;
}
//απάντηση ερωτημάτων. Τα c,a,b περιέχουν το 1ο ερώτημα
while(qq++<=Q){
//βρες τελευταία θέση με PS[x]==PS[a]+b
long ans = upper_bound(PS.begin(),PS.end(),PS[a]+b)-PS.begin();
printf("%ld\n",ans-1);
if(qq<=Q){
scanf(" %c%ld%ld",&c,&a,&b);
if(c!='Q') break;//δεν βρισκόμαστε στο σωστό subtask
}
}
Δείτε ολόκληρο τον κώδικα εδώ.
Λύση subtask με σημειακές ανακοινώσεις (30%)
Γνώσεις που θα χρειαστούμε: Segment Tree ή Binary Indexed Tree
Στο subtask αυτό οι ανακοινώσεις αναφέρονται σε διαστήματα μεγέθους \(1\) (από θέση \(a\) σε \(a+1\)), δηλαδή είναι σημειακές. Δύο λύσεις που μπορούν να κάνουν σημειακές ενημερώσεις στα prefix sum σε αποδοτικό χρόνο, είναι οι δομές segment tree και binary indexed tree. Η δομή segment tree αποτελείται από ένα ισοροπημένο δυαδικό δέντρο με \(N\) φύλλα και ύψος \(\mathcal{O}(\log{N})\). Κάθε κόμβος του δέντρου είναι είτε φύλλο και κρατά ένα στοιχείο του \(Z\), είτε έχει δύο απογόνους και κρατά το άθροισμα τους. Κάθε ενημέρωση ενός στοιχείου του \(Z\) (δηλαδή ενός φύλλου του segment tree) απαιτεί μόνο \(\log{N}\) ενημερώσεις στους κόμβους που είναι πρόγονοι του φύλλου. Στο συγκεκριμένο segment tree υπολογίζουμε τα αθροίσματα διαστημάτων (range sums) που θα χρησιμοποιήσουμε στη λύση του subtask.
long query(long si,long ss,long se,long L,long R){//υπολόγισε άθροισμα διαστήματος [L,R]
if(R<ss || se<L || R<L)
return 0;//βγήκαμε εκτός διαστήματος {L,R]
if(L<=ss && se<=R)
return st[si];//το διάστημα [ss,se] περιέχεται στο [L,R]
long mid = (ss+se)/2;
return query(si*2+1,ss,mid,L,R)+query(si*2+2,mid+1,se,L,R);
}
void upd(long si,long ss,long se,long pos,long val){//ενημέρωσε τη θέση pos με την τιμή val
if(ss == se){//φτάσαμε στο φύλλο pos
st[si] = val;
return;
}
long mid = (ss+se)/2;
if(pos<=mid)
upd(si*2+1,ss,mid,pos,val);
else
upd(si*2+2,mid+1,se,pos,val);
st[si] = st[si*2+1]+st[si*2+2];
}
Για κάθε ερώτημα που ξεκινά από το νησί \(a\) με \(b\) εισιτήρια:
- κάνουμε μια αναζήτηση πόσα εισιτήρια χρειάζονται για να πάμε από το νησί \(1\) στο \(a\) και τα προσθέτουμε στο \(b\). Με τον τρόπο αυτό μετασχηματίζουμε το ερώτημα που μας δίνεται και αντί για αφετηρία το νησί \(a\), έχουμε το νησί \(1\) (οπότε συνεχίζουμε όπως με το subtask με prefix sum).
- Κάνουμε δυαδική αναζήτηση στις θέσεις των νησιών μέχρι να βρούμε σε ποιό νησί έχουμε ξοδέψει \(b\) εισιτήρια.
Κάθε ερώτημα του προβλήματος θα κάνει λόγω της δυαδικής αναζήτησης \(\log{N}\) αναζητήσεις στο segment tree, κάθε μια από τις οποίες χρειάζεται χρόνο \(\mathcal{O}(\log{N})\), άρα η συνολική πολυπλοκότητα της λύσης αυτής είναι \(\mathcal{O}(Q\cdot \log^2{N})\).
b += query(0,1,N,1,a);
long left = a, right = N, ans = a;
while(left<=right){
long mid = (left+right)/2;
if(query(0,1,N,1,mid) > b){
right = mid - 1;//δεν φτάσαμε μέχρι το mid με b εισιτήρια
} else {
ans = mid;//το δεξιότερο όριο έως τώρα με b εισιτήρια
left = mid + 1;//ας δοκιμάσουμε ακόμα δεξιότερα
}
}
printf("%ld\n",ans);
Δείτε ολόκληρο τον κώδικα εδώ.
Βελτιωμένη λύση subtask με σημειακές ανακοινώσεις (30%)
Στο παραπάνω segment tree, κάθε διάστημα \([1,i]\) δίνεί το prefix sum της θέσης \(i\). Τα prefix sums έχουν αύξουσα διάταξη άρα στο segment tree όταν βρισκόμαστε σε οποιοδήποτε κόμβο \(si\) έχοντας \(b\) εισιτήρια, αποφασίζουμε αν θα πάμε στο αριστερό τμήμα του δηλαδή στον κόμβο \(si\cdot 2+1\) (αν δεν μας φτάνουν τα εισιτήρια για να τον προσπεράσουμε) ή στο δεξί κόμβο \(si\cdot 2+2\) (αν έχουμε αρκετά εισιτήρια για να προσπεράσουμε το αριστερό τμήμα του) οπότε ενσωματώνουμε τη δυαδική αναζήτηση στη δομή του.
Πιο αναλυτικά: αν \(b<st[si\cdot 2+1]\) θα συνεχίσουμε στον αριστερό απόγονο (καθώς τα εισιτήρια μας δεν μας επιτρέπουν να τον προσπεράσουμε), ενώ αν \(b>st[si\cdot 2+2]\) θα συνεχίσουμε στον δεξιό απόγονο (στην περίπτωση αυτή μειώνονται τα \(b\) εισιτήρια μας σε \(b-st[si\cdot 2+1]\) καθώς προσπεράσαμε τα νησιά του αριστερού απογόνου). Η περίπτωση \(b=st[si\cdot 2+1]\) χρειάζεται ιδιαίτερη προσοχή καθώς εξαντλήσαμε όλα μας τα εισιτήρια στο διάστημα που καλύπτει ο αριστερός κόμβος αλλά θέλουμε να συνεχίσουμε και στον δεξιό για τα εντοπίσουμε τα αριστερότατα συνεχόμενα νησιά του, που δεν χρειάζονται εισιτήριο. Υπάρχει όμως η περίπτωση να μη βρεθεί κανένα νησί στο αριστερό άκρο του δεξιού κόμβου χωρίς εισιτήριο. Στην περίπτωση αυτή, θα πρέπει να επιστρέψουμε μια θέση προς τα αριστερά (ώστε να ξαναγυρίσουμε στο δεξιότατο άκρο του αριστερού κόμβου).
if(B<st[si])//τα εισιτήρια μας έχουν εξαντληθεί και δεν μπορούμε να φτάσουμε στο νησί ss.
return ss-1;
return ss;
Συνολική πολυπλοκότητα \(\mathcal{O}(Q\cdot \log{N})\).
long query(long si,long ss,long se,long B){//βρες τη δεξιότερη θέση x, με sum[1,x]=B
while(ss<se){
long mid = (ss+se)/2;
if(B < st[si*2+1]){//πήγαινε αριστερά
si = si*2+1;
se = mid;
} else {
//Τα εισιτήρια μας έφτασαν για να καλυφθεί το αριστερό segment
//αλλά ίσως εξαντλήθηκαν. Ακόμα και αν εξαντλήθηκαν, θα προχωρήσουμε στο
//δεξιό segment (ώστε να προσπεράσουμε τα νησιά που δεν χρειάζονται εισιτήριο).
//Φτάνοντας στο φύλλο του δέντρου, θα αποφασίσουμε αν το παρακάναμε.
B -= st[si*2+1];//αφαίρεσε τα χρησιμοποιημένα εισιτήρια του αριστερού segment
si = si*2+2;
ss = mid+1;
}
}
if(B<st[si])//τα εισιτήρια μας έχουν εξαντληθεί και δεν μπορούμε να φτάσουμε στο νησί ss.
return ss-1;
return ss;
}
Δείτε ολόκληρο τον κώδικα εδώ.
Λύση με lazy propagation σε segment tree (76%)
Το μειονέκτημα του παραπάνω segment tree είναι ότι ενημερώνει μόνο ένα δρομολόγιο σε χρόνο \(\mathcal{O}(\log{N})\), κάνει δηλαδή σημειακά updates. Αν έχουμε να ενημερώσουμε ένα διάστημα \([a,b]\) με έως \(N\) δρομολόγια, θα ξοδέψουμε χρόνο της τάξης \(\mathcal{O}(N\cdot \log{N})\). Τη λύση σε αυτό τη δίνει μια τροποποίηση στο segment tree που λέγεται lazy propagation. Σε κάθε ανακοίνωση δεν ενημερώνουμε απευθείας όλα τα επηρεαζόμενα φύλλα, αλλά αφήνουμε τις ενημερώσεις όσο πιο ψηλά στο δέντρο μπορούμε και “τεμπελιάζουμε”. Όταν θα χρειαστεί σε επόμενη ανακοίνωση ή ερώτηση να προσπελάσουμε κάποιον κόμβο που έχει τιμή που “τεμπελιάζει”, σπρώχνουμε πιο χαμηλά την “τεμπέλικη” τιμή πριν προσπεράσουμε τον κόμβο αυτό.
void pushlazy(long si,long ss,long se){
if(lazy[si]==-1)
return;//no lazy here
if(ss == se){//leaf
st[si] = lazy[si];
lazy[si]=-1;
return;
}
long mid = (ss+se)/2;
lazy[si*2+1] = lazy[si*2+2] = lazy[si];//σπρώξε πιο κάτω το lazy
st[si*2+1] = (mid-ss+1)*lazy[si];//άθροισμα του διαστήματος που καλύπτει το αριστερό παιδί
st[si*2+2] = (se-(mid+1)+1)*lazy[si];//άθροισμα του διαστήματος που καλύπτει το αριστερό παιδί
st[si] = st[si*2+1]+st[si*2+2];//υπολόγισε το άθροισμα του τρέχοντος κόμβου
lazy[si] = -1;//έφυγε το lazy από τον τρέχοντα κόμβο
}
void upd(long si,long ss,long se,long L,long R,int val){
if(R<ss || se<L)
return;
if(L<=ss && se<=R){
lazy[si] = val;//ακόμα και αν είχε κάποιο lazy εδώ, ας χαθεί (ακυρώνεται)
st[si] = (se-ss+1) * val;
return;
}
pushlazy(si,ss,se);//αν τα παλιά lazy δεν ακυρώνονταν, η γραμμή αυτή θα έπρεπε να μπει πριν το προηγούμενο if
long mid = (ss+se)/2;
upd(si*2+1,ss,mid,L,R,val);
upd(si*2+2,mid+1,se,L,R,val);
st[si] = st[si*2+1]+st[si*2+2];
}
long query(long si,long ss,long se,long L,long R){//βρες το άθροισμα διαστήματος
pushlazy(si,ss,se);
if(L<=ss && se<=R)
return st[si];
if(R<ss || se<L)
return 0;
long mid = (ss+se)/2;
return query(si*2+1,ss,mid,L,R)+query(si*2+2,mid+1,se,L,R);
}
Ο παρακάτω κώδικας χρησιμοποιεί δυαδική αναζήτηση για να βρεί πως θα ξοδέψει \(b\) εισιτήρια. Ο χρόνος που απαιτείται είναι της τάξης \(\mathcal{O}(Q\cdot \log^2{N})\).
b += query(0,1,N,1,a);//μετέτρεψε το ταξίδι από το a σε ταξίδι από το 1
long left = a,right = N,ans = a;
while(left<=right){
long mid = (left+right)/2;
if(query(0,1,N,1,mid)>b){//πήγαινε αριστερά
right = mid - 1;
} else {//φτάσαμε έως εδώ, δοκίμασε ακόμα δεξιότερα
ans = mid;
left = mid + 1;
}
}
printf("%ld\n",ans);
Δείτε ολόκληρο τον κώδικα εδώ.
Πλήρης λύση με lazy propagation (100%)
Όπως και στη λύση των σημειακών ενημερώσεων χωρίς δυαδική αναζήτηση, έτσι και εδώ έχουμε να λύσουμε το πρόβλημα πως θα προχωρήσουμε στο δεξιό κόμβο (για να ανακαλύψουμε τα αριστερότατα \(0\)) αν έχουμε εξαντλήσει τα εισιτήρια μας στον αριστερό κόμβο. Εκτός από τη λύση που δόθηκε παραπάνω, θα μπορούμε να κάνουμε το εξής: υποθέτουμε ότι τα νησιά μας είναι \(N+1\) και όταν έχουμε ερώτημα για \(b\) εισιτήρια, ψάχνουμε για \(b+1\) (ένα παραπάνω) στο segment tree, οπότε ότι απάντηση και να βρούμε, αφαιρούμε ένα νησί. Βέβαια χρειάζεται το segment tree να καλύπτει \(N+1\) νησιά ώστε όταν τα εισιτήρια μας υπερκαλύπτουν μετακίνηση σε όλα τα νησιά, το νησί που αφαιρέσαμε να συνεχίσει να μας δίνει τη σωστή απάντηση \(N\).
Ο επόμενος κώδικας εκτελεί δυαδική αναζήτηση απευθείας στο segment tree βελτιώνοντας την χρονική πολυπλοκότητα της προηγούμενης λύσης σε \(\mathcal{O}(Q\cdot \log{N})\).
long query(long si,long ss,long se,long k){//return pos that spend k tickets
while(ss<se){
pushlazy(si,ss,se);
long mid = (ss+se)/2;
if(st[si*2+1] >= k){//πήγαινε αριστερά
si = si*2+1;
se = mid;
} else {//πήγαινε δεξιά και αφαίρεσε τα χρησιμοποιημένα εισιτήρια των αριστερών νησιών
k -= st[si*2+1];
si = si*2+2;
ss = mid+1;
}
}
return ss;
}
Δείτε ολόκληρο τον κώδικα εδώ.
Λύση με sqrt decomposition (buckets) (45%)
Γνώσεις που θα χρειαστούμε: SQRT Decomposition
Ο κώδικας του sqrt decomposition είναι πιο απλός στη σχεδίαση αλλά όχι τόσο αποδοτικός όσο το segment tree. Χωρίζει τον πίνακα \(Z\) σε \(\sqrt{N}\) διαστήματα (buckets) μεγέθους \(\sqrt{N}\) (εκτός ίσως από το τελευταίο διάστημα που θα είναι μικρότερο). Κάθε ερώτημα θα περιλαμβάνει από \(1\) έως \(\sqrt{N}\) συνεχόμενα buckets. Από τα buckets που αφορούν τo ερώτημα, το αριστερό και το δεξιό ενδέχεται να μην περιλαμβάνονται πλήρως στο ερώτημα, ενώ όλα τα ενδιάμεσα περιλαμβάνονται ολόκληρα. Στα buckets που δεν περιλαμβάνονται πλήρως, κάνουμε brute force στα \(\sqrt{N}\) στοιχεία τους, ενώ στα υπόλοιπα buckets, εκτελούμε σε χρόνο \(\mathcal{O}(1)\) την ενημέρωση/ερώτηση που θέλουμε.
Για να πετύχουμε τις ενημερώσεις/ερωτήσεις ενός bucket σε \(\mathcal{O}(1)\), κρατάμε μια “τεμπέλικη” (lazy) τιμή για το bucket στον πίνακα \(L\) και το άθροισμα του bucket στον πίνακα \(S\). Αν \(L_i=-1\) το bucket \(i\) δεν έχει lazy τιμή. Για να υπολογίσουμε το άθροισμα των στοιχείων του κάνουμε brute force. Αν \(L_i=1\) όλα τα στοιχεία του bucket θεωρείται ότι έχουν τιμή \(1\) (αλλά δεν ξοδεύουμε χρόνο για να τα κάνουμε \(1\)) οπότε το \(S_i\) υπολογίζεται αμέσως καθώς ισούτε με τον αριθμό στοιχείων του bucket. Αν \(L_i=0\) τότε όλα τα στοιχεία του bucket θεωρείται ότι έχουν τιμή \(0\) και το άθροισμα των στοιχείων του bucket είναι \(S_i=0\).
Στα μωβ κουτάκια, απεικονίζονται οι θέσεις του πίνακα Ζ. Στα σκούρα μωβ κουτάκια υπερισχύουν οι τιμές του L (lazy values) του κάθε bucket και αγνοούνται οι τιμές του Ζ. Το άθροισμα S (sum) των στοιχείων του Z για κάθε bucket, είναι πάντα έγκυρο. Με κόκκινο επισημαίνεται το τμήμα που επηρεάζει η πρώτη ανακοίνωση και με πράσινο η δεύτερη.
inline long bucket_no(long pos){ return pos / SQ; }//ποιος ο αριθμός bucket του νησιού pos
inline long bucket_begin(long id){ return (id)*SQ; }//πρώτο νησί του bucket id
inline long bucket_end(long id) { return min(N-1,bucket_begin(id+1)-1); }//τελευταίο νησί του bucket id
void upd(long a,long b,int val){
long b_id=bucket_no(a),l_id=bucket_no(b);//πρώτο και τελευταίο bucket που επηρεάζονται
long x=bucket_begin(b_id), y=bucket_end(b_id);
if(x<a){//από το πρώτο bucket επηρεάζεται τμήμα του μόνο
S[b_id] = 0;//θα επανυπολογίσουμε το άθροισμα
for(long i=x;i<=y;i++){
if(i<a||i>b){
if(L[b_id]!=-1)Z[i]=L[b_id];//κράτα τις τιμές Z[i] που δεν επηρεάζονται
}else {
Z[i]=val;//ενημέρωσε τις τιμές Z[i] που επηρεάζονται
}
S[b_id]+=Z[i];
}
L[b_id]=-1;//δεν υπάρχει κοινή τιμή για όλα τα Z[i] στο bucket
b_id++;
}
while(b_id<=l_id && (y=bucket_end(b_id))<=b){//ενημέρωση ολόκληρων buckets
L[b_id] = val;
S[b_id] = (y-bucket_begin(b_id)+1)*val;
b_id++;
}
if(b_id==l_id){//ενημέρωση τμήματος bucket στο τελευταίο bucket
x = bucket_begin(b_id), y=bucket_end(b_id);
S[b_id]=0;
for(long i=x;i<=y;i++){
if(i<=b)
Z[i] = val;
else if(L[b_id]!=-1)
Z[i] = L[b_id];
S[b_id]+=Z[i];
}
L[b_id]=-1;
}
}
Μπορούμε να απαντάμε τα ερωτήματα του προβλήματος με τη λύση της δυαδικής αναζήτησης για να βρούμε τη μεγαλύτερη τιμή (νησί) που μπορούμε να φτάσουμε με \(b\) εισιτήρια. Ο απαιτούμενος χρόνος είναι της τάξης \(\mathcal{O}(Q\cdot \sqrt{N} \cdot \log{N})\).
a--;//τα Z[i] στα buckets είναι 0-based
b += query(0,a);//μετέτρεψε το ταξίδι από το a σε ταξίδι από το 0
long left = a, right = N-1, ans = a;
while(left<=right){
long mid = (left+right)/2;
if(query(0,mid) > b){
right = mid - 1;//δεν αρκούν τα εισιτήρια για να φτάσουμε στο mid
} else {
ans = mid;//το δεξιότερο νησί που φτάσαμε έως τώρα
left = mid + 1;//ας δοκιμάσουμε ακόμα δεξιότερα
}
}
printf("%ld\n",ans+1);//κάνε την απάντηση 1-based
Δείτε ολόκληρο τον κώδικα εδώ.
Πλήρης λύση με sqrt decomposition (buckets) (100%)
Με μια τροποποίηση του κώδικα του sqrt decomposition μπορούμε να καταργήσουμε τη δυαδική αναζήτηση και να γλυτώσουμε από το λογαριθμικό παράγοντα στην τάξη χρόνου καταλήγοντας σε \(\mathcal{O}(Q\cdot \sqrt{N})\).
long query(long a,long b){
//ξεκινώντας από το νησί a, προσπέρνα νησιά μέχρι να ξοδέψουμε b εισιτήρια
//Είμαστε ήδη στο a, οπότε αρχίζουμε έλεγχο από το a+1
long ans = a, id = bucket_no(a+1), l_id=bucket_no(N-1);
long x = bucket_begin(id), y = bucket_end(id);
if(x < a+1){//Στο πρώτο bucket χρειαζόμαστε μόνο τμήμα του (κάνε brute force στο bucket)
while(ans+1<=y && ((L[id]==0 || (L[id]==-1 && Z[ans+1]==0)) || b-->0))
ans++;
if(ans<y)
id = l_id+1; //Δεν φτάσαμε μέχρι το τέλος του bucket. Εξαντλήσαμε τα εισιτήρια
else
id++;//ολοκληρώσαμε το bucket αυτό και συνεχίζουμε
}
while(id<=l_id && S[id]<=b){//προσπέρνα γρήγορα ολόκληρα buckets
b -= S[id];
ans = bucket_end(id);
id++;
}
x=bucket_begin(id), y=bucket_end(id);
if(id<=l_id){//brute force στο bucket που δεν μπορούμε να προσπεράσουμε ολόκληρο
while(ans+1<=y && ((L[id]==0 || (L[id]==-1 && Z[ans+1]==0)) || b-->0))
ans++;
}
return ans;
}
Δείτε ολόκληρο τον κώδικα εδώ.