PROBLEM LINK:
Practice
Contest
Author: Mohit Wadhwa
Tester: Parth Mittal
Editorialist: Parth Mittal
DIFFICULTY:
MEDIUMHARD
PREREQUISITES:
Segment Trees
PROBLEM:
Given numeric string $str$ where $str_i \in \{0..9\}$. We call $(x_1, x_2, x_3, x_4)$ quadruple a palindromic quadruple of string $S$ if it satisfies the following criteria : $S_{x_1} = S_{x_4}$ and $S_{x_2} = S_{x_3}$ where $x1 < x2 < x3 < x4$. Queries are:
1 i j
: Print number of different palindromic quadruples $(x_1, x_2, x_3, x_4)$ for string $str$ such that $i ≤ x1 < x2 < x3 < x4 ≤ j$. $\mod 10^9 + 7$.
2 idx ch
: Replace $str_{idx}$ with character $ch$.
EXPLANATION:
We can use a segment tree with some clever information in the nodes to solve this task.
Let's say we already know the answer for the two children of a node, then what additional information do we need to compute the answer for this node?
We are looking for subsequences of the kind abba
, where $a, b \in \left\{0, 1, \dots , 9\right\}$. Possibilities are:

abba
in left child

abba
in right child

a
in left child, bba
in right child (and its symmetric case)

ab
in left child, ba
in right child.
So we need to store number of ways to generate these for each node too.
Note that to compute these, we need no more additional information.
Hence we have an $O(N\log N \times \texttt{alpha}^2)$ solution, where $\texttt{alpha}$ is the size of the alphabet.
asked
12 Oct '16, 23:14
2★rounaqwl66
26●3
accept rate:
25%