PROBLEM LINK:
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.