PRCS16E - Editorial

editorial
, , , ,
1

PROBLEM LINK:

Practice
Contest

Author: Mohit Wadhwa
Tester: Parth Mittal
Editorialist: Parth Mittal

DIFFICULTY:

MEDIUM-HARD

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 sub-sequences 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.