Ψηφιακό Κύκλωμα

Υπάρχει ένα κύκλωμα, το οποίο αποτελείται από ~N + M~ πύλες αριθμημένες από ~0~ εώς ~N + M - 1~. Οι πύλες ~0~ εώς ~N - 1~ είναι πύλες ορίων, ενώ οι πύλες ~N~ εώς ~N + M - 1~ είναι πύλες πηγής.

Κάθε πύλη, εκτός από την πύλη ~0~, είναι είσοδος σε ακριβώς μία πύλη ορίων. Συγκεκριμένα, για κάθε ~i~ τέτοιο ώστε ~1 \le i \le N + M - 1~, η πύλη ~i~ είναι μια είσοδος στην πύλη ~P[i]~, όπου ~0 \le P[i] \le N-1~. Είναι σημαντικό ότι έχουμε επίσης ~P[i] < i~. Επιπρόσθετα, θα υποθέτουμε ότι το P[0] = -1. Κάθε πύλη ορίου έχει μία ή περισσότερες εισόδους. Οι πύλες πηγής δεν έχουν εισόδους.

Κάθε πύλη έχει μια κατάσταση που είναι είτε ~0~ είτε ~1~. Οι αρχικές καταστάσεις των πυλών πηγής δίνονται από έναν πίνακα ~A~ ο οποίος περιέχει ~M~ ακέραιους αριθμούς. Δηλαδή, για κάθε ~j~ τέτοιο ώστε ~0 \le j \le M - 1~, η αρχική κατάσταση της πύλης πηγής ~N + j~ είναι ~A[j]~.

Η κατάσταση κάθε πύλης ορίου εξαρτάται από τις καταστάσεις των εισόδων της και καθορίζεται ως εξής. Πρώτον, σε κάθε πύλη ορίου εκχωρείται μια παράμετρος ορίου. Η παράμετρος που εκχωρείται σε μια πύλη ορίου με ~c~ εισόδους πρέπει να είναι ένας ακέραιος αριθμός μεταξύ ~1~ και ~c~ (συμπεριλαμβανομένων). Τότε, η κατάσταση μιας πύλης ορίου με παράμετρο ~p~ είναι ~1~, εάν τουλάχιστον ~p~ από τις εισόδους της είναι ~1~, διαφορετικά είναι ~0~.

Για παράδειγμα, ας υποθέσουμε ότι υπάρχουν ~N = 3~ πύλες ορίων και ~M = 4~ πύλες πηγής. Οι είσοδοι στην πύλη ~0~ είναι οι πύλες ~1~ και ~6~, οι είσοδοι στην πύλη ~1~ είναι οι πύλες ~2~, ~4~ και ~5~ και η μόνη είσοδος στην πύλη ~2~ είναι η πύλη ~3~.

Αυτό το παράδειγμα απεικονίζεται στο επόμενο σχήμα.

Ας υποθέσουμε ότι οι πύλες πηγής ~3~ και ~5~ έχουν κατάσταση ~1~, ενώ οι πύλες πηγής ~4~ και ~6~ έχουν κατάσταση ~0~. Ας υποθέσουμε ότι εκχωρούμε τις παραμέτρους ~1~, ~2~ και ~2~ στις πύλες ορίων ~2~, ~1~ και ~0~ αντίστοιχα. Σε αυτήν την περίπτωση, η πύλη ~2~ έχει κατάσταση ~1~, η πύλη ~1~ έχει κατάσταση ~1~ και η πύλη ~0~ έχει κατάσταση ~0~. Η συγκεκριμένη εκχώρηση των τιμών των παραμέτρων και των καταστάσεων απεικονίζεται στο επόμενο σχήμα. Οι πύλες των οποίων η κατάσταση είναι ~1~ σημειώνονται με μαύρο χρώμα.

