Problem Link:
Practice
Contest
Difficulty:
Hard
Prerequisites:
Splay Trees
Problem:
Given a suffix array, find the number of strings that correpond to it. The suffix array can be obtained by applying some operations(see problem for details).
Explanation:
The problem can be broken into two parts:
 Constructing the suffix array from queries.
 Given the suffix array, find the number of strings that correspond to it.
We will first solve the easy part, finding number of strings.
Given a Suffix Array find number of strings
Let the suffix array be a_{1}, a_{2}, ... a_{n}.
Let S be an arbitrary string corresponding to the given suffix array.
Let
S[i] = i^{th} character of the string
Suffix[i] = suffix of S starting from i^{th} character.
We must have
S[a_{1}] ≤ S[a_{2}] ≤ S[a_{3}] ... ≤ S[a_{n}]  (1)
Also, by our definition of "string", if S[a_{i}] < S[a_{i+1}], then S[a_{i+1}] = S[a_{i}] + 1.
Therefore, if we replace each '≤' by exactly one out of '=' and '<', we will get a unique string.
Also, if each '≤' had full "freedom" of choosing exactly one out of '<' and '=', then number of strings for a given suffix array would be 2^{n1}.
However, world is not such a nice place. Any '≤' can always be replaced by '<', but it might not possible to replace it by '='. So lets try to see when a '≤' cannot be replaced by '='.
Consider an arbitrary '≤', S[a_{i}] ≤ S[a_{i+1}], and lets see what happens when we replace it by '='.
By suffix array condition, we have
Suffix[a_{i}] < Suffix[a_{i+1}].
But S[a_{i}] = S[a_{i+1}]
So, we should have Suffix[a_{i}+1] < Suffix[a_{i+1}+1]
Therefore, the '≤' between S[a_{i}] and S[a_{i+1}] can be replaced by '=' iff a_{i}+1 appears before a_{i+1}+1 in the suffix array. The answer will be 2^{k} where
k = no of positions i such that a_{i}+1 appears before a_{i+1}+1 in the suffix array

To handle the case where a_{i} = N or a_{i+1} = N, we can append(conceptually) '0' to the of string, and rewrite the suffix array as
n+1, a_{1}, a_{2}, ... a_{n}

Since the suffix array is very large, we will actually obtain it in the form:
(x_{1}, y_{1}), (x_{2}, y_{2}), ... (x_{k}, y_{k})
Where each (x_{i}, y_{i}) represents an AP starting at x_{i}, ending at y_{i}, with common difference ±1.
It can be verified if both a_{i} and a_{i+1} are not boundary of some contiguous segment(i.e. do not belong to the set { x_{1}, y_{1}, x_{2}, y_{2}, ... x_{k}, y_{k} }), then a_{i}+1 appears before a_{i+1}+1. So, we have to only check at boundaries of segments, which are O(k) in number.
It is non trivial to find the position of a_{i}+1 's. However, to check the order of two arbitrary elements in suffix array, we only need to check
 If they belong to same contiguous segment, then what is their order in the segment.
 If they belong to different segments, then what is the order of those segments.
This can be done using STL's map data structure as m[x_{i}] = m[y_{i}] = i, and using lower_bound to locate the relative position of segments in which they lie.
Obtaining the suffix array
We need to implement the two operations : flip ranges and move ranges to front.
This can be done using balanced binary trees(splay trees). Each node in the tree will store a range of consecutive numbers from u to v (u may larger than v).
At the beginning our tree contains only single node which is (1, n).
At any time, the nodes of the tree form a disjoin partition of the range (1,n).
Every node has:
 int u, v: indicate the range(u, v).
 int num: the subtree rooted at this node has total of num array elements.
 bool flip: the entire subtree rooted at this node is flipped. This will be propagated down in lazy manner.
A fliprange, or moverangetofront operation may need to split at most 2 nodes(for beginning and end of operation's range), so do that first.
Use splay operation to obtain a subtree that corresponds to the given range.
 Flip operation: Flip that range by updating flip flag on the node.
 Move the range to front: Can be done by shuffling O(1) nodes of the tree.
Setter's Solution:
Can be found here
Tester's Solution:
Can be found here