PROBLEM LINK:
Author: Ildar Gainullin
Tester: Oleksandr Kulkov
Editorialist: Oleksandr Kulkov
DIFFICULTY:
MEDIUM-HARD
PREREQUISITES:
persistent segment tree and hashes OR bitsets
PROBLEM:
You are to proccess q queries of inversing bits on subsegments in bit sequence and output the lexicographically maximal sequence among all you got.
QUICK EXPLANATION:
You can recalculate hashes in persistent segment tree after each query and then choose maximum among current best found sequence and the current computed one by computing their lcp in O(\log n).
EXPLANATION:
Considering that we can calculate the hashes of two strings quickly, we can also compare them lexycographically by binary searching their largest common prefix (lcp) and checking the character right after it.
Let’s maintain polynomial hash of kind \sum\limits_{i=1}^n s_i x^i in persistent segment tree. To provide inversion queries in the vertex we can precalculate hashes for strings consisting of only 1's and then to change hash in vertex from h_v to \sum\limits_{k=l}^r x^k - h_v and push inversion query into the children of the current vertex.
Now the only thing left is to implement all this which turns out to be pretty tedious. Please refer to the solution code for better understanding of technical details.
ALTERNATIVE SOLUTION:
You can also solve this problem in O\left(\dfrac{n^2}{32}\right) using bitsets.
AUTHOR’S AND TESTER’S SOLUTIONS:
Author’s solution can be found here.
Tester’s solution can be found here.