PROBLEM LINK:
Author: Tadija Sebez, Yahor Dubovik
Tester: Takuki Kurokawa, Nishant
Editorialist: Srikkanth R
DIFFICULTY:
Medium-Hard
PREREQUISITES:
Palindrome Trees, 2D Data Structures, Subtree Sum Queries, Binary Lifting
PROBLEM:
You are given a string S[1..N] of length N. Let ST[1..M] be the set of palindromes of S (if a palindrome occurs multiple times, it is counted only once).
Every palindrome in the set ST has an associated integer value that is initially zero.
Answer Q of the following queries.
-
1 \ L \ R \ P \ X : Add X to the value of every palindrome that
- (i) can be expressed as T + S[L..R] + rev(T) for some (possibly empty) string T, and
- (ii) are substrings of the prefix S[1..P]
- 2 \ L \ R : Print the value of the palindrome S[L..R].
- It is guaranteed that S[L..R] is a palindrome for all queries.
QUICK EXPLANATION:
We first build the palindrome tree PT of the given string S. Let \texttt{node}(S) be the node of the palindrome tree corresponding to the palindrome S.
The set of palindrome strings that can be expressed as T + S[L..R] + rev(T) correspond to nodes in the subtree of \texttt{node}(S[L..R]).
In order to answer subtree queries, we order the nodes of PT in dfs order.
Let \texttt{dfs\_in}[i] be the number of nodes visited before \texttt{node}(ST[i]) is visited for the first time in dfs order and similarly define \texttt{dfs\_out}[i].
If we represent each palindrome ST[i] as a point in 2D, say (x, y) where
- x is the smallest R such that ST[i] = S[L..R] for some L (i.e. the first occurrence of ST[i] in the string S)
- y is the index of \texttt{node}(ST[i]) in any valid dfs ordering of the tree PT
then, the first query can be rewritten as
- Add X to all points (a, b) such that 1 \leq a \leq P and \texttt{dfs\_in}[i] \leq b \leq \texttt{dfs\_out}[i]
For the second query we simply need evaluate the value of the point (x, y).
Both these queries can be implemented as a 2D version of any (point update - range query) data structure (such as segment tree or binary indexed tree) .
The only part left is to find which palindrome the string S[L..R] belongs to, i.e. compute \texttt{node}(S[L..R]). As palindromes can occur multiple times, this is not trivial to do. A simple approach might be to use rolling hashes, however we can make use of the already constructed palindrome tree.
We already determine (while constructing the palindrome tree) the node corresponding to the largest palindrome ending at R for every R = 1, 2, \dots N. Furthermore we also have suffix links pointing towards the next largest palindrome ending at R. Therefore we can follow the suffix links until we obtain a string with the same length as S[L..R] which would be the desired node. To speed up the process, we can use binary lifting over the suffix links to compute such a node in O(\log N) time.
EXPLANATION:
Prerequisites : Palindrome Tree
We strongly recommend that you learn about palindrome trees in detail (for example from adilet’s blog).
For convenience, we describe here what the palindromic tree is and the useful by products of the algorithm to compute it (only the essential details).
A palindromic tree is a “trie-like” data structure of a string S[1..N] with the following properties
- Every palindromic substring of S corresponds to a node of the tree.
- For convenience let \texttt{node}(S[L..R]) be the node of the tree corresponding to the palindromic substring S[L..R]. Note that even if a substring occurs more than once, there is only a single node corresponding to this string. Whenever we refer to \texttt{node}(A) for a string A, it should be understood that A is a palindromic substring of S.
- There is a directed edge with label c from \texttt{node}(A) to \texttt{node}(B) if B = c A c (for some character c and palindromic substrings A, B).
- For every node we also store links (called suffix links) to longest proper suffixes, i.e. \texttt{sufLink}(\texttt{node}(A)) = \texttt{node}(B) if B is the longest proper suffix of A.
- The total number of nodes in the tree is at most N + 2. A clear consequence of this is that there are at most N+2 distinct palindromic substrings of S (you may try to prove this for yourself, there are at most N are non-empty palindromic substrings).
- We cannot afford to store the entire substring inside the node that it represents (this can lead to O(N^2) space for even the simple string aa\dots a), however we can store starting and ending indices of the first occurrence of the substring.
- The data structure can be built using only O(N) space and in O(N) time.
- Additionally we also have for every R = 1, 2, \dots N, the (node corresponding to) longest suffix of S[1..R] that is a palindromic substring
Mapping substrings to palindromes
The queries given refer to the palindromes as substrings S[L..R]. The palindromic tree computed only has the first occurrence of these palindromes, not all of them.
So we will need to identify the nodes in the palindromic tree correspond to the given query so that we may use properties of the palindromic tree to solve the problem.
We know for every R, the node corresponding to the longest suffix of S[1..R] that is a palindrome (this is a by product of the algorithm to compute the tree). Let this node be \texttt{LSuffix}(R).
The suffix link from \texttt{LSuffix(R)} gets you to the second longest suffix of S[1..R] that is a palindrome. Following the suffix link from that we can obtain the third largest suffix and so on. We can enumerate all suffixes of S[1..R] that are palindromes by simply iterating through the suffix links until we get a string with the same length as S[L..R], which is our desired node. While this solution works it is too slow as it can take O(N) in some cases (the simplest example of this is the string aa\dots a).
To optimize this process we can use “binary lifting” to reach the desired string quickly. For every node we calculate the (2^j)^{th} suffix link ancestor (the node obtained by following the suffix link 2^j times). This can be calculated for all j = 0, 1, \dots \log N and for each node i in O(N \log N) time by applying the following recursive formula while performing a dfs traversal of the tree
$$ k = \texttt{sufLinkJmp}[j-1][i]$$
$$ \texttt{sufLinkJmp}[j][i] = \texttt{sufLinkJmp}[j-1][k] \text{ for all } j > 0$$
$$ \texttt{sufLinkJmp}[0][i] = \texttt{sufLink}[i]$$
Once these jump values are calculated, we can binary search for the desired ancester as follows,
for j = lgN ... 0 do
if sufLinkJmp[j][i] has length greater than or equal to R - L + 1
i = sufLinkJmp[j][i]
// The value of i obtained after the above for loop is the desired node
Intuitively we are “jumping” as much as possible until we reach the desired node. Another way to think about it is that if the number of suffix link jumps to be performed is d then we can represent d in binary as a sum of power of twos, and for every power of two we can use the precomputed values to jump that many steps in a single iteration. Thus in O(\log N) steps we can obtain the node in the tree corresponding to any given palindromic substring S[L..R].
Finding strings that satisfy condition (i) of query 1
Let T be any substring t_0 t_1 \dots t_{k}. The nodes we are interested in are those of the form T + S[L..R] + rev(T) = t_0 t_1 \dots t_k S[L..R] t_k t_{k-1} \dots t_1 t_0.
By definition of the palindrome tree, we know that there will exist edges S[L..R] \rightarrow t_k S[L..R] t_{k} \rightarrow t_{k-1} t_k S[L..R] t_{k} t_{k-1} \dots T S[L..R] rev(T). Clearly S[L..R] is the ancestor of T S[L..R] rev(T). Therefore all the nodes corresponding to our candidate strings are in the subtree of node S[L..R].
A well known technique to handle subtree queries is to order the nodes as per a dfs traversal. The ordering is obtained by starting out with an empty array (say A) and performing a dfs traversal over the tree. Whenever a node is visited for the first time, append it to the end of A. For each node, store \texttt{dfs\_in}[i] as the index of the node i in the array A. The value \texttt{dfs\_out}[i] is computed as the index of the last element in the array A when the recursive call for dfs finishes at node i (at this time all nodes in the subtree of node i have been visited). The nodes in the subtree of i form a contiguous subarray of A, namely from A[\texttt{dfs\_in}[i]] ... A[\texttt{dfs\_out}[i]]. So to handle queries like “Add X to every node in subtree of i” may now be handled by “Add X to the contiguous subarray of A”.
Finding strings that satisfy condition (ii) of query 1
The algorithm to compute the palindromic tree starts of by initializing a tree for the empty string and then reads the string character by character. Once a new palindromic substring is found, a new node is created for it and then it is added to the tree (along with the necessary tree edges and suffix links). Therefore we have the first occurrence of every palindrome.
Consider the list ST[1..M] of palindromes which are ordered by the first time they are found by the algorithm. The strings that satisfy condition (ii) form a prefix of this array ST[1..M]. Similar to strings satisfying condition (i), these strings are also contiguous subarrays.
Query 1 is a 2D range sum
If we consider the 2D grid and associate each palindrome S[L..R] with the point (x, y) such that
- x is the index of S[L..R] when the palindromes are sorted according to their occurrence (when the string is read from left to right)
- y is the index in the dfs ordering
Query 1 asks to add X to every point (x, y) such that 1 \leq x \leq P and \texttt{dfs\_in}[i] \leq y \leq \texttt{dfs\_out}[i].
Query 2 asks to find the value of the point (x, y) corresponding to the string S[L..R]. We already discussed how to compute x, y from L, R efficiently in the preceding steps.
These queries can be handled by 2D data structures such as a 2D segment tree or binary indexed tree.
2D data structures
A 2D segment tree is built by first splitting on the x coordinate, i.e. build a usual segment tree wherein a node corresponding to an interval [l, r] now contains all points with x coordinates between l, r.
Now within each node build another segment tree based on the y co-ordinate. Each point (x, y) contributes to at most O(\log^2 N) inner segment tree nodes.
While supporting lazy propagation on such a segment tree is hard to do efficiently, we can overcome lazy propagation by transforming (range updates and point queries) to (point updates and range queries).
Suppose we need to perform range updates and point queries on a grid g[x][y]. Consider the grid h[x][y] = g[x][y] - g[x-1][y] - g[x][y-1] + g[x-1][y-1]. The value g[x][y] can be obtained from h[x][y] by adding all the values in the grid [0, x] \times [0, y].
When the query of type 1, “Add X to the rectangle with bottom left corner (l_1, r_1) and top right corner (l_2, r_2)” is performed on the grid g, only four terms of the grid h are changed, namely h[l_1][r_1], h[l_2 + 1][r_1], h[l_1][r_2 + 1] and h[l_2+1][r_2+1]. This operation can be done as 4 point updates on the 2D segment tree over h.
The second query of type 1, is then a sum of a sub-rectangle of the grid h (namely the grid [0, x] \times [0, y]) which can be obtained by adding O(\log^2 N) nodes of the inner segment tree.
TIME COMPLEXITY : O((N + Q) \log^2 N)
SPACE COMPLEXITY : O(N \log N)
SOLUTIONS:
Tester's Code
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
using namespace __gnu_pbds;
using namespace std;
const int RANDOM = chrono::high_resolution_clock::now().time_since_epoch().count();
struct chash {
int operator()(int x) const { return x ^ RANDOM; }
};
#define int long long
#define pb push_back
#define fast ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0)
const int P1 = 31;
const int MOD1 = 1e9 + 7;
const int P2 = 37;
const int MOD2 = 1e9 + 9;
const int N = 1e5 + 100;
const int sigma = 26;
string S;
vector<int> ptree[N]; //palindromic tree
int st[N], en[N]; //indices of substring that they represent
int timer = 0;
int tin[N], tout[N];
void dfs(int node, int par = -1) {
tin[node] = timer++;
for (auto x : ptree[node]) {
if (x != par) dfs(x, node);
}
tout[node] = timer - 1;
}
namespace palindrome_tree
{
//we also know that ith node represents S[st[i] ... en[i]]
int s[N], len[N], link[N], to[N][sigma];
int n, last, sz;
void init()
{
s[n++] = -1;
link[0] = 1;
len[1] = -1;
sz = 2;
}
int get_link(int v)
{
while (s[n - len[v] - 2] != s[n - 1]) v = link[v];
return v;
}
void add_letter(int c)
{
s[n++] = c;
last = get_link(last);
if (!to[last][c])
{
len[sz] = len[last] + 2;
en[sz] = n - 2;
st[sz] = en[sz] - len[sz] + 1;
link[sz] = to[get_link(link[last])][c];
to[last][c] = sz++;
}
last = to[last][c];
}
//create explicite tree
void process() {
for (int i = 0;i < sz;i++) {
for (int j = 0;j < sigma;j++) {
if (to[i][j] > 0) {
ptree[i].push_back(to[i][j]);
}
}
}
}
};
struct Hashs
{
vector<int> hashs;
vector<int> pows;
int P;
int MOD;
Hashs() {}
Hashs(string& s, int P, int MOD) : P(P), MOD(MOD)
{
int n = s.size();
pows.resize(n + 1, 0);
hashs.resize(n + 1, 0);
pows[0] = 1;
for (int i = n - 1;i >= 0;i--)
{
hashs[i] = (1LL * hashs[i + 1] * P + s[i] - 'a' + 1) % MOD;
pows[n - i] = (1LL * pows[n - i - 1] * P) % MOD;
}
pows[n] = (1LL * pows[n - 1] * P) % MOD;
}
int get_hash(int l, int r)
{
int ans = hashs[l] + MOD - (1LL * hashs[r + 1] * pows[r - l + 1]) % MOD;
ans %= MOD;
return ans;
}
};
struct node;
node* newNode();
struct node {
int lv, rv, sum;
node* left, * right;
node() : left(NULL), right(NULL), sum(0) {}
inline void init(int l, int r) {
lv = l;
rv = r;
}
inline void extend() {
if (!left) {
int m = (lv + rv) / 2;
left = newNode();
right = newNode();
left->init(lv, m);
right->init(m + 1, rv);
}
}
int query(int l, int r) {
if (r < lv || rv < l) {
return 0;
}
if (l <= lv && rv <= r) {
return sum;
}
extend();
return left->query(l, r) + right->query(l, r);
}
void modify(int p, int newVal) {
if (lv == rv) {
sum += newVal;
return;
}
extend();
(p <= left->rv ? left : right)->modify(p, newVal);
sum = left->sum + right->sum;
}
};
node* newNode() {
static int bufSize = 2e7;
static node buf[(int)2e7];
assert(bufSize);
return &buf[--bufSize];
}
node* ST[4 * N];
//add value y to indices in range l to r for all subnodes <= x
void update(int node, int ss, int se, int l, int r, int x, int y) {
if (ss > r || se < l) return;
if (l <= ss && se <= r) {
ST[node]->modify(x, y);
return;
}
int mid = (ss + se) / 2;
update(node * 2 + 1, ss, mid, l, r, x, y);
update(node * 2 + 2, mid + 1, se, l, r, x, y);
}
//Find value of a node at index x if it ends at y
int query(int node, int ss, int se, int x, int y) {
if (ss > x || se < x) return 0;
int res = ST[node]->query(y, N - 1);
if (ss != se)
{
int mid = (ss + se) / 2;
if (x <= mid) res += query(node * 2 + 1, ss, mid, x, y);
else res += query(node * 2 + 2, mid + 1, se, x, y);
}
return res;
}
signed main()
{
fast;
cin >> S;
//create palindromic tree
palindrome_tree::init();
for (auto x : S) palindrome_tree::add_letter(x - 'a');
palindrome_tree::process();
//perform euler tour on tree
dfs(0);
dfs(1);
//also store the hashes to map string [L...R] to node in palindromic tree
Hashs go1(S, P1, MOD1), go2(S, P2, MOD2);
map<pair<int, int>, int > mapping;
for (int i = 1;i < palindrome_tree::sz;i++) {
int h1 = go1.get_hash(st[i], en[i]);
int h2 = go2.get_hash(st[i], en[i]);
mapping[{h1, h2}] = i;
}
//init segtree
for (int i = 0;i < 4 * N;i++) {
ST[i] = newNode();
ST[i]->init(0, N - 1);
}
int q;
cin >> q;
while (q--)
{
int t, l, r, p, x;
cin >> t >> l >> r;
l--, r--;
//Find the node in palindromic tree for S[L...R]
int h1 = go1.get_hash(l, r);
int h2 = go2.get_hash(l, r);
int node_id = mapping[{h1, h2}];
assert(mapping.find({ h1, h2 }) != mapping.end());
if (t == 1) {
cin >> p >> x;
p--;
update(0, 0, N - 1, tin[node_id], tout[node_id], p, x);
}
else {
cout << query(0, 0, N - 1, tin[node_id], en[node_id]) << '\n';
}
}
}
Setter's Code
#ifdef DEBUG
#define _GLIBCXX_DEBUG
#endif
//#pragma GCC optimize(“O3”)
#include <bits/stdc++.h>
using namespace std;
typedef long double ld;
typedef long long ll;
struct node {
int nxt[26];
int len;
int link;
int pref;
node() {
memset(nxt, -1, sizeof nxt);
len = -1;
link = -1;
}
};
string s, q;
const int maxN = 1e5 + 10;
node c[maxN + 10];
int lst;
int sz = 0;
int for_pref[maxN + 10];
void add_letter(int pos, char p) {
int state = lst;
while (state != -1 && q[pos - c[state].len - 1] != p) {
state = c[state].link;
}
assert(state != -1);
assert(q[pos - c[state].len - 1] == p);
if (c[state].nxt[p - ‘a’] == -1) {
int new_node = lst = sz++;
c[state].nxt[p - ‘a’] = new_node;
c[new_node].len = c[state].len + 2;
c[state].nxt[p - ‘a’] = new_node;
do {
state = c[state].link;
} while (state != -1 && q[pos - c[state].len - 1] != p);
if (state == -1) {
c[new_node].link = 1;
} else {
c[new_node].link = c[state].nxt[p - 'a'];
}
c[new_node].pref = pos;
} else {
lst = c[state].nxt[p - 'a'];
}
for_pref[pos] = lst;
}
void init() {
q = “#” + s;
for (int i = 0; i < q.size() + 4; i++) {
c[i] = node();
}
c[0].len = -1;
lst = 1;
c[1].len = 0;
c[1].link = 0;
sz = 2;
for (int i = 1; i < q.size(); i++) {
add_letter(i, q[i]);
}
}
// все челы от [0, sz - 1]
// sz <= n + 2, т.е. maxN = длина строки + 10
// link[i] < i, можно писать динамику без дфса, а фориками
// link[i] = наибольший суффиксный палиндром исходного палиндрома
// link[“abcba”] = “a”, link[“aacaa”] = “aa”
vector g[maxN];
const int LOG = 20;
int up[LOG][maxN];
int h[maxN];
//l, r
int tin[maxN];
int tout[maxN];
int timer = 0;
void dfs(int v) {
// tin[v] = timer++;
for (int to : g[v]) {
h[to] = h[v] + 1;
dfs(to);
}
// tout[v] = timer;
}
void dfs2(int v) {
tin[v] = timer++;
for (int z = 0; z < 26; z++) {
if (c[v].nxt[z] != -1) {
dfs2(c[v].nxt[z]);
}
}
tout[v] = timer;
}
int get_node(int l, int r) {
int node = for_pref[r];
for (int i = LOG - 1; i >= 0; i–) {
if (h[node] >= (1 << i) && c[up[i][node]].len >= r - l + 1) {
node = up[i][node];
}
}
assert(c[node].len == r - l + 1);
return node;
}
int tp[maxN];
int id[maxN];
int pref[maxN];
int x[maxN];
//pref[i] tin[i] … tout[i] - 1
//z <= pref[i]
//[1 … pref[i]], tin[i] tin[i]
struct Fenwick {
vector f;
vector data;
int n;
Fenwick(int _n) {
n = _n;
f.resize(n + 1);
}
Fenwick() {
n = 0;
}
void addPt(int x) {
data.emplace_back(x);
}
void start() {
sort(data.begin(), data.end());
data.erase(unique(data.begin(), data.end()), data.end());
n = data.size();
f.resize(n + 1, 0);
}
void updPriv(int pos, int v) {
while (pos <= n) {
f[pos] += v;
pos = (pos | (pos - 1)) + 1;
}
}
ll getPriv(int r) {
ll ans = 0;
while (r > 0) {
ans += f[r];
r &= (r - 1);
}
return ans;
}
void upd(int T, int by) {
int pos = lower_bound(data.begin(), data.end(), T) - data.begin();
assert(0 <= pos && pos < data.size() && data[pos] == T);
updPriv(pos + 1, by);
}
ll get(int Tl, int Tr) {
int l = lower_bound(data.begin(), data.end(), Tl) - data.begin() + 1;
int r = lower_bound(data.begin(), data.end(), Tr) - data.begin();
return getPriv(r) - getPriv(l - 1);
}
};
struct Fenwick2D {
//координаты известын заранее, иначе надо сжатое до или еще какой-то кал
//запросы суммы на полуинтервалах, так все хорошо с lower_bound
vector cordFirst;
vector t;
int n;
Fenwick2D(const vector < int >& cord) {
cordFirst = cord;
sort(cordFirst.begin(), cordFirst.end());
cordFirst.erase(unique(cordFirst.begin(), cordFirst.end()), cordFirst.end());
n = cordFirst.size();
t.resize(n + 1);
}
void build() {
for (int i = 1; i <= n; i++) {
t[i].start();
}
}
int getCord(int x) {
auto it = lower_bound(cordFirst.begin(), cordFirst.end(), x) - cordFirst.begin();
return it + 1;
}
void addPoint(int x, int y) {
x = getCord(x);
while (x <= n) {
t[x].addPt(y);
x = (x | (x - 1)) + 1;
}
}
ll querySimple(int r, int l2, int r2) {
ll ans = 0;
while (r > 0) {
ans += t[r].get(l2, r2);
r &= (r - 1);
}
return ans;
}
ll query(int l1, int r1, int l2, int r2) {
l1 = getCord(l1);
r1 = getCord(r1) - 1;
return querySimple(r1, l2, r2) - querySimple(l1 - 1, l2, r2);
}
void add(int x, int y, int w) {
x = getCord(x);
while (x <= n) {
t[x].upd(y, w);
x = (x | (x - 1)) + 1;
}
}
};
int main() {
ios_base::sync_with_stdio(false);
cin.tie(nullptr);
// freopen(“input.txt”, “r”, stdin);
cin >> s;
init();
for (int i = 1; i < sz; i++) {
g[c[i].link].emplace_back(i);
up[0][i] = c[i].link;
}
for (int i = 0; i + 1 < LOG; i++) {
for (int j = 0; j < sz; j++) {
up[i + 1][j] = up[i][up[i][j]];
}
}
dfs(0);
dfs2(0);
dfs2(1);
// for (int z = 0; z < sz; z++) {
// if (c[z].len == 2) {
// dfs2(z);
// }
// }
int q;
cin >> q;
for (int i = 0; i < q; i++) {
cin >> tp[i];
int l, r;
cin >> l >> r;
id[i] = get_node(l, r);
if (tp[i] == 1) {
cin >> pref[i] >> x[i];
}
}
vector crdX;
int n = s.size();
for (int z = 0; z <= n + 1; z++) {
crdX.emplace_back(z);
}
Fenwick2D f(crdX);
for (int i = 0; i < q; i++) {
if (tp[i] == 1) {
assert(1 <= pref[i] && pref[i] <= n);
f.addPoint(n - pref[i], tin[id[i]]);
f.addPoint(n - pref[i], tout[id[i]]);
}
}
//abcba → bcb
f.build();
//tin[id[i]] <= tout[
for (int i = 0; i < q; i++) {
if (tp[i] == 1) {
f.add(n - pref[i], tin[id[i]], x[i]);
f.add(n - pref[i], tout[id[i]], -x[i]);
}
else {
cout << f.query(0, n - c[id[i]].pref + 1, 0, tin[id[i]] + 1) << ‘\n’;
}
}
return 0;
}