Οι καταστάσεις των πυλών πηγής θα υποβληθούν σε ~Q~ ενημερώσεις (updates). Κάθε ενημέρωση περιγράφεται από δύο ακέραιους αριθμούς ~L~ και ~R~ (~N \le L \le R \le N + M - 1~) και εναλλάσσει (toggles) τις καταστάσεις όλων των πυλών πηγής που αριθμούνται μεταξύ ~L~ και ~R~, συμπεριλαμβανομένων. Δηλαδή, για κάθε ~i~ τέτοιο ώστε το ~L \le i \le R~, η πύλη πηγής ~i~ αλλάζει την κατάστασή της σε ~1~, εάν η κατάστασή της είναι ~0~ ή σε ~0~, εάν η κατάστασή της είναι ~1~ . Η νέα κατάσταση κάθε πύλης που έχει εναλλαγεί (toggled gate) παραμένει αμετάβλητη έως ότου γίνει πιθανή εναλλαγή από κάποια μεταγενέστερη ενημέρωση.

Ο στόχος σας είναι να μετράτε, μετά από κάθε ενημέρωση, πόσες διαφορετικές εκχωρήσεις παραμέτρων σε πύλες ορίων έχουν ως αποτέλεσμα η πύλη ~0~ να έχει κατάσταση ~1~. Δύο εκχωρήσεις θεωρούνται διαφορετικές εάν υπάρχει τουλάχιστον μία πύλη ορίου που έχει διαφορετική τιμή της παραμέτρου της και στις δύο εκχωρήσεις. Καθώς το πλήθος των τρόπων μπορεί να είναι μεγάλος, θα πρέπει να τον υπολογίσετε ως modulo ~1\;000\;002\;022~.

Σημειώστε ότι στο παραπάνω παράδειγμα, υπάρχουν ~6~ διαφορετικές εκχωρήσεις παραμέτρων στις πύλες ορίων, καθώς οι πύλες ~0~, ~1~ και ~2~ έχουν εισόδους ~2~, ~3~ και ~1~ αντίστοιχα. Σε ~2~ από αυτές τις ~6~ αναθέσεις, η πύλη ~0~ έχει την κατάσταση ~1~.

Λεπτομέρειες Υλοποίησης

Να υλοποιήσετε τις δύο διαδικασίες.

void init(int N, int M, int[] P, int[] A)

• ~N~ : ο αριθμός των πυλών ορίων.
• ~M~ : ο αριθμός των πυλών πηγής.
• ~P~ : ένας πίνακας μήκους ~N + M~ που περιγράφει τις εισόδους στις πύλες ορίων.
• ~A~ : ένας πίνακας μήκους ~M~ που περιγράφει τις αρχικές καταστάσεις των πυλών πηγής.
• Αυτή η διαδικασία καλείται ακριβώς μία φορά, πριν από οποιαδήποτε κλήση της count_ways.

int count_ways(int L, int R)

• ~L~, ~R~ : τα όρια του εύρους των πυλών πηγής, των οποίων οι καταστάσεις εναλλάσσονται.
• Αυτή η διαδικασία θα πρέπει πρώτα να εκτελέσει την καθορισμένη ενημέρωση και, στη συνέχεια, να επιστρέψει τον αριθμό (πλήθος) των τρόπων, modulo ~1\;000\;002\;022~, για την εκχώρηση παραμέτρων στις πύλες ορίων, με αποτέλεσμα η πύλη ~0~ να έχει την κατάσταση ~1~.
• Αυτή η διαδικασία καλείται ακριβώς ~Q~ φορές.

Παράδειγμα

Θεωρείστε την ακόλουθη σειρά κλήσεων:

init(3, 4, [-1, 0, 1, 2, 1, 1, 0], [1, 0, 1, 0])

Αυτό το παράδειγμα απεικονίζεται στην παραπάνω περιγραφή του προβλήματος.

count_ways(3, 4)

Αυτό αλλάζει τις καταστάσεις των πυλών ~3~ και ~4~, δηλαδή η κατάσταση της πύλης ~3~ γίνεται ~0~ και η κατάσταση της πύλης ~4~ γίνεται ~1~. Δύο τρόποι εκχώρησης των παραμέτρων που έχουν ως αποτέλεσμα η πύλη ~0~ να έχει την κατάσταση ~1~ απεικονίζονται στα επόμενα σχήματα.

