Problem Description

Given a string $s$ of length $n$, for a sequence $D=([l_1,r_1],\cdots,[l_k,r_k])$, define $F(D)=s[l_1,r_1]+\cdots+s[l_k,r_k]$.

We maintain a multiset $S$. There are $q$ operations of three types:

• $1\;D$: Insert $F(D)$ into $S$.
• $2\;t$: Undo the $t$-th operation (guaranteed to be type 1).
• $3\;D_1\;D_2$: Query how many strings in $S$ have $F(D_1)$ as a prefix and $F(D_2)$ as a suffix.

Constraints

$1\le n,q\le 10^5$

$1\le l_i\le r_i\le n$

$\sum |D|\le 3\times 10^5$

$6\text{s},1\text{GB}$

Solution

Assume $n,q,\sum|D|$ are of the same order.

If each string were given directly, this is a classic problem. Build tries for the original and reversed strings. The constraints mean that strings in $S$ lie in the subtree of the query strings. Mapping to DFS order gives 2D range counting. With insertions and deletions, adding a time dimension allows CDQ divide-and-conquer, giving $O(n\log^2 n)$ complexity.

However, building the tries directly is impractical. Since we only need the nodes at the ends of strings, we can build their virtual tree and compute DFS order. First, we need to sort the strings lexicographically. Build the suffix array of $s$, then we can compute LCP to compare two intervals in $O(1)$. Using two pointers, we can compare $F(D_1)$ and $F(D_2)$ in $O(|D_1|+|D_2|)$.

Direct sort would be too slow. Instead, sort all $D$ by total string length ascending, then insert them into a set for automatic sorting. This yields $O(n\log n)$ complexity.

After sorting, we can compute the LCP array between adjacent $F(D)$. Using a monotonic stack, we obtain the subtree DFS order intervals $[\text{L}_i,\text{R}_i]$ for each node. Finally, apply the approach from the beginning to compute answers.