Algorithmic Solution for Sequence Similarity Constraints via Suffix Automaton and Binary Lifting Union-Find
Tech
1
The problem requires counting the number of valid sequences \(b\) given constraints \(b_i \in [L_i, R_i]\) and a similarity condition defined by a sequence \(a\). Two sequences \(a\) and \(b\) are defined as "k-similar" if, for every quadruple \((l_1, r_1, l_2, r_2)\) where the intervals \([l_1, r_1]\) and \([l_2, r_2]\) are adjacent, of equal length \(\le k\), and the substrings \(a_{l_1\ldots r_1}\) and \(a_{l_2 \ldots r_2}\) are identical, the corresponding substrings in \(b\) must also be identical.
The solution involves maintaining equivalence relations among indices of \(b\) using a Disjoint Set Union (DSU). Indices within the same connected component must have equal values. When merging sets, the valid range for the component is updated to \([\max(L), \min(R)]\), and the answer is adjusted by multiplying the sizes of these ranges modulo \(998244353\).
The primary challenge is efficiently identifying all pairs of intervals in \(a\) that trigger a merge in \(b\). A naive \(O(n^2)\) enumeration of intervals is too slow. Instead, we utilize a technique based on finding "AA" type substrings (concatenation of a string with itself). For each length \(i\), we set "key points" at intervals of \(i\). Any "AA" substring of length \(2i\) must span two consecutive key points. By enumerating these key points and calculating the Longest Common Prefix (LCP) and Longest Common Suffix (LCS) using Suffix Arrays (or Suffix Automata), we can determine the valid ranges of length \(i\) that form "AA" patterns in \(O(n \log n)\) time.
To avoid \(O(n^2)\) merge operations, we employ a binary lifting optimization on the DSU structure. We construct \(O(\log n)\) layers of virtual nodes. A node at layer \(j\) and position \(x\) represents the interval \([x, x + 2^j - 1]\). When two intervals of length \(2^k\) need to be merged, we attempt to merge their virtual nodes at layer \(k\). If they are already connected, no further action is needed for that range. Otherwise, we recursively merge the two halves of the interval at layer \(k-1\). This structure ensures that there are only \(O(n \log n)\) virtual nodes and operations, reducing the total complexity to \(O(n \log^2 n)\).
The implementation uses `atcoder::suffix_array` for string processing and a DSU with path compression and union by size. The `add` function handles the recursive merging of intervals using the virtual node layers.
#include <bits/stdc++.h>
#include <atcoder/string>
using namespace atcoder;
using namespace std;
const int MOD = 998244353;
const int MAXN = 2000005;
int n, q;
int a[MAXN];
int limit_low[MAXN], limit_high[MAXN];
int parent[MAXN * 20];
int component_low[MAXN * 20], component_high[MAXN * 20];
long long answer = 1;
int inv[MAXN];
int find(int u) {
return parent[u] == u ? u : parent[u] = find(parent[u]);
}
// Attempt to merge sets containing u and v.
// Returns true if a merge occurred, false if already connected.
bool merge_sets(int u, int v) {
u = find(u);
v = find(v);
if (u == v) return false;
// Update answer by removing old contributions
answer = answer * inv[component_high[u] - component_low[u] + 1] % MOD;
answer = answer * inv[component_high[v] - component_low[v] + 1] % MOD;
if (component_low[u] < component_low[v]) swap(u, v);
parent[v] = u;
component_low[u] = max(component_low[u], component_low[v]);
component_high[u] = min(component_high[u], component_high[v]);
// Add contribution of the new merged set
if (component_high[u] < component_low[u]) {
answer = 0;
} else {
answer = answer * (component_high[u] - component_low[u] + 1) % MOD;
}
return true;
}
int get_virtual_node(int layer, int index) {
return layer * n + index;
}
// Recursive merge function for interval [x, x + 2^id - 1] and [y, y + 2^id - 1]
void add_interval_merge(int id, int x, int y) {
if (id == 0) {
merge_sets(x, y);
return;
}
if (!merge_sets(get_virtual_node(id, x), get_virtual_node(id, y))) return;
add_interval_merge(id - 1, x, y);
add_interval_merge(id - 1, x + (1 << (id - 1)), y + (1 << (id - 1)));
}
struct SuffixInfo {
int sa[MAXN], rank[MAXN], lcp[MAXN], st[20][MAXN];
int n;
void init(int _n) {
n = _n;
fill(lcp, lcp + 2 * n + 1, 0);
}
void build(int *s) {
vector<int> s_vec(n);
for (int i = 0; i < n; ++i) s_vec[i] = s[i + 1];
auto sa_vec = suffix_array(s_vec);
for (int i = 0; i < n; ++i) {
sa[i + 1] = sa_vec[i] + 1;
rank[sa[i + 1]] = i + 1;
}
for (int i = 1, k = 0; i <= n; ++i) {
if (k) --k;
while (s[i + k] == s[sa[rank[i] - 1] + k]) ++k;
lcp[rank[i]] = k;
}
for (int i = 1; i <= n; ++i) st[0][i] = lcp[i];
for (int j = 1; j <= 19; ++j) {
for (int i = 1; i + (1 << j) - 1 <= n; ++i) {
st[j][i] = min(st[j-1][i], st[j-1][i + (1 << (j-1))]);
}
}
}
int query_lcp(int u, int v) {
if (u == v) return n - u + 1;
u = rank[u]; v = rank[v];
if (u > v) swap(u, v);
int k = __lg(v - u);
return min(st[k][u+1], st[k][v - (1<<k) + 1]);
}
} s1, s2;
long long power(long long base, int exp) {
long long res = 1;
while (exp) {
if (exp & 1) res = res * base % MOD;
base = base * base % MOD;
exp >>= 1;
}
return res;
}
void solve() {
cin >> n;
answer = 1;
for (int i = 1; i <= n; ++i) {
cin >> a[i];
parent[i] = i;
}
for (int i = 1; i <= 20 * n; ++i) parent[i] = i;
for (int i = 1; i <= n; ++i) {
cin >> limit_low[i] >> limit_high[i];
component_low[i] = limit_low[i];
component_high[i] = limit_high[i];
answer = answer * (limit_high[i] - limit_low[i] + 1) % MOD;
}
// Initialize virtual nodes limits to large range, effectively no constraint until merged
for (int i = 1; i <= 20 * n; ++i) {
component_low[i] = 1;
component_high[i] = 1000000;
}
s1.init(n); s2.init(n);
s1.build(a);
reverse(a + 1, a + n + 1);
s2.build(a);
for (int len = 1; len <= n / 2; ++len) {
if (answer == 0) {
cout << 0 << " ";
continue;
}
for (int pos = len; pos + len <= n; pos += len) {
int p = pos, q = pos + len;
int lcp_val = min(len, s1.query_lcp(p, q));
int lcs_val = min(len, s2.query_lcp(n - p + 1, n - q + 1));
if (lcp_val + lcs_val - 1 < len) continue;
int l = p - lcs_val + 1;
int r = p + lcp_val - 1;
int matched_len = r - l + 1;
auto apply_merge = [&](int L, int R, int dest_offset) {
int k = __lg(R - L + 1);
add_interval_merge(k, L, L + dest_offset);
add_interval_merge(k, R - (1<<k) + 1, R - (1<<k) + 1 + dest_offset);
};
apply_merge(l, r, len);
}
cout << answer << " ";
}
cout << "\n";
}
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
// Precompute modular inverses
for (int i = 1; i <= 1000000; ++i) inv[i] = power(i, MOD - 2);
int t;
cin >> t;
while (t--) solve();
return 0;
}
