×

# PRCS16E - Editorial

Tester: Parth Mittal
Editorialist: Parth Mittal

MEDIUM-HARD

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.

This question is marked "community wiki".

263
accept rate: 25%

19.7k350498541

 toggle preview community wiki:
Preview

By Email:

Markdown Basics

• *italic* or _italic_
• **bold** or __bold__
• image?![alt text](/path/img.jpg "title")
• numbered list: 1. Foo 2. Bar
• to add a line break simply add two spaces to where you would like the new line to be.
• basic HTML tags are also supported
• mathemetical formulas in Latex between \$ symbol

Question tags:

×15,480
×1,726
×1,236
×21
×1

question asked: 12 Oct '16, 23:14

question was seen: 595 times

last updated: 02 Jan '17, 19:18