Σε όλες τις άλλες εκχωρήσεις παραμέτρων, η πύλη ~0~ έχει κατάσταση ~0~. Έτσι, η διαδικασία θα πρέπει να επιστρέψει ~2~.

count_ways(4, 5)

Αυτό αλλάζει τις καταστάσεις των πυλών ~4~ και ~5~. Ως αποτέλεσμα, όλες οι πύλες πηγής έχουν κατάσταση ~0~ και για οποιαδήποτε εκχώρηση παραμέτρων, η πύλη ~0~ έχει κατάσταση ~0~. Έτσι, η διαδικασία θα πρέπει να επιστρέψει ~0~.

count_ways(3, 6)

Αυτό αλλάζει τις καταστάσεις όλων των πυλών πηγής σε ~1~. Ως αποτέλεσμα, για οποιαδήποτε εκχώρηση παραμέτρων, η πύλη ~0~ έχει κατάσταση ~1~. Έτσι, η διαδικασία θα πρέπει να επιστρέψει ~6~.

Περιορισμοί

• ~1 \le N, M \le 100\;000~
• ~1 \le Q \le 100\;000~
• ~P[0] = -1~
• ~0 \le P[i] < i~ και ~P[i] \le N - 1~ (για κάθε ~i~ τέτοιο ώστε ~1 \le i \le N + M - 1~)
• Κάθε πύλη ορίου έχει τουλάχιστον μία είσοδο (για κάθε ~i~ όπου ~0 \le i \le N - 1~ υπάρχει ένας δείκτης ~x~ τέτοιος ώστε ~i < x \le N + M - 1~ και ~P[x] = i~).
• ~0 \le A[j] \le 1~ (για κάθε ~j~ τέτοιο ώστε ~0 \le j \le M - 1~)
• ~N \le L \le R \le N + M - 1~

Υποπροβλήματα

1. (2 βαθμοί) ~N = 1~, ~M \le 1000~, ~Q \le 5~
2. (7 βαθμοί) ~N, M \le 1000~, ~Q \le 5~, κάθε πύλη ορίου έχει ακριβώς δύο εισόδους.
3. (9 βαθμοί) ~N, M \le 1000~, ~Q \le 5~
4. (4 βαθμοί) ~M = N + 1~, ~M = 2^z~ (για κάποιο θετικό ακέραιο ~z~), ~P[i] = \lfloor\frac{i - 1}{2}\rfloor~ (για κάθε ~i~ τέτοιο ώστε ~1 \le i \le N + M - 1~), ~L = R~
5. (12 βαθμοί) ~M = N + 1~, ~M = 2^z~ (για κάποιο θετικό ακέραιο ~z~), ~P[i] = \lfloor\frac{i - 1}{2}\rfloor~ (για κάθε ~i~ τέτοιο ώστε ~1 \le i \le N + M - 1~)
6. (27 βαθμοί) Κάθε πύλη ορίου έχει ακριβώς δύο εισόδους.
7. (28 βαθμοί) ~N, M \le 5000~
8. (11 βαθμοί) Κανένας επιπλέον περιορισμός

Υπόδειγμα Βαθμολογητή

Ο βαθμολογητής διαβάζει την είσοδο στην ακόλουθη μορφή:

• line ~1~: ~N \; M \; Q~
• line ~2~: ~P[0] \; P[1] \; \ldots \; P[N + M - 1]~
• line ~3~: ~A[0] \; A[1] \; \ldots \; A[M - 1]~
• line ~4 + k~ (~0 \le k \le Q - 1~) : ~L \; R~ για την ενημέρωση ~k~

Ο βαθμολογητής εκτυπώνει τις απαντήσεις σας στην ακόλουθη μορφή:

• γραμμή ~1 + k~ (~0 \le k \le Q - 1~) : η τιμή επιστροφής της count_ways για την ενημέρωση ~k~