Schieber-Vishkin algorithm
The Schieber-Vishkin algorithm is a parallel algorithm for finding the lowest common ancestor (LCA) of two nodes in a tree. It operates in the concurrent-read exclusive-write (CREW) PRAM model and is notable for its efficiency, achieving logarithmic time complexity. The algorithm preprocesses the tree in time and allows subsequent LCA queries to be answered in time.
You are encouraged to solve this task according to the task description, using any language you may know.
- Problem definition
The lowest common ancestor problem is defined as follows:
Given a rooted tree with nodes, and two nodes and in the tree, find the deepest node that is an ancestor of both and . Formally, satisfies:
and for any other node in the intersection:
- Input
1. A rooted tree , where is the set of nodes and is the set of edges. The tree has nodes. 2. A pair of nodes , where .
- Output
The algorithm outputs the node that is the lowest common ancestor of and .
- Algorithm overview
The Schieber-Vishkin algorithm is designed to preprocess the tree in parallel to enable constant-time LCA queries. The preprocessing involves assigning each node a label that encodes information about its position in the tree hierarchy. These labels are constructed using tree structures such as parent-child relationships and depth.
The key steps of the algorithm are:
1. Tree representation: The input tree is represented as an adjacency list or similar structure. The root node is identified. 2. Preprocessing in parallel: During preprocessing:
- Nodes are assigned labels based on their position in the tree. - Depth-first search (DFS) or similar traversal techniques are used to compute necessary information.
3. Query resolution: Using the precomputed labels, the LCA of any two nodes and can be determined in time.
- Complexity
- Preprocessing time: using processors in the CREW PRAM model. - Query time: . - Space complexity: .
- Applications
The Schieber-Vishkin algorithm is widely used in applications where fast query resolution is critical, such as:
- Network routing and communication. - Computational biology, particularly in phylogenetics. - Query optimization in databases. - Text processing, such as suffix tree and suffix array construction.
This algorithm is a foundational result in parallel computing and demonstrates how preprocessing can enable efficient query answering in tree-based problems.
// Compilation command: g++ -std=c++20 -Wall -Wextra -pedantic SchieberVishkinAlgorithm.cpp -o SchieberVishkinAlgorithm
#include <algorithm>
#include <array>
#include <bit>
#include <cassert>
#include <iostream>
#include <limits>
#include <span>
#include <stack>
#include <vector>
struct Node {
int child = 0;
int sibling = 0;
int parent = 0;
};
struct LCAData {
std::vector<int> pi;
std::vector<int> beta;
std::vector<int> alpha;
std::vector<int> tau;
std::vector<int> lambda;
};
bool traversalPhase(
int &p, int &time,
std::vector<int> &pi,
std::vector<int> &beta,
std::vector<int> &tau,
std::vector<int> &lambda,
const std::vector<Node> &nodes
) {
while (true) {
++time;
pi[p] = time;
tau[time] = 0;
lambda[time] = 1 + lambda[time>>1];
if (nodes[p].child != 0) {
p = nodes[p].child;
continue;
}
beta[p] = time;
break;
}
while (true) {
tau[beta[p]] = nodes[p].parent;
if (nodes[p].sibling != 0) {
p = nodes[p].sibling;
return true;
}
p = nodes[p].parent;
if (p != 0) {
int w = time & -pi[p];
int h = lambda[w];
beta[p] = ((time >> h) | 1) << h;
} else
return false;
}
}
void computeAlpha(
const std::vector<Node> &nodes,
int root,
std::vector<int> &alpha,
const std::vector<int> &beta
) {
std::stack<int> stk;
stk.push(root);
while (!stk.empty()) {
int u = stk.top(); stk.pop();
alpha[u] = alpha[nodes[u].parent] | (beta[u] & -beta[u]);
if (nodes[u].sibling)
stk.push(nodes[u].sibling);
if (nodes[u].child)
stk.push(nodes[u].child);
}
}
LCAData buildLCAData(int N, const std::vector<int>& A) {
LCAData D;
D.pi.assign(N+1, 0);
D.beta.assign(N+1, 0);
D.alpha.assign(N+1, 0);
D.tau.assign(N+1, 0);
D.lambda.assign(N+1, 0);
std::vector<Node> nodes(N + 1);
int t = 0;
for (int v = N; v > 0; --v) {
int u = 0;
while (A[v] > A[t] || (A[v] == A[t] && v > t)) {
u = t;
t = nodes[t].parent;
}
if (u) {
nodes[v].sibling = nodes[u].sibling;
nodes[u].sibling = 0;
nodes[u].parent = v;
nodes[v].child = u;
} else
nodes[v].sibling = nodes[t].child;
nodes[t].child = v;
nodes[v].parent = t;
t = v;
}
int p = nodes[0].child;
int time = 0;
D.lambda[0] = -1;
while (traversalPhase(p, time, D.pi, D.beta, D.tau, D.lambda, nodes));
p = nodes[0].child;
D.lambda[0] = D.lambda[time];
D.pi[0] = D.beta[0] = D.alpha[0] = 0;
if (p)
computeAlpha(nodes, p, D.alpha, D.beta);
return D;
}
int nca(int x, int y, const LCAData& D) {
unsigned bx = static_cast<unsigned>(D.beta[x]);
unsigned by = static_cast<unsigned>(D.beta[y]);
unsigned b = (bx <= by) ? (by & -bx) : (bx & -by);
if (b == 0)
return D.pi[x] <= D.pi[y] ? x : y;
int h = std::countr_zero(b);
unsigned ax = static_cast<unsigned>(D.alpha[x]);
unsigned ay = static_cast<unsigned>(D.alpha[y]);
unsigned k = ax & ay & ~((~0u) << h);
if (k == 0)
return D.pi[x] <= D.pi[y] ? x : y;
h = std::countr_zero(k);
int jx = (((D.beta[x] >> h) | 1) << h);
if (jx != D.beta[x]) {
unsigned lmask = static_cast<unsigned>(D.alpha[x]) & ((1u << h) - 1u);
if (lmask) {
int l = std::countr_zero(lmask);
x = D.tau[(((D.beta[x] >> l) | 1) << l)];
}
}
int jy = (((D.beta[y] >> h) | 1) << h);
if (jy != D.beta[y]) {
unsigned lmask = static_cast<unsigned>(D.alpha[y]) & ((1u << h) - 1u);
if (lmask) {
int l = std::countr_zero(lmask);
y = D.tau[(((D.beta[y] >> l) | 1) << l)];
}
}
return D.pi[x] <= D.pi[y] ? x : y;
}
std::vector<int> solveTestCase(
const std::vector<int> &values,
const std::vector<std::array<int, 2>> &queries
) {
int n = int(values.size());
std::vector<int> A(n+2), R(n+2), B(n+2);
A[0] = std::numeric_limits<int>::max();
int N = 1, cnt = 0;
for (int i = 1; i <= n; ++i) {
if (i > 1 && values[i-1] != values[i-2]) {
A[N] = cnt;
R[N] = i;
++N;
cnt = 0;
}
B[i] = N;
++cnt;
}
A[N] = cnt;
R[N] = n + 1;
LCAData D = buildLCAData(N, A);
std::vector<int> ans;
ans.reserve(queries.size());
for (auto [i, j] : queries) {
int x = B[i], y = B[j];
int z;
if (x == y)
z = j - i + 1;
else {
int mid = (x + 1 < y) ? A[nca(x+1, y-1, D)] : 0;
z = std::max({mid, R[x]-i, A[y]-(R[y]-j)+1});
}
ans.push_back(z);
}
return ans;
}
int main() {
std::vector<int> values = {-1, -1, 1, 1, 1, 1, 3, 10, 10, 10};
std::vector<std::array<int, 2>> queries = {{2, 3}, {1, 10}, {5, 10}};
std::vector<int> expected = {1, 4, 3};
auto result = solveTestCase(values, queries);
assert(result == expected);
std::cout << "All tests passed.\n";
return 0;
}
using System;
using System.Collections.Generic;
class Program
{
static Result Process(int N, int[] A)
{
int[] pi = new int[N + 1];
int[] beta = new int[N + 1];
int[] alfa = new int[N + 1];
int[] tau = new int[N + 1];
int[] lam = new int[N + 1];
Node[] nodes = new Node[N + 1];
for (int i = 0; i <= N; i++)
{
nodes[i] = new Node();
}
// Make triply linked tree
int t = 0;
for (int v = N; v > 0; v--)
{
int u = 0;
while (A[v] > A[t] || (A[v] == A[t] && v > t))
{
u = t;
t = nodes[t].Parent;
}
if (u != 0)
{
nodes[v].Sib = nodes[u].Sib;
nodes[u].Sib = 0;
nodes[u].Parent = v;
nodes[v].Child = u;
}
else
{
nodes[v].Sib = nodes[t].Child;
}
nodes[t].Child = v;
nodes[v].Parent = t;
t = v;
}
// Begin first traversal
int p = nodes[0].Child;
int n = 0;
lam[0] = -1;
while (Traversal(nodes, p, n, pi, beta, tau, lam, out p, out n))
{
// Continue traversal
}
// Begin second traversal
p = nodes[0].Child;
lam[0] = lam[n];
pi[0] = beta[0] = alfa[0] = 0;
// Perform second traversal
if (p != 0)
{
ComputeAlfa(nodes, p, alfa, beta);
}
return new Result(pi, beta, alfa, tau, lam);
}
static bool Traversal(Node[] nodes, int initialP, int initialN, int[] pi, int[] beta, int[] tau, int[] lam, out int newP, out int newN)
{
int p = initialP;
int n = initialN;
// s3: Compute beta in the easy case
while (true)
{
n++;
pi[p] = n;
tau[n] = 0;
lam[n] = 1 + lam[n >> 1];
if (nodes[p].Child != 0)
{
p = nodes[p].Child;
continue;
}
beta[p] = n;
break;
}
// s4: Compute tau, bottom-up
while (true)
{
tau[beta[p]] = nodes[p].Parent;
if (nodes[p].Sib != 0)
{
p = nodes[p].Sib;
newP = p;
newN = n;
return true; // Go back to s3
}
p = nodes[p].Parent;
// Compute beta in the hard case
if (p != 0)
{
int h = lam[n & -pi[p]];
beta[p] = ((n >> h) | 1) << h;
}
else
{
newP = p;
newN = n;
return false; // Exit traversal
}
}
}
static void ComputeAlfa(Node[] nodes, int node, int[] alfa, int[] beta)
{
// s7: Compute alfa, top-down
alfa[node] = alfa[nodes[node].Parent] | (beta[node] & -beta[node]);
if (nodes[node].Child != 0)
{
ComputeAlfa(nodes, nodes[node].Child, alfa, beta);
}
// s8: Continue traversal
if (nodes[node].Sib != 0)
{
ComputeAlfa(nodes, nodes[node].Sib, alfa, beta);
}
}
static int Nca(int x, int y, int[] beta, int[] alfa, int[] tau, int[] lam, int[] pi)
{
// Find common height
int h;
if (beta[x] <= beta[y])
{
h = lam[beta[y] & -beta[x]];
}
else
{
h = lam[beta[x] & -beta[y]];
}
// Find true height
int k = alfa[x] & alfa[y] & -(1 << h);
h = lam[k & -k];
// Find beta[z]
int j = ((beta[x] >> h) | 1) << h;
// Find x' and y'
if (j != beta[x])
{
int l = lam[alfa[x] & ((1 << h) - 1)];
x = tau[((beta[x] >> l) | 1) << l];
}
if (j != beta[y])
{
int l = lam[alfa[y] & ((1 << h) - 1)];
y = tau[((beta[y] >> l) | 1) << l];
}
// Find z
int z = (pi[x] <= pi[y]) ? x : y;
return z;
}
static List<int> SolveTestCase(int n, int[] values, int[,] queries)
{
List<int> results = new List<int>();
int[] A = new int[n + 2];
A[0] = int.MaxValue; // A[0]
int[] R = new int[n + 2];
int[] B = new int[n + 2];
int N = 1;
int count = 0;
int? oldx = null;
for (int i = 1; i <= n; i++)
{
int x = values[i - 1];
if (i > 1 && (oldx == null || x != oldx))
{
A[N] = count;
R[N] = i;
N++;
count = 0;
}
B[i] = N;
count++;
oldx = x;
}
A[N] = count;
R[N] = n + 1;
Result result = Process(N, A);
int[] pi = result.Pi;
int[] beta = result.Beta;
int[] alfa = result.Alfa;
int[] tau = result.Tau;
int[] lam = result.Lam;
int queryCount = queries.GetLength(0);
for (int q = 0; q < queryCount; q++)
{
int i = queries[q, 0];
int j = queries[q, 1];
int x = B[i];
int y = B[j];
int z;
if (x == y)
{
z = j - i + 1;
}
else
{
if (x + 1 != y)
{
z = A[Nca(x + 1, y - 1, beta, alfa, tau, lam, pi)];
}
else
{
z = 0;
}
z = Math.Max(z, Math.Max(R[x] - i, A[y] - R[y] + j + 1));
}
results.Add(z);
}
return results;
}
static void Main(string[] args)
{
// Hard-coded test data
List<TestCase> testCases = new List<TestCase>();
testCases.Add(new TestCase(
10,
new int[] { -1, -1, 1, 1, 1, 1, 3, 10, 10, 10 },
new int[,] { { 2, 3 }, { 1, 10 }, { 5, 10 } },
new int[] { 1, 4, 3 }
));
for (int idx = 0; idx < testCases.Count; idx++)
{
TestCase test = testCases[idx];
int n = test.N;
int[] values = test.Values;
int[,] queries = test.Queries;
int[] expected = test.Expected;
Console.WriteLine($"Test Case {idx + 1}:");
Console.WriteLine($"Size: {n}, Queries: {queries.GetLength(0)}");
Console.Write("Values: ");
foreach (int value in values)
{
Console.Write($"{value} ");
}
Console.WriteLine();
List<int> results = SolveTestCase(n, values, queries);
Console.WriteLine("Queries and Results:");
for (int q_idx = 0; q_idx < queries.GetLength(0); q_idx++)
{
int query0 = queries[q_idx, 0];
int query1 = queries[q_idx, 1];
int result = results[q_idx];
int exp = expected[q_idx];
Console.WriteLine($"Query: {query0} {query1}");
Console.WriteLine($"Result: {result} (Expected: {exp})");
if (result != exp)
{
Console.WriteLine(" WARNING: Result doesn't match expected output");
}
}
Console.WriteLine();
}
}
}
class Node
{
public int Child { get; set; } = 0;
public int Sib { get; set; } = 0;
public int Parent { get; set; } = 0;
}
class Result
{
public int[] Pi { get; }
public int[] Beta { get; }
public int[] Alfa { get; }
public int[] Tau { get; }
public int[] Lam { get; }
public Result(int[] pi, int[] beta, int[] alfa, int[] tau, int[] lam)
{
Pi = pi;
Beta = beta;
Alfa = alfa;
Tau = tau;
Lam = lam;
}
}
class TestCase
{
public int N { get; }
public int[] Values { get; }
public int[,] Queries { get; }
public int[] Expected { get; }
public TestCase(int n, int[] values, int[,] queries, int[] expected)
{
N = n;
Values = values;
Queries = queries;
Expected = expected;
}
}
- Output:
Test Case 1: Size: 10, Queries: 3 Values: -1 -1 1 1 1 1 3 10 10 10 Queries and Results: Query: 2 3 Result: 1 (Expected: 1) Query: 1 10 Result: 4 (Expected: 4) Query: 5 10 Result: 3 (Expected: 3)
IDENTIFICATION DIVISION.
PROGRAM-ID. JAVA-TO-COBOL.
ENVIRONMENT DIVISION.
DATA DIVISION.
WORKING-STORAGE SECTION.
01 VARS.
05 N-IN PIC S9(9) COMP.
05 Q-COUNT PIC S9(9) COMP.
05 I PIC S9(9) COMP.
05 J PIC S9(9) COMP.
05 Q-IDX PIC S9(9) COMP.
05 N-TOTAL PIC S9(9) COMP.
05 COUNT-VAL PIC S9(9) COMP.
05 OLDX PIC S9(9) COMP.
05 X-VAL PIC S9(9) COMP.
05 Y-VAL PIC S9(9) COMP.
05 Z-VAL PIC S9(9) COMP.
05 VAL1 PIC S9(9) COMP.
05 VAL2 PIC S9(9) COMP.
05 X-PLUS PIC S9(9) COMP.
05 NCA-X PIC S9(9) COMP.
05 NCA-Y PIC S9(9) COMP.
05 NCA-RES PIC S9(9) COMP.
05 IDX-N PIC S9(9) COMP.
05 IDX-NCA PIC S9(9) COMP.
05 IDX-X PIC S9(9) COMP.
05 IDX-Y PIC S9(9) COMP.
05 N PIC S9(9) COMP.
05 T PIC S9(9) COMP.
05 V PIC S9(9) COMP.
05 U PIC S9(9) COMP.
05 LOOP-DONE PIC S9(9) COMP.
05 IDX-V PIC S9(9) COMP.
05 IDX-T PIC S9(9) COMP.
05 IDX-U PIC S9(9) COMP.
05 P-VAR PIC S9(9) COMP.
05 N-VAR PIC S9(9) COMP.
05 TRAVERSAL-DONE PIC S9(9) COMP.
05 S3-DONE PIC S9(9) COMP.
05 S4-DONE PIC S9(9) COMP.
05 HALF-N PIC S9(9) COMP.
05 IDX-HALF PIC S9(9) COMP.
05 IDX-P PIC S9(9) COMP.
05 IDX-BETA-P PIC S9(9) COMP.
05 H-VAR PIC S9(9) COMP.
05 K-VAR PIC S9(9) COMP.
05 L-VAR PIC S9(9) COMP.
05 J-VAR PIC S9(9) COMP.
05 TEMP-K PIC S9(9) COMP.
05 MASK-VAL PIC S9(9) COMP.
05 IDX-AND PIC S9(9) COMP.
05 IDX-TAU PIC S9(9) COMP.
05 ALFA-NODE PIC S9(9) COMP.
05 CURR-NODE PIC S9(9) COMP.
05 ALFA-DONE PIC S9(9) COMP.
05 BACKTRACK-DONE PIC S9(9) COMP.
05 IDX-CURR PIC S9(9) COMP.
05 IDX-PARENT PIC S9(9) COMP.
01 BIT-VARS.
05 BIT-A PIC S9(9) COMP.
05 BIT-B PIC S9(9) COMP.
05 BIT-RES PIC S9(9) COMP.
05 BIT-MUL PIC S9(9) COMP.
05 TEMP-A PIC S9(9) COMP.
05 TEMP-B PIC S9(9) COMP.
05 REM-A PIC S9(9) COMP.
05 REM-B PIC S9(9) COMP.
05 BIT-IDX PIC S9(9) COMP.
05 BIT-VAL PIC S9(9) COMP.
05 BIT-SHIFT PIC S9(9) COMP.
05 BIT-DIV PIC S9(9) COMP.
01 ARRAYS.
05 VALUES-ARR OCCURS 10005 TIMES PIC S9(9) COMP.
05 QUERY-I OCCURS 10005 TIMES PIC S9(9) COMP.
05 QUERY-J OCCURS 10005 TIMES PIC S9(9) COMP.
05 EXPECTED-ARR OCCURS 10005 TIMES PIC S9(9) COMP.
05 RESULTS-ARR OCCURS 10005 TIMES PIC S9(9) COMP.
05 A-ARR OCCURS 10005 TIMES PIC S9(9) COMP.
05 R-ARR OCCURS 10005 TIMES PIC S9(9) COMP.
05 B-ARR OCCURS 10005 TIMES PIC S9(9) COMP.
01 TREE-ARRAYS.
05 PI-ARR OCCURS 10005 TIMES PIC S9(9) COMP.
05 BETA-ARR OCCURS 10005 TIMES PIC S9(9) COMP.
05 ALFA-ARR OCCURS 10005 TIMES PIC S9(9) COMP.
05 TAU-ARR OCCURS 10005 TIMES PIC S9(9) COMP.
05 LAM-ARR OCCURS 10005 TIMES PIC S9(9) COMP.
05 NODES OCCURS 10005 TIMES.
10 NODE-CHILD PIC S9(9) COMP VALUE 0.
10 NODE-SIB PIC S9(9) COMP VALUE 0.
10 NODE-PARENT PIC S9(9) COMP VALUE 0.
01 DISP-VARS.
05 DISP-NUM PIC -9(9).
05 TEMP-STR-I PIC X(15).
05 TEMP-STR-J PIC X(15).
05 TEMP-STR-RES PIC X(15).
05 TEMP-STR-EXP PIC X(15).
PROCEDURE DIVISION.
MAIN-PARA.
MOVE 10 TO N-IN
MOVE 3 TO Q-COUNT
MOVE -1 TO VALUES-ARR(1)
MOVE -1 TO VALUES-ARR(2)
MOVE 1 TO VALUES-ARR(3)
MOVE 1 TO VALUES-ARR(4)
MOVE 1 TO VALUES-ARR(5)
MOVE 1 TO VALUES-ARR(6)
MOVE 3 TO VALUES-ARR(7)
MOVE 10 TO VALUES-ARR(8)
MOVE 10 TO VALUES-ARR(9)
MOVE 10 TO VALUES-ARR(10)
MOVE 2 TO QUERY-I(1)
MOVE 3 TO QUERY-J(1)
MOVE 1 TO EXPECTED-ARR(1)
MOVE 1 TO QUERY-I(2)
MOVE 10 TO QUERY-J(2)
MOVE 4 TO EXPECTED-ARR(2)
MOVE 5 TO QUERY-I(3)
MOVE 10 TO QUERY-J(3)
MOVE 3 TO EXPECTED-ARR(3)
DISPLAY "Test Case 1:"
DISPLAY "Size: " N-IN ", Queries: " Q-COUNT
DISPLAY "Values: -1 -1 1 1 1 1 3 10 10 10"
PERFORM SOLVE-TEST-CASE
DISPLAY "Queries and Results:"
PERFORM VARYING Q-IDX FROM 1 BY 1 UNTIL Q-IDX > Q-COUNT
MOVE QUERY-I(Q-IDX) TO DISP-NUM
MOVE DISP-NUM TO TEMP-STR-I
MOVE QUERY-J(Q-IDX) TO DISP-NUM
MOVE DISP-NUM TO TEMP-STR-J
DISPLAY "Query: " FUNCTION TRIM(TEMP-STR-I)
" " FUNCTION TRIM(TEMP-STR-J)
MOVE RESULTS-ARR(Q-IDX) TO DISP-NUM
MOVE DISP-NUM TO TEMP-STR-RES
MOVE EXPECTED-ARR(Q-IDX) TO DISP-NUM
MOVE DISP-NUM TO TEMP-STR-EXP
DISPLAY "Result: " FUNCTION TRIM(TEMP-STR-RES)
" (Expected: " FUNCTION TRIM(TEMP-STR-EXP) ")"
IF RESULTS-ARR(Q-IDX) NOT = EXPECTED-ARR(Q-IDX)
DISPLAY " WARNING: Result doesn't match expected"
END-IF
END-PERFORM
STOP RUN.
SOLVE-TEST-CASE.
MOVE 2147483647 TO A-ARR(1)
MOVE 1 TO N-TOTAL
MOVE 0 TO COUNT-VAL
MOVE -999999 TO OLDX
PERFORM VARYING I FROM 1 BY 1 UNTIL I > N-IN
MOVE VALUES-ARR(I) TO X-VAL
IF I > 1 AND X-VAL NOT = OLDX
COMPUTE IDX-N = N-TOTAL + 1
MOVE COUNT-VAL TO A-ARR(IDX-N)
MOVE I TO R-ARR(IDX-N)
ADD 1 TO N-TOTAL
MOVE 0 TO COUNT-VAL
END-IF
MOVE N-TOTAL TO B-ARR(I)
ADD 1 TO COUNT-VAL
MOVE X-VAL TO OLDX
END-PERFORM
COMPUTE IDX-N = N-TOTAL + 1
MOVE COUNT-VAL TO A-ARR(IDX-N)
COMPUTE R-ARR(IDX-N) = N-IN + 1
MOVE N-TOTAL TO N
PERFORM PROCESS-PARA
PERFORM VARYING Q-IDX FROM 1 BY 1 UNTIL Q-IDX > Q-COUNT
MOVE QUERY-I(Q-IDX) TO I
MOVE QUERY-J(Q-IDX) TO J
MOVE B-ARR(I) TO X-VAL
MOVE B-ARR(J) TO Y-VAL
IF X-VAL = Y-VAL
COMPUTE Z-VAL = J - I + 1
ELSE
COMPUTE X-PLUS = X-VAL + 1
IF X-PLUS NOT = Y-VAL
COMPUTE NCA-X = X-VAL + 1
COMPUTE NCA-Y = Y-VAL - 1
PERFORM NCA-PARA
COMPUTE IDX-NCA = NCA-RES + 1
MOVE A-ARR(IDX-NCA) TO Z-VAL
ELSE
MOVE 0 TO Z-VAL
END-IF
COMPUTE IDX-X = X-VAL + 1
COMPUTE VAL1 = R-ARR(IDX-X) - I
COMPUTE IDX-Y = Y-VAL + 1
COMPUTE VAL2 = A-ARR(IDX-Y) - R-ARR(IDX-Y) + J + 1
IF VAL1 > Z-VAL
MOVE VAL1 TO Z-VAL
END-IF
IF VAL2 > Z-VAL
MOVE VAL2 TO Z-VAL
END-IF
END-IF
MOVE Z-VAL TO RESULTS-ARR(Q-IDX)
END-PERFORM.
PROCESS-PARA.
PERFORM VARYING I FROM 1 BY 1 UNTIL I > N + 1
MOVE 0 TO NODE-CHILD(I)
MOVE 0 TO NODE-SIB(I)
MOVE 0 TO NODE-PARENT(I)
END-PERFORM
MOVE 0 TO T
PERFORM VARYING V FROM N BY -1 UNTIL V <= 0
MOVE 0 TO U
MOVE 0 TO LOOP-DONE
PERFORM UNTIL LOOP-DONE = 1
COMPUTE IDX-V = V + 1
COMPUTE IDX-T = T + 1
IF A-ARR(IDX-V) > A-ARR(IDX-T) OR
(A-ARR(IDX-V) = A-ARR(IDX-T) AND V > T)
MOVE T TO U
MOVE NODE-PARENT(IDX-T) TO T
ELSE
MOVE 1 TO LOOP-DONE
END-IF
END-PERFORM
COMPUTE IDX-V = V + 1
COMPUTE IDX-T = T + 1
COMPUTE IDX-U = U + 1
IF U NOT = 0
MOVE NODE-SIB(IDX-U) TO NODE-SIB(IDX-V)
MOVE 0 TO NODE-SIB(IDX-U)
MOVE V TO NODE-PARENT(IDX-U)
MOVE U TO NODE-CHILD(IDX-V)
ELSE
MOVE NODE-CHILD(IDX-T) TO NODE-SIB(IDX-V)
END-IF
MOVE V TO NODE-CHILD(IDX-T)
MOVE T TO NODE-PARENT(IDX-V)
MOVE V TO T
END-PERFORM
MOVE NODE-CHILD(1) TO P-VAR
MOVE 0 TO N-VAR
MOVE -1 TO LAM-ARR(1)
MOVE 0 TO TRAVERSAL-DONE
PERFORM UNTIL TRAVERSAL-DONE = 1
PERFORM TRAVERSAL-PARA
END-PERFORM
MOVE NODE-CHILD(1) TO P-VAR
COMPUTE IDX-N = N-VAR + 1
MOVE LAM-ARR(IDX-N) TO LAM-ARR(1)
MOVE 0 TO PI-ARR(1)
MOVE 0 TO BETA-ARR(1)
MOVE 0 TO ALFA-ARR(1)
IF P-VAR NOT = 0
MOVE P-VAR TO ALFA-NODE
PERFORM COMPUTE-ALFA
END-IF.
TRAVERSAL-PARA.
MOVE 0 TO S3-DONE
PERFORM UNTIL S3-DONE = 1
ADD 1 TO N-VAR
COMPUTE IDX-P = P-VAR + 1
MOVE N-VAR TO PI-ARR(IDX-P)
COMPUTE IDX-N = N-VAR + 1
MOVE 0 TO TAU-ARR(IDX-N)
COMPUTE HALF-N = N-VAR / 2
COMPUTE IDX-HALF = HALF-N + 1
COMPUTE LAM-ARR(IDX-N) = 1 + LAM-ARR(IDX-HALF)
IF NODE-CHILD(IDX-P) NOT = 0
MOVE NODE-CHILD(IDX-P) TO P-VAR
ELSE
MOVE N-VAR TO BETA-ARR(IDX-P)
MOVE 1 TO S3-DONE
END-IF
END-PERFORM
MOVE 0 TO S4-DONE
PERFORM UNTIL S4-DONE = 1
COMPUTE IDX-P = P-VAR + 1
COMPUTE IDX-BETA-P = BETA-ARR(IDX-P) + 1
MOVE NODE-PARENT(IDX-P) TO TAU-ARR(IDX-BETA-P)
IF NODE-SIB(IDX-P) NOT = 0
MOVE NODE-SIB(IDX-P) TO P-VAR
MOVE 1 TO S4-DONE
MOVE 0 TO TRAVERSAL-DONE
EXIT PARAGRAPH
END-IF
MOVE NODE-PARENT(IDX-P) TO P-VAR
COMPUTE IDX-P = P-VAR + 1
IF P-VAR NOT = 0
MOVE N-VAR TO BIT-A
COMPUTE BIT-B = 0 - PI-ARR(IDX-P)
PERFORM DO-BIT-AND
COMPUTE IDX-AND = BIT-RES + 1
MOVE LAM-ARR(IDX-AND) TO H-VAR
COMPUTE BIT-VAL = N-VAR
COMPUTE BIT-SHIFT = H-VAR
PERFORM DO-BIT-SHIFT-RIGHT
MOVE BIT-RES TO BIT-A
MOVE 1 TO BIT-B
PERFORM DO-BIT-OR
MOVE BIT-RES TO BIT-VAL
COMPUTE BIT-SHIFT = H-VAR
PERFORM DO-BIT-SHIFT-LEFT
MOVE BIT-RES TO BETA-ARR(IDX-P)
ELSE
MOVE 1 TO S4-DONE
MOVE 1 TO TRAVERSAL-DONE
EXIT PARAGRAPH
END-IF
END-PERFORM.
COMPUTE-ALFA.
MOVE ALFA-NODE TO CURR-NODE
MOVE 0 TO ALFA-DONE
PERFORM UNTIL ALFA-DONE = 1
COMPUTE IDX-CURR = CURR-NODE + 1
COMPUTE IDX-PARENT = NODE-PARENT(IDX-CURR) + 1
MOVE BETA-ARR(IDX-CURR) TO BIT-A
COMPUTE BIT-B = 0 - BETA-ARR(IDX-CURR)
PERFORM DO-BIT-AND
MOVE ALFA-ARR(IDX-PARENT) TO BIT-A
MOVE BIT-RES TO BIT-B
PERFORM DO-BIT-OR
MOVE BIT-RES TO ALFA-ARR(IDX-CURR)
IF NODE-CHILD(IDX-CURR) NOT = 0
MOVE NODE-CHILD(IDX-CURR) TO CURR-NODE
ELSE
IF NODE-SIB(IDX-CURR) NOT = 0
MOVE NODE-SIB(IDX-CURR) TO CURR-NODE
ELSE
MOVE 0 TO BACKTRACK-DONE
PERFORM UNTIL BACKTRACK-DONE = 1
IF CURR-NODE = 0 OR
NODE-SIB(IDX-CURR) NOT = 0
MOVE 1 TO BACKTRACK-DONE
ELSE
MOVE NODE-PARENT(IDX-CURR) TO CURR-NODE
COMPUTE IDX-CURR = CURR-NODE + 1
END-IF
END-PERFORM
IF CURR-NODE = 0
MOVE 1 TO ALFA-DONE
ELSE
MOVE NODE-SIB(IDX-CURR) TO CURR-NODE
END-IF
END-IF
END-IF
END-PERFORM.
NCA-PARA.
COMPUTE IDX-X = NCA-X + 1
COMPUTE IDX-Y = NCA-Y + 1
IF BETA-ARR(IDX-X) <= BETA-ARR(IDX-Y)
MOVE BETA-ARR(IDX-Y) TO BIT-A
COMPUTE BIT-B = 0 - BETA-ARR(IDX-X)
PERFORM DO-BIT-AND
COMPUTE IDX-AND = BIT-RES + 1
MOVE LAM-ARR(IDX-AND) TO H-VAR
ELSE
MOVE BETA-ARR(IDX-X) TO BIT-A
COMPUTE BIT-B = 0 - BETA-ARR(IDX-Y)
PERFORM DO-BIT-AND
COMPUTE IDX-AND = BIT-RES + 1
MOVE LAM-ARR(IDX-AND) TO H-VAR
END-IF
MOVE ALFA-ARR(IDX-X) TO BIT-A
MOVE ALFA-ARR(IDX-Y) TO BIT-B
PERFORM DO-BIT-AND
MOVE BIT-RES TO TEMP-K
COMPUTE BIT-VAL = 1
COMPUTE BIT-SHIFT = H-VAR
PERFORM DO-BIT-SHIFT-LEFT
MOVE TEMP-K TO BIT-A
COMPUTE BIT-B = 0 - BIT-RES
PERFORM DO-BIT-AND
MOVE BIT-RES TO K-VAR
MOVE K-VAR TO BIT-A
COMPUTE BIT-B = 0 - K-VAR
PERFORM DO-BIT-AND
COMPUTE IDX-AND = BIT-RES + 1
MOVE LAM-ARR(IDX-AND) TO H-VAR
COMPUTE BIT-VAL = BETA-ARR(IDX-X)
COMPUTE BIT-SHIFT = H-VAR
PERFORM DO-BIT-SHIFT-RIGHT
MOVE BIT-RES TO BIT-A
MOVE 1 TO BIT-B
PERFORM DO-BIT-OR
MOVE BIT-RES TO BIT-VAL
COMPUTE BIT-SHIFT = H-VAR
PERFORM DO-BIT-SHIFT-LEFT
MOVE BIT-RES TO J-VAR
IF J-VAR NOT = BETA-ARR(IDX-X)
COMPUTE BIT-VAL = 1
COMPUTE BIT-SHIFT = H-VAR
PERFORM DO-BIT-SHIFT-LEFT
COMPUTE MASK-VAL = BIT-RES - 1
MOVE ALFA-ARR(IDX-X) TO BIT-A
MOVE MASK-VAL TO BIT-B
PERFORM DO-BIT-AND
COMPUTE IDX-AND = BIT-RES + 1
MOVE LAM-ARR(IDX-AND) TO L-VAR
COMPUTE BIT-VAL = BETA-ARR(IDX-X)
COMPUTE BIT-SHIFT = L-VAR
PERFORM DO-BIT-SHIFT-RIGHT
MOVE BIT-RES TO BIT-A
MOVE 1 TO BIT-B
PERFORM DO-BIT-OR
MOVE BIT-RES TO BIT-VAL
COMPUTE BIT-SHIFT = L-VAR
PERFORM DO-BIT-SHIFT-LEFT
COMPUTE IDX-TAU = BIT-RES + 1
MOVE TAU-ARR(IDX-TAU) TO NCA-X
COMPUTE IDX-X = NCA-X + 1
END-IF
IF J-VAR NOT = BETA-ARR(IDX-Y)
COMPUTE BIT-VAL = 1
COMPUTE BIT-SHIFT = H-VAR
PERFORM DO-BIT-SHIFT-LEFT
COMPUTE MASK-VAL = BIT-RES - 1
MOVE ALFA-ARR(IDX-Y) TO BIT-A
MOVE MASK-VAL TO BIT-B
PERFORM DO-BIT-AND
COMPUTE IDX-AND = BIT-RES + 1
MOVE LAM-ARR(IDX-AND) TO L-VAR
COMPUTE BIT-VAL = BETA-ARR(IDX-Y)
COMPUTE BIT-SHIFT = L-VAR
PERFORM DO-BIT-SHIFT-RIGHT
MOVE BIT-RES TO BIT-A
MOVE 1 TO BIT-B
PERFORM DO-BIT-OR
MOVE BIT-RES TO BIT-VAL
COMPUTE BIT-SHIFT = L-VAR
PERFORM DO-BIT-SHIFT-LEFT
COMPUTE IDX-TAU = BIT-RES + 1
MOVE TAU-ARR(IDX-TAU) TO NCA-Y
COMPUTE IDX-Y = NCA-Y + 1
END-IF
IF PI-ARR(IDX-X) <= PI-ARR(IDX-Y)
MOVE NCA-X TO NCA-RES
ELSE
MOVE NCA-Y TO NCA-RES
END-IF.
DO-BIT-AND.
MOVE 0 TO BIT-RES
MOVE 1 TO BIT-MUL
MOVE BIT-A TO TEMP-A
MOVE BIT-B TO TEMP-B
PERFORM UNTIL TEMP-A >= 0
COMPUTE TEMP-A = TEMP-A + 65536
END-PERFORM
PERFORM UNTIL TEMP-B >= 0
COMPUTE TEMP-B = TEMP-B + 65536
END-PERFORM
PERFORM VARYING BIT-IDX FROM 1 BY 1 UNTIL BIT-IDX > 16
DIVIDE TEMP-A BY 2 GIVING TEMP-A REMAINDER REM-A
DIVIDE TEMP-B BY 2 GIVING TEMP-B REMAINDER REM-B
IF REM-A = 1 AND REM-B = 1
COMPUTE BIT-RES = BIT-RES + BIT-MUL
END-IF
COMPUTE BIT-MUL = BIT-MUL * 2
END-PERFORM.
DO-BIT-OR.
MOVE 0 TO BIT-RES
MOVE 1 TO BIT-MUL
MOVE BIT-A TO TEMP-A
MOVE BIT-B TO TEMP-B
PERFORM UNTIL TEMP-A >= 0
COMPUTE TEMP-A = TEMP-A + 65536
END-PERFORM
PERFORM UNTIL TEMP-B >= 0
COMPUTE TEMP-B = TEMP-B + 65536
END-PERFORM
PERFORM VARYING BIT-IDX FROM 1 BY 1 UNTIL BIT-IDX > 16
DIVIDE TEMP-A BY 2 GIVING TEMP-A REMAINDER REM-A
DIVIDE TEMP-B BY 2 GIVING TEMP-B REMAINDER REM-B
IF REM-A = 1 OR REM-B = 1
COMPUTE BIT-RES = BIT-RES + BIT-MUL
END-IF
COMPUTE BIT-MUL = BIT-MUL * 2
END-PERFORM.
DO-BIT-SHIFT-LEFT.
COMPUTE BIT-MUL = 2 ** BIT-SHIFT
COMPUTE BIT-RES = BIT-VAL * BIT-MUL
DIVIDE BIT-RES BY 65536 GIVING BIT-DIV REMAINDER BIT-RES.
DO-BIT-SHIFT-RIGHT.
COMPUTE BIT-MUL = 2 ** BIT-SHIFT
DIVIDE BIT-VAL BY BIT-MUL GIVING BIT-RES.
- Output:
Test Case 1: Size: +000000010, Queries: +000000003 Values: -1 -1 1 1 1 1 3 10 10 10 Queries and Results: Query: 000000002 000000003 Result: 000000001 (Expected: 000000001) Query: 000000001 000000010 Result: 000000004 (Expected: 000000004) Query: 000000005 000000010 Result: 000000003 (Expected: 000000003)
import 'dart:math';
import 'dart:collection';
class Node {
int child = 0;
int sib = 0;
int parent = 0;
}
class Result {
List<int> pi;
List<int> beta;
List<int> alfa;
List<int> tau;
List<int> lam;
Result(this.pi, this.beta, this.alfa, this.tau, this.lam);
}
class TestCase {
int n;
List<int> values;
List<List<int>> queries;
List<int> expected;
TestCase(this.n, this.values, this.queries, this.expected);
}
// Static variables for traversal
int _p = 0;
int _n = 0;
int getP() => _p;
int getN() => _n;
bool traversal(List<Node> nodes, int initialP, int initialN, List<int> pi,
List<int> beta, List<int> tau, List<int> lam) {
_p = initialP;
_n = initialN;
// s3: Compute beta in the easy case
while (true) {
_n++;
pi[_p] = _n;
tau[_n] = 0;
lam[_n] = 1 + lam[_n >> 1];
if (nodes[_p].child != 0) {
_p = nodes[_p].child;
continue;
}
beta[_p] = _n;
break;
}
// s4: Compute tau, bottom-up
while (true) {
tau[beta[_p]] = nodes[_p].parent;
if (nodes[_p].sib != 0) {
_p = nodes[_p].sib;
return true; // Go back to s3
}
_p = nodes[_p].parent;
// Compute beta in the hard case
if (_p != 0) {
int h = lam[_n & -pi[_p]];
beta[_p] = ((_n >> h) | 1) << h;
} else {
return false; // Exit traversal
}
}
}
void compute_alfa(List<Node> nodes, int node, List<int> alfa, List<int> beta) {
// s7: Compute alfa, top-down
alfa[node] = alfa[nodes[node].parent] | (beta[node] & -beta[node]);
if (nodes[node].child != 0) {
compute_alfa(nodes, nodes[node].child, alfa, beta);
}
// s8: Continue traversal
if (nodes[node].sib != 0) {
compute_alfa(nodes, nodes[node].sib, alfa, beta);
}
}
int nca(int x, int y, List<int> beta, List<int> alfa,
List<int> tau, List<int> lam, List<int> pi) {
// Find common height
int h;
if (beta[x] <= beta[y]) {
h = lam[beta[y] & -beta[x]];
} else {
h = lam[beta[x] & -beta[y]];
}
// Find true height
int k = alfa[x] & alfa[y] & -(1 << h);
h = lam[k & -k];
// Find beta[z]
int j = ((beta[x] >> h) | 1) << h;
// Find x' and y'
if (j != beta[x]) {
int l = lam[alfa[x] & ((1 << h) - 1)];
x = tau[((beta[x] >> l) | 1) << l];
}
if (j != beta[y]) {
int l = lam[alfa[y] & ((1 << h) - 1)];
y = tau[((beta[y] >> l) | 1) << l];
}
// Find z
int z = (pi[x] <= pi[y]) ? x : y;
return z;
}
Result process(int N, List<int> A) {
List<int> pi = List<int>.filled(N + 1, 0);
List<int> beta = List<int>.filled(N + 1, 0);
List<int> alfa = List<int>.filled(N + 1, 0);
List<int> tau = List<int>.filled(N + 1, 0);
List<int> lam = List<int>.filled(N + 1, 0);
List<Node> nodes = List<Node>.generate(N + 1, (_) => Node());
// Make triply linked tree
int t = 0;
for (int v = N; v > 0; v--) {
int u = 0;
while (A[v] > A[t] || (A[v] == A[t] && v > t)) {
u = t;
t = nodes[t].parent;
}
if (u != 0) {
nodes[v].sib = nodes[u].sib;
nodes[u].sib = 0;
nodes[u].parent = v;
nodes[v].child = u;
} else {
nodes[v].sib = nodes[t].child;
}
nodes[t].child = v;
nodes[v].parent = t;
t = v;
}
// Begin first traversal
int p = nodes[0].child;
int n = 0;
lam[0] = -1;
while (traversal(nodes, p, n, pi, beta, tau, lam)) {
// Continue traversal
n = getN();
p = getP();
}
// Begin second traversal
p = nodes[0].child;
lam[0] = lam[n];
pi[0] = beta[0] = alfa[0] = 0;
// Perform second traversal
if (p != 0) {
compute_alfa(nodes, p, alfa, beta);
}
return Result(pi, beta, alfa, tau, lam);
}
List<int> solve_test_case(int n, List<int> values, List<List<int>> queries) {
List<int> results = [];
List<int> A = List<int>.filled(n + 2, 0);
A[0] = 1 << 30; // A[0] = MAX_INT
List<int> R = List<int>.filled(n + 2, 0);
List<int> B = List<int>.filled(n + 2, 0);
int N = 1;
int count = 0;
int? oldx;
for (int i = 1; i <= n; i++) {
int x = values[i - 1];
if (i > 1 && (oldx == null || x != oldx)) {
A[N] = count;
R[N] = i;
N++;
count = 0;
}
B[i] = N;
count++;
oldx = x;
}
A[N] = count;
R[N] = n + 1;
Result result = process(N, A);
List<int> pi = result.pi;
List<int> beta = result.beta;
List<int> alfa = result.alfa;
List<int> tau = result.tau;
List<int> lam = result.lam;
for (List<int> query in queries) {
int i = query[0];
int j = query[1];
int x = B[i];
int y = B[j];
int z;
if (x == y) {
z = j - i + 1;
} else {
if (x + 1 != y) {
z = A[nca(x + 1, y - 1, beta, alfa, tau, lam, pi)];
} else {
z = 0;
}
z = max(z, max(R[x] - i, A[y] - R[y] + j + 1));
}
results.add(z);
}
return results;
}
void main() {
// Hard-coded test data
List<TestCase> testCases = [];
testCases.add(TestCase(
10,
[-1, -1, 1, 1, 1, 1, 3, 10, 10, 10],
[[2, 3], [1, 10], [5, 10]],
[1, 4, 3]
));
for (int idx = 0; idx < testCases.length; idx++) {
TestCase test = testCases[idx];
int n = test.n;
List<int> values = test.values;
List<List<int>> queries = test.queries;
List<int> expected = test.expected;
print("Test Case ${idx + 1}:");
print("Size: $n, Queries: ${queries.length}");
print("Values: ${values.join(' ')}");
List<int> results = solve_test_case(n, values, queries);
print("Queries and Results:");
for (int q_idx = 0; q_idx < queries.length; q_idx++) {
List<int> query = queries[q_idx];
int result = results[q_idx];
int exp = expected[q_idx];
print("Query: ${query[0]} ${query[1]}");
print("Result: $result (Expected: $exp)");
if (result != exp) {
print(" WARNING: Result doesn't match expected output");
}
}
print("");
}
}
- Output:
Test Case 1: Size: 10, Queries: 3 Values: -1 -1 1 1 1 1 3 10 10 10 Queries and Results: Query: 2 3 Result: 1 (Expected: 1) Query: 1 10 Result: 4 (Expected: 4) Query: 5 10 Result: 3 (Expected: 3)
Type Node
child As Integer
sib As Integer
parent As Integer
End Type
Sub compute_alfa(node As Integer, nodes() As Node, beta() As Integer, alfa() As Integer)
' s7: Compute alfa, top-down
alfa(node) = alfa(nodes(node).parent) Or (beta(node) And -beta(node))
If nodes(node).child <> 0 Then compute_alfa(nodes(node).child, nodes(), beta(), alfa())
' s8: Continue traversal
If nodes(node).sib <> 0 Then compute_alfa(nodes(node).sib, nodes(), beta(), alfa())
End Sub
Sub process(N As Integer, A() As Integer, pi() As Integer, beta() As Integer, alfa() As Integer, tau() As Integer, lam() As Integer)
Dim As Node nodes(0 To 100)
' Make triply linked tree
Dim As Integer t = 0
For v As Integer = N To 1 Step -1
Dim As Integer u = 0
While A(v) > A(t) Or (A(v) = A(t) And v > t)
u = t
t = nodes(t).parent
Wend
If u <> 0 Then
nodes(v).sib = nodes(u).sib
nodes(u).sib = 0
nodes(u).parent = v
nodes(v).child = u
Else
nodes(v).sib = nodes(t).child
End If
nodes(t).child = v
nodes(v).parent = t
t = v
Next
' Begin first traversal
Dim As Integer p = nodes(0).child
Dim As Integer m = 0
lam(0) = -1
Do
' s3: Compute beta in the easy case
Do
m += 1
pi(p) = m
tau(m) = 0
lam(m) = 1 + lam(m Shr 1)
If nodes(p).child <> 0 Then
p = nodes(p).child
Else
beta(p) = m
Exit Do
End If
Loop
' s4: Compute tau, bottom-up
Do
tau(beta(p)) = nodes(p).parent
If nodes(p).sib <> 0 Then
p = nodes(p).sib
Exit Do
End If
p = nodes(p).parent
' Compute beta in the hard case
If p <> 0 Then
Dim h As Integer = lam(m And -pi(p))
beta(p) = ((m Shr h) Or 1) Shl h
Else
Exit Do, Do
End If
Loop
Loop While p <> 0
' Begin second traversal
p = nodes(0).child
lam(0) = lam(m)
pi(0) = 0 : beta(0) = 0 : alfa(0) = 0
' Perform second traversal
If p <> 0 Then compute_alfa(p, nodes(), beta(), alfa())
End Sub
Function nca(x As Integer, y As Integer, beta() As Integer, alfa() As Integer, tau() As Integer, lam() As Integer, pi() As Integer) As Integer
Dim As Integer h, k, j, l
' Find common height
If beta(x) <= beta(y) Then
h = lam(beta(y) And -beta(x))
Else
h = lam(beta(x) And -beta(y))
End If
' Find true height
k = alfa(x) And alfa(y) And -(1 Shl h)
If k = 0 Then
h = 0
Else
h = lam(k And -k)
End If
' Find beta[z]
j = ((beta(x) Shr h) Or 1) Shl h
' Find x' and y'
If j <> beta(x) Then
l = lam(alfa(x) And ((1 Shl h) - 1))
x = tau(((beta(x) Shr l) Or 1) Shl l)
End If
If j <> beta(y) Then
l = lam(alfa(y) And ((1 Shl h) - 1))
y = tau(((beta(y) Shr l) Or 1) Shl l)
End If
' Find z
Return Iif(pi(x) <= pi(y), x, y)
End Function
Sub solve_test_case(m As Integer, values() As Integer, queries() As Integer, num_queries As Integer, expected() As Integer)
Dim As Integer A(100), R(100), B(100)
Dim As Integer pi(100), beta(100), alfa(100), tau(100), lam(100)
A(0) = 2147483647
Dim As Integer N = 1, cnt = 0, oldx = 0
For i As Integer = 1 To m
Dim As Integer x = values(i)
If i > 1 And x <> oldx Then
A(N) = cnt
R(N) = i
N += 1
cnt = 0
End If
B(i) = N
cnt += 1
oldx = x
Next
A(N) = cnt
R(N) = m + 1
process(N, A(), pi(), beta(), alfa(), tau(), lam())
Print "Queries and Results:"
For q As Integer = 1 To num_queries
Dim As Integer i1 = queries((q - 1) * 2 + 1)
Dim As Integer j1 = queries((q - 1) * 2 + 2)
Dim As Integer x1 = B(i1)
Dim As Integer y1 = B(j1)
Dim As Integer z
If x1 = y1 Then
z = j1 - i1 + 1
Else
If x1 + 1 <> y1 Then
z = A(nca(x1 + 1, y1 - 1, beta(), alfa(), tau(), lam(), pi()))
Else
z = 0
End If
If (R(x1) - i1) > z Then z = R(x1) - i1
If (A(y1) - R(y1) + j1 + 1) > z Then z = A(y1) - R(y1) + j1 + 1
End If
Print "Query: "; i1; " "; j1
Print "Result: "; z; " (Expected: "; expected(q); ")"
If z <> expected(q) Then Print " WARNING: Result doesn't match expected output"
Next
Print
End Sub
' Hard-coded test data
Dim As Integer values(1 To 10) = {-1, -1, 1, 1, 1, 1, 3, 10, 10, 10}
Dim As Integer queries(1 To 6) = {2, 3, 1, 10, 5, 10}
Dim As Integer expected(1 To 3) = {1, 4, 3}
Print "Test Case 1:"
Print "Size: 10, Queries: 3"
Print "Values: ";
For i As Integer = 1 To 10
Print values(i); ' " ";
Next
Print
solve_test_case(10, values(), queries(), 3, expected())
Sleep
- Output:
Test Case 1: Size: 10, Queries: 3 Values: -1-1 1 1 1 1 3 10 10 10 Queries and Results: Query: 2 3 Result: 1 (Expected: 1) Query: 1 10 Result: 4 (Expected: 4) Query: 5 10 Result: 3 (Expected: 3)
package main
import (
"fmt"
"math"
)
type Node struct {
Child int
Sib int
Parent int
}
type Result struct {
Pi []int
Beta []int
Alfa []int
Tau []int
Lam []int
}
// Process function replicates the main logic
func process(N int, A []int) Result {
pi := make([]int, N+1)
beta := make([]int, N+1)
alfa := make([]int, N+1)
tau := make([]int, N+1)
lam := make([]int, N+1)
nodes := make([]Node, N+1)
// Make triply linked tree
t := 0
for v := N; v > 0; v-- {
u := 0
for A[v] > A[t] || (A[v] == A[t] && v > t) {
u = t
t = nodes[t].Parent
}
if u != 0 {
nodes[v].Sib = nodes[u].Sib
nodes[u].Sib = 0
nodes[u].Parent = v
nodes[v].Child = u
} else {
nodes[v].Sib = nodes[t].Child
}
nodes[t].Child = v
nodes[v].Parent = t
t = v
}
// First traversal
p := nodes[0].Child
n := 0
lam[0] = -1
for traversal(nodes, p, n, pi, beta, tau, lam) {
n = getN()
p = getP()
}
// Second traversal
p = nodes[0].Child
lam[0] = lam[n]
pi[0] = 0
beta[0] = 0
alfa[0] = 0
if p != 0 {
computeAlfa(nodes, p, alfa, beta)
}
return Result{Pi: pi, Beta: beta, Alfa: alfa, Tau: tau, Lam: lam}
}
// Static variables to simulate nonlocal variables
var p, n int
func getP() int {
return p
}
func getN() int {
return n
}
func traversal(nodes []Node, initialP, initialN int, pi, beta, tau, lam []int) bool {
p = initialP
n = initialN
for {
n++
pi[p] = n
tau[n] = 0
lam[n] = 1 + lam[n>>1]
if nodes[p].Child != 0 {
p = nodes[p].Child
continue
}
beta[p] = n
break
}
for {
tau[beta[p]] = nodes[p].Parent
if nodes[p].Sib != 0 {
p = nodes[p].Sib
return true
}
p = nodes[p].Parent
if p != 0 {
h := lam[n&-pi[p]]
beta[p] = ((n >> h) | 1) << h
} else {
return false
}
}
}
func computeAlfa(nodes []Node, node int, alfa, beta []int) {
alfa[node] = alfa[nodes[node].Parent] | (beta[node] & -beta[node])
if nodes[node].Child != 0 {
computeAlfa(nodes, nodes[node].Child, alfa, beta)
}
if nodes[node].Sib != 0 {
computeAlfa(nodes, nodes[node].Sib, alfa, beta)
}
}
func nca(x, y int, beta, alfa, tau, lam, pi []int) int {
var h int
if beta[x] <= beta[y] {
h = lam[beta[y]&-beta[x]]
} else {
h = lam[beta[x]&-beta[y]]
}
k := alfa[x] & alfa[y] & -(1 << h)
h = lam[k&-k]
j := ((beta[x] >> h) | 1) << h
if j != beta[x] {
l := lam[alfa[x]&((1<<h)-1)]
x = tau[((beta[x]>>l)|1)<<l]
}
if j != beta[y] {
l := lam[alfa[y]&((1<<h)-1)]
y = tau[((beta[y]>>l)|1)<<l]
}
if pi[x] <= pi[y] {
return x
}
return y
}
func solveTestCase(n int, values []int, queries [][]int) []int {
results := []int{}
A := make([]int, n+2)
A[0] = math.MaxInt32
R := make([]int, n+2)
B := make([]int, n+2)
N := 1
count := 0
var oldx *int
for i := 1; i <= n; i++ {
x := values[i-1]
if i > 1 && (oldx == nil || x != *oldx) {
A[N] = count
R[N] = i
N++
count = 0
}
B[i] = N
count++
oldx = &x
}
A[N] = count
R[N] = n + 1
result := process(N, A)
pi := result.Pi
beta := result.Beta
alfa := result.Alfa
tau := result.Tau
lam := result.Lam
for _, query := range queries {
i, j := query[0], query[1]
x, y := B[i], B[j]
var z int
if x == y {
z = j - i + 1
} else {
if x+1 != y {
z = A[nca(x+1, y-1, beta, alfa, tau, lam, pi)]
} else {
z = 0
}
z = max(z, max(R[x]-i, A[y]-R[y]+j+1))
}
results = append(results, z)
}
return results
}
func max(a, b int) int {
if a > b {
return a
}
return b
}
func main() {
testCases := []struct {
n int
values []int
queries [][]int
expected []int
}{
{
n: 10,
values: []int{-1, -1, 1, 1, 1, 1, 3, 10, 10, 10},
queries: [][]int{
{2, 3}, {1, 10}, {5, 10},
},
expected: []int{1, 4, 3},
},
}
for idx, testCase := range testCases {
fmt.Printf("Test Case %d:\n", idx+1)
results := solveTestCase(testCase.n, testCase.values, testCase.queries)
fmt.Println("Results:", results)
}
}
- Output:
Test Case 1: Results: [1 4 3]
import java.util.*;
class Main {
static Result process(int N, int[] A) {
int[] pi = new int[N + 1];
int[] beta = new int[N + 1];
int[] alfa = new int[N + 1];
int[] tau = new int[N + 1];
int[] lam = new int[N + 1];
Node[] nodes = new Node[N + 1];
for (int i = 0; i <= N; i++) {
nodes[i] = new Node();
}
// Make triply linked tree
int t = 0;
for (int v = N; v > 0; v--) {
int u = 0;
while (A[v] > A[t] || (A[v] == A[t] && v > t)) {
u = t;
t = nodes[t].parent;
}
if (u != 0) {
nodes[v].sib = nodes[u].sib;
nodes[u].sib = 0;
nodes[u].parent = v;
nodes[v].child = u;
} else {
nodes[v].sib = nodes[t].child;
}
nodes[t].child = v;
nodes[v].parent = t;
t = v;
}
// Begin first traversal
int p = nodes[0].child;
int n = 0;
lam[0] = -1;
while (traversal(nodes, p, n, pi, beta, tau, lam)) {
// Continue traversal
n = getN();
p = getP();
}
// Begin second traversal
p = nodes[0].child;
lam[0] = lam[n];
pi[0] = beta[0] = alfa[0] = 0;
// Perform second traversal
if (p != 0) {
compute_alfa(nodes, p, alfa, beta);
}
return new Result(pi, beta, alfa, tau, lam);
}
// These static variables are used to simulate the nonlocal variables in Python
private static int p;
private static int n;
private static int getP() {
return p;
}
private static int getN() {
return n;
}
static boolean traversal(Node[] nodes, int initialP, int initialN, int[] pi, int[] beta, int[] tau, int[] lam) {
p = initialP;
n = initialN;
// s3: Compute beta in the easy case
while (true) {
n++;
pi[p] = n;
tau[n] = 0;
lam[n] = 1 + lam[n >> 1];
if (nodes[p].child != 0) {
p = nodes[p].child;
continue;
}
beta[p] = n;
break;
}
// s4: Compute tau, bottom-up
while (true) {
tau[beta[p]] = nodes[p].parent;
if (nodes[p].sib != 0) {
p = nodes[p].sib;
return true; // Go back to s3
}
p = nodes[p].parent;
// Compute beta in the hard case
if (p != 0) {
int h = lam[n & -pi[p]];
beta[p] = ((n >> h) | 1) << h;
} else {
return false; // Exit traversal
}
}
}
static void compute_alfa(Node[] nodes, int node, int[] alfa, int[] beta) {
// s7: Compute alfa, top-down
alfa[node] = alfa[nodes[node].parent] | (beta[node] & -beta[node]);
if (nodes[node].child != 0) {
compute_alfa(nodes, nodes[node].child, alfa, beta);
}
// s8: Continue traversal
if (nodes[node].sib != 0) {
compute_alfa(nodes, nodes[node].sib, alfa, beta);
}
}
static int nca(int x, int y, int[] beta, int[] alfa, int[] tau, int[] lam, int[] pi) {
// Find common height
int h;
if (beta[x] <= beta[y]) {
h = lam[beta[y] & -beta[x]];
} else {
h = lam[beta[x] & -beta[y]];
}
// Find true height
int k = alfa[x] & alfa[y] & -(1 << h);
h = lam[k & -k];
// Find beta[z]
int j = ((beta[x] >> h) | 1) << h;
// Find x' and y'
if (j != beta[x]) {
int l = lam[alfa[x] & ((1 << h) - 1)];
x = tau[((beta[x] >> l) | 1) << l];
}
if (j != beta[y]) {
int l = lam[alfa[y] & ((1 << h) - 1)];
y = tau[((beta[y] >> l) | 1) << l];
}
// Find z
int z = (pi[x] <= pi[y]) ? x : y;
return z;
}
static List<Integer> solve_test_case(int n, int[] values, int[][] queries) {
List<Integer> results = new ArrayList<>();
int[] A = new int[n + 2];
A[0] = Integer.MAX_VALUE; // A[0]
int[] R = new int[n + 2];
int[] B = new int[n + 2];
int N = 1;
int count = 0;
Integer oldx = null;
for (int i = 1; i <= n; i++) {
int x = values[i - 1];
if (i > 1 && (oldx == null || x != oldx)) {
A[N] = count;
R[N] = i;
N++;
count = 0;
}
B[i] = N;
count++;
oldx = x;
}
A[N] = count;
R[N] = n + 1;
Result result = process(N, A);
int[] pi = result.pi;
int[] beta = result.beta;
int[] alfa = result.alfa;
int[] tau = result.tau;
int[] lam = result.lam;
for (int[] query : queries) {
int i = query[0];
int j = query[1];
int x = B[i];
int y = B[j];
int z;
if (x == y) {
z = j - i + 1;
} else {
if (x + 1 != y) {
z = A[nca(x + 1, y - 1, beta, alfa, tau, lam, pi)];
} else {
z = 0;
}
z = Math.max(z, Math.max(R[x] - i, A[y] - R[y] + j + 1));
}
results.add(z);
}
return results;
}
public static void main(String[] args) {
// Hard-coded test data
List<TestCase> testCases = new ArrayList<>();
testCases.add(new TestCase(
10,
new int[]{-1, -1, 1, 1, 1, 1, 3, 10, 10, 10},
new int[][]{{2, 3}, {1, 10}, {5, 10}},
new int[]{1, 4, 3}
));
for (int idx = 0; idx < testCases.size(); idx++) {
TestCase test = testCases.get(idx);
int n = test.n;
int[] values = test.values;
int[][] queries = test.queries;
int[] expected = test.expected;
System.out.println("Test Case " + (idx + 1) + ":");
System.out.println("Size: " + n + ", Queries: " + queries.length);
System.out.print("Values: ");
for (int value : values) {
System.out.print(value + " ");
}
System.out.println();
List<Integer> results = solve_test_case(n, values, queries);
System.out.println("Queries and Results:");
for (int q_idx = 0; q_idx < queries.length; q_idx++) {
int[] query = queries[q_idx];
int result = results.get(q_idx);
int exp = expected[q_idx];
System.out.println("Query: " + query[0] + " " + query[1]);
System.out.println("Result: " + result + " (Expected: " + exp + ")");
if (result != exp) {
System.out.println(" WARNING: Result doesn't match expected output");
}
}
System.out.println();
}
}
static class TestCase {
int n;
int[] values;
int[][] queries;
int[] expected;
public TestCase(int n, int[] values, int[][] queries, int[] expected) {
this.n = n;
this.values = values;
this.queries = queries;
this.expected = expected;
}
}
}
class Node {
int child = 0;
int sib = 0;
int parent = 0;
}
class Result {
int[] pi;
int[] beta;
int[] alfa;
int[] tau;
int[] lam;
public Result(int[] pi, int[] beta, int[] alfa, int[] tau, int[] lam) {
this.pi = pi;
this.beta = beta;
this.alfa = alfa;
this.tau = tau;
this.lam = lam;
}
}
- Output:
Test Case 1: Size: 10, Queries: 3 Values: -1 -1 1 1 1 1 3 10 10 10 Queries and Results: Query: 2 3 Result: 1 (Expected: 1) Query: 1 10 Result: 4 (Expected: 4) Query: 5 10 Result: 3 (Expected: 3)
class Node {
constructor() {
this.child = 0;
this.sib = 0;
this.parent = 0;
}
}
class Result {
constructor(pi, beta, alfa, tau, lam) {
this.pi = pi;
this.beta = beta;
this.alfa = alfa;
this.tau = tau;
this.lam = lam;
}
}
function process(N, A) {
const pi = Array(N + 1).fill(0);
const beta = Array(N + 1).fill(0);
const alfa = Array(N + 1).fill(0);
const tau = Array(N + 1).fill(0);
const lam = Array(N + 1).fill(0);
const nodes = Array.from({ length: N + 1 }, () => new Node());
let t = 0;
// Build triply linked tree
for (let v = N; v > 0; v--) {
let u = 0;
while (A[v] > A[t] || (A[v] === A[t] && v > t)) {
u = t;
t = nodes[t].parent;
}
if (u !== 0) {
nodes[v].sib = nodes[u].sib;
nodes[u].sib = 0;
nodes[u].parent = v;
nodes[v].child = u;
} else {
nodes[v].sib = nodes[t].child;
}
nodes[t].child = v;
nodes[v].parent = t;
t = v;
}
// First traversal
let p = nodes[0].child;
let n = 0;
lam[0] = -1;
while (traversal(nodes, p, n, pi, beta, tau, lam)) {
n = getN();
p = getP();
}
// Second traversal
p = nodes[0].child;
lam[0] = lam[n];
pi[0] = beta[0] = alfa[0] = 0;
if (p !== 0) {
computeAlfa(nodes, p, alfa, beta);
}
return new Result(pi, beta, alfa, tau, lam);
}
// Static variables to simulate nonlocal variables
let p, n;
function getP() {
return p;
}
function getN() {
return n;
}
function traversal(nodes, initialP, initialN, pi, beta, tau, lam) {
p = initialP;
n = initialN;
while (true) {
n++;
pi[p] = n;
tau[n] = 0;
lam[n] = 1 + lam[n >> 1];
if (nodes[p].child !== 0) {
p = nodes[p].child;
continue;
}
beta[p] = n;
break;
}
while (true) {
tau[beta[p]] = nodes[p].parent;
if (nodes[p].sib !== 0) {
p = nodes[p].sib;
return true;
}
p = nodes[p].parent;
if (p !== 0) {
const h = lam[n & -pi[p]];
beta[p] = ((n >> h) | 1) << h;
} else {
return false;
}
}
}
function computeAlfa(nodes, node, alfa, beta) {
alfa[node] = alfa[nodes[node].parent] | (beta[node] & -beta[node]);
if (nodes[node].child !== 0) {
computeAlfa(nodes, nodes[node].child, alfa, beta);
}
if (nodes[node].sib !== 0) {
computeAlfa(nodes, nodes[node].sib, alfa, beta);
}
}
function nca(x, y, beta, alfa, tau, lam, pi) {
let h;
if (beta[x] <= beta[y]) {
h = lam[beta[y] & -beta[x]];
} else {
h = lam[beta[x] & -beta[y]];
}
const k = alfa[x] & alfa[y] & -(1 << h);
h = lam[k & -k];
const j = ((beta[x] >> h) | 1) << h;
if (j !== beta[x]) {
const l = lam[alfa[x] & ((1 << h) - 1)];
x = tau[((beta[x] >> l) | 1) << l];
}
if (j !== beta[y]) {
const l = lam[alfa[y] & ((1 << h) - 1)];
y = tau[((beta[y] >> l) | 1) << l];
}
return pi[x] <= pi[y] ? x : y;
}
function solveTestCase(n, values, queries) {
const results = [];
const A = Array(n + 2).fill(0);
const R = Array(n + 2).fill(0);
const B = Array(n + 2).fill(0);
A[0] = Number.MAX_SAFE_INTEGER;
let N = 1;
let count = 0;
let oldx = null;
for (let i = 1; i <= n; i++) {
const x = values[i - 1];
if (i > 1 && (oldx === null || x !== oldx)) {
A[N] = count;
R[N] = i;
N++;
count = 0;
}
B[i] = N;
count++;
oldx = x;
}
A[N] = count;
R[N] = n + 1;
const result = process(N, A);
const { pi, beta, alfa, tau, lam } = result;
for (const query of queries) {
const [i, j] = query;
const x = B[i];
const y = B[j];
let z;
if (x === y) {
z = j - i + 1;
} else {
if (x + 1 !== y) {
z = A[nca(x + 1, y - 1, beta, alfa, tau, lam, pi)];
} else {
z = 0;
}
z = Math.max(z, Math.max(R[x] - i, A[y] - R[y] + j + 1));
}
results.push(z);
}
return results;
}
// Example usage
const testCases = [
{
n: 10,
values: [-1, -1, 1, 1, 1, 1, 3, 10, 10, 10],
queries: [
[2, 3],
[1, 10],
[5, 10],
],
expected: [1, 4, 3],
},
];
for (const testCase of testCases) {
const { n, values, queries, expected } = testCase;
const results = solveTestCase(n, values, queries);
console.log("Results:", results);
console.log("Expected:", expected);
}
- Output:
Results: [ 1, 4, 3 ] Expected: [ 1, 4, 3 ]
""" rosettacode.org/wiki/Schieber-Vishkin_algorithm """
""" Node structure for a triply linked tree. """
mutable struct Node{T <: Integer}
child::T
sib::T
parent::T
end
Node() = Node{Int}(0, 0, 0)
""" Process the input array `a` of size `n` into a triply linked tree
and return the vectors pi_, beta, alfa, tau, and lam.
"""
function process(n::Integer, a::Vector)::Tuple
pi_ = zeros(Int, n + 1) # pi is a builtin constant in Julia
beta = zeros(Int, n + 1)
alfa = zeros(Int, n + 1)
tau = zeros(Int, n + 1)
lam = zeros(Int, n + 1)
nodes = [Node() for _ in 1:n+1] # Create n+1 default Node objects
# Make triply linked tree
t = 0
for v in n:-1:1
u = 0
while a[v+1] > a[t+1] || (a[v+1] == a[t+1] && v > t)
u = t
t = nodes[t+1].parent
end
if u != 0
nodes[v+1].sib = nodes[u+1].sib
nodes[u+1].sib = 0
nodes[u+1].parent = v
nodes[v+1].child = u
else
nodes[v+1].sib = nodes[t+1].child
end
nodes[t+1].child = v
nodes[v+1].parent = t
t = v
end
# Begin first traversal
p = nodes[begin].child
n_count = 0
lam[begin] = -1
""" First traversal function """
function traversal()
while true
# s3: Compute beta in the easy case
n_count += 1
pi_[p+1] = n_count
tau[n_count+1] = 0
lam[n_count+1] = 1 + lam[(n_count >> 1) + 1]
if nodes[p+1].child != 0
p = nodes[p+1].child
continue # Go back to the beginning of the `while true` loop (s3)
end
beta[p+1] = n_count
break
end
# s4: Compute tau, bottom-up
while true
tau[beta[p+1]] = nodes[p+1].parent
if nodes[p+1].sib != 0
p = nodes[p+1].sib
return true
end
p = nodes[p+1].parent
# Compute beta in the hard case
if p != 0
h = lam[(n_count & (-pi_[p+1])) + 1] # Adjust index for lam access
beta[p+1] = ((n_count >> h) | 1) << h
else
return false # Exit traversal
end
end
end
# Perform first traversal
while traversal(); end
# Begin second traversal
p = nodes[begin].child
lam[begin] = lam[n_count+1]
pi_[begin] = 0
beta[begin] = 0
alfa[begin] = 0
""" Recursive function for second traversal """
function compute_alfa(node)
# s7: Compute alfa, top-down
alfa[node+1] = alfa[nodes[node+1].parent + 1] | (beta[node+1] & (-beta[node+1]))
if nodes[node+1].child != 0
compute_alfa(nodes[node+1].child)
end
# s8: Continue traversal
if nodes[node+1].sib != 0
compute_alfa(nodes[node+1].sib)
end
end
# Perform second (recursive) traversal if needed
p != 0 && compute_alfa(p)
return pi_, beta, alfa, tau, lam
end
""" Compute the nearest common ancestor (NCA) of two nodes x and y """
function nca(
x::Int,
y::Int,
beta::Vector{Int},
alfa::Vector{Int},
tau::Vector{Int},
lam::Vector{Int},
pi_::Vector{Int},
)
# Find common height
h = beta[x+1] <= beta[y+1] ? lam[(beta[y+1] & (-beta[x+1] + 1)) + 1] : lam[(beta[x+1] & (-beta[y+1]) + 1) + 1]
# Find true height
k = alfa[x+1] & alfa[y+1] & (~(1 << h) + 1) # `~X + 1` is `-X`
h = lam[(k & (-k)) + 1]
# Find beta[z]
j = ((beta[x+1] >> h) | 1) << h
# Find x' and y'
if j != beta[x+1]
l = lam[(alfa[x+1] & ((1 << h) - 1)) + 1]
x = tau[(((beta[x+1] >> l) | 1) << l) + 1]
end
if j != beta[y+1]
l = lam[(alfa[y+1] & ((1 << h) - 1)) + 1]
y = tau[(((beta[y+1] >> l) | 1) << l) + 1]
end
# Find z
return pi_[x+1] <= pi_[y+1] ? x : y
end
""" Solve a test case using Schieber-Vishkin given values and queries,
running the queries in parallel using threads.
"""
function schiebervishkin(
n::Int,
values::Vector{Int32},
queries::Vector{Tuple{Int, Int}},
)
results = zeros(Int32, length(queries))
a = Int[typemax(Int32)]
r = zeros(Int, n + 2)
b = zeros(Int, n + 2)
big_n = 1
count = 0
oldx = nothing
for i in 1:n
x = values[i]
if i > 1 && x != oldx
push!(a, count)
r[big_n+1] = i
big_n += 1
count = 0
end
b[i] = big_n
count += 1
oldx = x # Store the value directly
end
push!(a, count)
r[big_n+1] = n + 1
(pi_, beta, alfa, tau, lam) = process(big_n, a)
Threads.@threads for t in eachindex(queries)
i, j = queries[t]
x, y = b[i], b[j]
z = 0
if x == y
z = (j - i + 1)
else
if x + 1 != y
z = a[nca(x + 1, y - 1, beta, alfa, tau, lam, pi_) + 1]
end
z = max(z, r[x+1] - i, a[y+1] - (r[y+1] - j - 1))
end
results[t] = z
end
return results
end
function main()
# Hard-coded test data
test_cases = [
(
10, # n
Int32[-1, -1, 1, 1, 1, 1, 3, 10, 10, 10], # values (Int32)
[(2, 3), (1, 10), (5, 10)], # queries (Tuple of Int)
Int32[1, 4, 3] # expected (Int32)
)
]
for (idx, (n, values, queries, expected)) in enumerate(test_cases)
println("Test Case $(idx):")
println("Size: $(n), Queries: $(length(queries))")
println("Values: ", join(map(string, values), " "))
results = schiebervishkin(n, values, queries)
println("Queries and Results:")
for q_idx in eachindex(queries)
i, j = queries[q_idx]
result = results[q_idx]
exp = expected[q_idx]
println("Query: $(i) $(j)")
println("Result: $(result) (Expected: $(exp))")
if result != exp
println(" WARNING: Result doesn't match expected output")
end
end
println()
end
end
main()
- Output:
Test Case 1: Size: 10, Queries: 3 Values: -1 -1 1 1 1 1 3 10 10 10 Queries and Results: Query: 2 3 Result: 1 (Expected: 1) Query: 1 10 Result: 4 (Expected: 4) Query: 5 10 Result: 3 (Expected: 3)
import java.util.*
data class Node(
var child: Int = 0,
var sib: Int = 0,
var parent: Int = 0
)
data class Result(
val pi: IntArray,
val beta: IntArray,
val alfa: IntArray,
val tau: IntArray,
val lam: IntArray
)
data class TestCase(
val n: Int,
val values: IntArray,
val queries: Array<IntArray>,
val expected: IntArray
)
class CodeKt{
// These variables are used to simulate the nonlocal variables in Python
private var p = 0
private var n = 0
private fun getP(): Int = p
private fun getN(): Int = n
fun process(N: Int, A: IntArray): Result {
val pi = IntArray(N + 1)
val beta = IntArray(N + 1)
val alfa = IntArray(N + 1)
val tau = IntArray(N + 1)
val lam = IntArray(N + 1)
val nodes = Array(N + 1) { Node() }
// Make triply linked tree
var t = 0
for (v in N downTo 1) {
var u = 0
while (A[v] > A[t] || (A[v] == A[t] && v > t)) {
u = t
t = nodes[t].parent
}
if (u != 0) {
nodes[v].sib = nodes[u].sib
nodes[u].sib = 0
nodes[u].parent = v
nodes[v].child = u
} else {
nodes[v].sib = nodes[t].child
}
nodes[t].child = v
nodes[v].parent = t
t = v
}
// Begin first traversal
var p = nodes[0].child
var n = 0
lam[0] = -1
while (traversal(nodes, p, n, pi, beta, tau, lam)) {
// Continue traversal
n = getN()
p = getP()
}
// Begin second traversal
p = nodes[0].child
lam[0] = lam[n]
pi[0] = 0
beta[0] = 0
alfa[0] = 0
// Perform second traversal
if (p != 0) {
computeAlfa(nodes, p, alfa, beta)
}
return Result(pi, beta, alfa, tau, lam)
}
fun traversal(nodes: Array<Node>, initialP: Int, initialN: Int, pi: IntArray, beta: IntArray, tau: IntArray, lam: IntArray): Boolean {
p = initialP
n = initialN
// s3: Compute beta in the easy case
while (true) {
n++
pi[p] = n
tau[n] = 0
lam[n] = 1 + lam[n shr 1]
if (nodes[p].child != 0) {
p = nodes[p].child
continue
}
beta[p] = n
break
}
// s4: Compute tau, bottom-up
while (true) {
tau[beta[p]] = nodes[p].parent
if (nodes[p].sib != 0) {
p = nodes[p].sib
return true // Go back to s3
}
p = nodes[p].parent
// Compute beta in the hard case
if (p != 0) {
val h = lam[n and -pi[p]]
beta[p] = ((n shr h) or 1) shl h
} else {
return false // Exit traversal
}
}
}
fun computeAlfa(nodes: Array<Node>, node: Int, alfa: IntArray, beta: IntArray) {
// s7: Compute alfa, top-down
alfa[node] = alfa[nodes[node].parent] or (beta[node] and -beta[node])
if (nodes[node].child != 0) {
computeAlfa(nodes, nodes[node].child, alfa, beta)
}
// s8: Continue traversal
if (nodes[node].sib != 0) {
computeAlfa(nodes, nodes[node].sib, alfa, beta)
}
}
fun nca(x: Int, y: Int, beta: IntArray, alfa: IntArray, tau: IntArray, lam: IntArray, pi: IntArray): Int {
// Find common height
val h = if (beta[x] <= beta[y]) {
lam[beta[y] and -beta[x]]
} else {
lam[beta[x] and -beta[y]]
}
// Find true height
val k = alfa[x] and alfa[y] and -(1 shl h)
val trueH = lam[k and -k]
// Find beta[z]
val j = ((beta[x] shr trueH) or 1) shl trueH
// Find x' and y'
var newX = x
var newY = y
if (j != beta[x]) {
val l = lam[alfa[x] and ((1 shl trueH) - 1)]
newX = tau[((beta[x] shr l) or 1) shl l]
}
if (j != beta[y]) {
val l = lam[alfa[y] and ((1 shl trueH) - 1)]
newY = tau[((beta[y] shr l) or 1) shl l]
}
// Find z
return if (pi[newX] <= pi[newY]) newX else newY
}
fun solveTestCase(n: Int, values: IntArray, queries: Array<IntArray>): List<Int> {
val results = mutableListOf<Int>()
val A = IntArray(n + 2)
A[0] = Int.MAX_VALUE // A[0]
val R = IntArray(n + 2)
val B = IntArray(n + 2)
var N = 1
var count = 0
var oldX: Int? = null
for (i in 1..n) {
val x = values[i - 1]
if (i > 1 && (oldX == null || x != oldX)) {
A[N] = count
R[N] = i
N++
count = 0
}
B[i] = N
count++
oldX = x
}
A[N] = count
R[N] = n + 1
val result = process(N, A)
val pi = result.pi
val beta = result.beta
val alfa = result.alfa
val tau = result.tau
val lam = result.lam
for (query in queries) {
val i = query[0]
val j = query[1]
val x = B[i]
val y = B[j]
val z = if (x == y) {
j - i + 1
} else {
val commonAncestorValue = if (x + 1 != y) {
A[nca(x + 1, y - 1, beta, alfa, tau, lam, pi)]
} else {
0
}
maxOf(commonAncestorValue, maxOf(R[x] - i, A[y] - R[y] + j + 1))
}
results.add(z)
}
return results
}
@JvmStatic
fun main(args: Array<String>) {
// Hard-coded test data
val testCases = listOf(
TestCase(
10,
intArrayOf(-1, -1, 1, 1, 1, 1, 3, 10, 10, 10),
arrayOf(
intArrayOf(2, 3),
intArrayOf(1, 10),
intArrayOf(5, 10)
),
intArrayOf(1, 4, 3)
)
)
for ((idx, test) in testCases.withIndex()) {
val n = test.n
val values = test.values
val queries = test.queries
val expected = test.expected
println("Test Case ${idx + 1}:")
println("Size: $n, Queries: ${queries.size}")
print("Values: ")
values.forEach { print("$it ") }
println()
val results = solveTestCase(n, values, queries)
println("Queries and Results:")
for (qIdx in queries.indices) {
val query = queries[qIdx]
val result = results[qIdx]
val exp = expected[qIdx]
println("Query: ${query[0]} ${query[1]}")
println("Result: $result (Expected: $exp)")
if (result != exp) {
println(" WARNING: Result doesn't match expected output")
}
}
println()
}
}
}
- Output:
Test Case 1: Size: 10, Queries: 3 Values: -1 -1 1 1 1 1 3 10 10 10 Queries and Results: Query: 2 3 Result: 1 (Expected: 1) Query: 1 10 Result: 4 (Expected: 4) Query: 5 10 Result: 3 (Expected: 3)
-- WARNING: horrible mashup of 0|1|2-based indexing, and logical|bitwise|math operations (tee-hee!)
enum CHILD,SIB,PARENT
--enum PIE,BETA,ALFA,TAU,LAM -- (not actually used anymore)
function computeAlfa(integer node, sequence alfa, beta, nodes)
node += 1
alfa[node] = alfa[nodes[node][PARENT]+1] || (beta[node] && -beta[node])
if nodes[node][CHILD]!=0 then
alfa = computeAlfa(nodes[node][CHILD],alfa,beta,nodes)
end if
if nodes[node][SIB]!=0 then
alfa = computeAlfa(nodes[node][SIB],alfa,beta,nodes)
end if
return alfa
end function
function process(integer N, sequence A)
sequence pie = repeat(0,N+1),
beta = repeat(0,N+1),
alfa = repeat(0,N+1),
tau = repeat(0,N+1),
lam = repeat(0,N+1),
nodes = repeat({0,0,0},N+1)
-- Make triply linked tree.
integer t = 1
for v=N+1 to 2 by -1 do
integer u = 0
while A[v]>A[t] or (A[v]==A[t] and v>t) do
u = t
t = nodes[t][PARENT]+1
end while
if u!=0 then
nodes[v][SIB] = nodes[u][SIB]
nodes[u][SIB] = 0
nodes[u][PARENT] = v-1
nodes[v][CHILD] = u-1
else
nodes[v][SIB] = nodes[t][CHILD]
end if
nodes[t][CHILD] = v-1
nodes[v][PARENT] = t-1
t = v
end for
-- First traversal.
integer p = nodes[1][CHILD]+1, n = 0
lam[1] = -1
bool done = false
while not done do
-- Compute beta in the easy case.
while true do
n += 1
pie[p] = n
tau[n+1] = 0
lam[n+1] = 1 + lam[(n>>1)+1]
if nodes[p][CHILD]=0 then
beta[p] = n
exit
end if
p = nodes[p][CHILD]+1
end while
-- Compute tau, bottom-up.
while true do
tau[beta[p]] = nodes[p][PARENT]
if nodes[p][SIB]!=0 then
p = nodes[p][SIB]+1
exit
end if
p = nodes[p][PARENT]+1
if p=1 then
done = true
exit
end if
-- Compute beta in the hard case.
integer h = lam[(n&&-pie[p])+1]
beta[p] = ((n>>h)||1) << h
end while
end while
-- Second traversal.
p = nodes[1][CHILD]
lam[1] = lam[n]
alfa[1] = 0
beta[1] = 0
pie[1] = 0
if p!=0 then
alfa = computeAlfa(p,alfa,beta,nodes)
end if
return {pie, beta, alfa, tau, lam}
end function
function nca(integer x, y, sequence r)
sequence {pie, beta, alfa, tau, lam} = r
x += 1
y += 1
-- Find common height.
integer h = iff(beta[x]<=beta[y]?lam[(beta[y]&&-beta[x])+1]
:lam[(beta[x]&&-beta[y])+1])
-- Find true height.
integer k = alfa[x]&&alfa[y]&&-(1<<h)
h = lam[(k&&-k)+1]
-- Find beta[z].
integer j = ((beta[x]>>h)||1) << h
-- Find x' and y'.
integer l
if j != beta[x] then
l = lam[(alfa[x]&&((1<<h)-1))+1]
x = tau[(((beta[x]>>l)||1)<<l)+1]
end if
if j != beta[y] then
l = lam[(alfa[y]&&((1<<h)-1))+1]
y = tau[(((beta[y]>>l)||1)<<l)+1]
end if
-- Find z.
integer z = iff(pie[x]<=pie[y] ? x : y)
return z
end function
function solve_test_case(integer n, sequence v, queries)
sequence res = {},
A = {power(2,30)},
R = repeat(0,n),
B = repeat(0,n)
integer N = 1,
count = 0,
oldx = -1
for i,x in v do
if i>1 and x!=oldx then
A &= count
R[N] = i
N += 1
count = 0
end if
B[i] = N
count += 1
oldx = x
end for
A &= count
R[N] = n+1
sequence r = process(N,A)
for t in queries do
integer {i,j} = t,
x = B[i],
y = B[j],
z = j-i+1 -- (x==y case)
if x!=y then
z = iff(x+1!=y?A[nca(x+1, y-1, r)]:0)
z = max(z,max(R[x]-i,A[y+1]-R[y]+j+1))
end if
res &= z
end for
return res
end function
constant tests = {
{{-1, -1, 1, 1, 1, 1, 3, 10, 10, 10},
{{{2,3},1},{{1,10},4},{{5,10},3}}}
}
for idx, t in tests do
sequence {v,q} = t
integer n = length(v)
printf(1,"Test Case %d:\n",idx)
printf(1,"Size: %d, Queries: %d\n",{n,length(q)})
printf(1,"Values: %s\n",{join(v,fmt:="%d")})
sequence results = solve_test_case(n,v,vslice(q,1))
printf(1,"Queries and Results:\n")
for qdx,qe in q do
integer {{i,j},e} = qe,
result = results[qdx]
printf(1,"Query: %d %d\n",{i,j})
printf(1,"Result: %d (Expected: %d)\n",{result,e})
if result!=e then
printf(1," WARNING: Result doesn't match expected output\n")
end if
end for
printf(1,"\n")
end for
- Output:
Test Case 1: Size: 10, Queries: 3 Values: -1 -1 1 1 1 1 3 10 10 10 Queries and Results: Query: 2 3 Result: 1 (Expected: 1) Query: 1 10 Result: 4 (Expected: 4) Query: 5 10 Result: 3 (Expected: 3)
Although Pluto arrays use 1-based indexing by default, they can in fact be indexed from any integer.
I've therefore used 0-based indexing for the working arrays (and noted where this has been done) to make the translation from Python easier.
local class Node
function __construct()
self.child = 0
self.sib = 0
self.parnt = 0 -- NOTE: parent is a reserved word
end
end
local class Result
-- NOTE: 0-based indexing used for all 5 arrays.
function __construct(pi, beta, alfa, tau, lam)
self.pi = pi
self.beta = beta
self.alfa = alfa
self.tau = tau
self.lam = lam
end
end
-- NOTE: A is a 0-based array.
local function process(N, A)
-- NOTE: 0-based indexing used for all 6 of the following arrays.
local pi = {}
local beta = {}
local alfa = {}
local tau = {}
local lam = {}
local nodes = {}
for i = 0, N do
pi[i] = 0
beta[i] = 0
alfa[i] = 0
tau[i] = 0
lam[i] = 0
nodes[i] = new Node()
end
-- Make triply linked tree.
local t = 0
for v = N, 1, -1 do
local u = 0
while A[v] > A[t] or (A[v] == A[t] and v > t) do
u = t
t = nodes[t].parnt
end
if u != 0 then
nodes[v].sib = nodes[u].sib
nodes[u].sib = 0
nodes[u].parnt = v
nodes[v].child = u
else
nodes[v].sib = nodes[t].child
end
nodes[t].child = v
nodes[v].parnt = t
t = v
end
-- Begin first traversal.
local p = nodes[0].child
local n = 0
lam[0] = -1
local function traversal()
-- s3: Compute beta in the easy case.
while true do
++n
pi[p] = n
tau[n] = 0
lam[n] = 1 + lam[n >> 1]
if nodes[p].child != 0 then
p = nodes[p].child
continue
end
beta[p] = n
break
end
-- s4: Compute tau, bottom-up.
while true do
tau[beta[p]] = nodes[p].parnt
if nodes[p].sib != 0 then
p = nodes[p].sib
return true -- go back to s3
end
p = nodes[p].parnt
-- Compute beta in the hard case.
if p != 0 then
local h = lam[n & -pi[p]]
beta[p] = ((n >> h) | 1) << h
else
return false -- exit traversal
end
end
end
-- Perform first traversal.
while traversal() do ; end
-- Begin second traversal.
p = nodes[0].child
lam[0] = lam[n]
alfa[0] = 0
beta[0] = 0
pi[0] = 0
local function computeAlfa(node)
-- s7: Compute alfa, top-down.
alfa[node] = alfa[nodes[node].parnt] | (beta[node] & -beta[node])
if nodes[node].child != 0 then
computeAlfa(nodes[node].child)
end
-- s8: Continue traversal.
if nodes[node].sib != 0 then
computeAlfa(nodes[node].sib)
end
end
-- Perform second traversal.
if p != 0 then computeAlfa(p) end
return new Result(pi, beta, alfa, tau, lam)
end
-- NOTE: All 5 incoming arrays are 0-based.
local function nca(x, y, beta, alfa, tau, lam, pi)
-- Find common height.
local h
if beta[x] <= beta[y] then
h = lam[beta[y] & -beta[x]]
else
h = lam[beta[x] & -beta[y]]
end
-- Find true height.
local k = alfa[x] & alfa[y] & -(1 << h)
h = lam[k & -k]
-- Find beta[z].
local j = ((beta[x] >> h) | 1) << h
-- Find x' and y'.
local l
if j != beta[x] then
l = lam[alfa[x] & ((1 << h) - 1)]
x = tau[((beta[x] >> l) | 1) << l]
end
if j != beta[y] then
l = lam[alfa[y] & ((1 << h) - 1)]
y = tau[((beta[y] >> l) | 1) << l]
end
-- Find z.
local z = pi[x] <= pi[y] ? x : y
return z
end
local function solve_test_case(n, values, queries)
local results = {}
-- NOTE: A, R and B are 0-based arrays.
local A = {}
A[0] = math.maxinteger
local R = {}
local B = {}
for i = 0, n + 1 do
R[i] = 0
B[i] = 0
end
local N = 1
local count = 0
local oldx = nil
for i = 1, n do
local x = values[i] -- values is 1-based
if i > 1 and x != oldx then
A:insert(count)
R[N] = i
N += 1
count = 0
end
B[i] = N
count += 1
oldx = x
end
A:insert(count)
R[N] = n + 1
local r = process(N, A)
for queries as t do -- t is 1-based
local i = t[1]
local j = t[2]
local x = B[i]
local y = B[j]
local z
if x == y then
z = j - i + 1
else
if x + 1 != y then
z = A[nca(x + 1, y - 1, r.beta, r.alfa, r.tau, r.lam, r.pi)]
else
z = 0
end
z = math.max(z, math.max(R[x] - i, A[y] - R[y] + j + 1))
end
results:insert(z)
end
return results
end
-- Hard-coded test data.
local testCases = {
{
n = 10,
values = {-1, -1, 1, 1, 1, 1, 3, 10, 10, 10},
queries = {{2, 3}, {1, 10}, {5, 10}},
expected = {1, 4, 3}
}
}
for idx, test in testCases do
local n = test["n"]
local values = test["values"]
local queries = test["queries"]
local expected = test["expected"]
print($"Test Case {idx}:")
print($"Size: {n}, Queries: {#queries}")
print($"Values: {values:concat(" ")}")
local results = solve_test_case(n, values, queries)
print("Queries and Results:")
for qIdx = 1, #queries do
local q = queries[qIdx]
local i = q[1]
local j = q[2]
local result = results[qIdx]
local exp = expected[qIdx]
print($"Query: {i} {j}")
print($"Result: {result} (Expected: {exp})")
if result != exp then
print(" WARNING: Result doesn't match expected output")
end
end
print()
end
- Output:
Test Case 1: Size: 10, Queries: 3 Values: -1 -1 1 1 1 1 3 10 10 10 Queries and Results: Query: 2 3 Result: 1 (Expected: 1) Query: 1 10 Result: 4 (Expected: 4) Query: 5 10 Result: 3 (Expected: 3)
Structure Node
child.i
sib.i
parent.i
EndStructure
Procedure compute_alfa(node, Array nodes.Node(1), Array beta.i(1), Array alfa.i(1))
alfa(node) = alfa(nodes(node)\parent) | (beta(node) & -beta(node))
If nodes(node)\child <> 0
compute_alfa(nodes(node)\child, nodes(), beta(), alfa())
EndIf
If nodes(node)\sib <> 0
compute_alfa(nodes(node)\sib, nodes(), beta(), alfa())
EndIf
EndProcedure
Procedure process(N, Array A.i(1), Array pi.i(1), Array beta.i(1), Array alfa.i(1), Array tau.i(1), Array lam.i(1))
Dim nodes.Node(100)
t = 0
For v = N To 1 Step -1
u = 0
While A(v) > A(t) Or (A(v) = A(t) And v > t)
u = t
t = nodes(t)\parent
Wend
If u <> 0
nodes(v)\sib = nodes(u)\sib
nodes(u)\sib = 0
nodes(u)\parent = v
nodes(v)\child = u
Else
nodes(v)\sib = nodes(t)\child
EndIf
nodes(t)\child = v
nodes(v)\parent = t
t = v
Next
p = nodes(0)\child
m = 0
lam(0) = -1
Repeat
Repeat
m + 1
pi(p) = m
tau(m) = 0
lam(m) = 1 + lam(m >> 1)
If nodes(p)\child <> 0
p = nodes(p)\child
Else
beta(p) = m
Break
EndIf
ForEver
Repeat
tau(beta(p)) = nodes(p)\parent
If nodes(p)\sib <> 0
p = nodes(p)\sib
Break
EndIf
p = nodes(p)\parent
If p <> 0
h = lam(m & -pi(p))
beta(p) = ((m >> h) | 1) << h
Else
Break 2
EndIf
ForEver
Until p = 0
p = nodes(0)\child
lam(0) = lam(m)
pi(0) = 0 : beta(0) = 0 : alfa(0) = 0
If p <> 0
compute_alfa(p, nodes(), beta(), alfa())
EndIf
EndProcedure
Procedure.i nca(x, y, Array beta.i(1), Array alfa.i(1), Array tau.i(1), Array lam.i(1), Array pi.i(1))
If beta(x) <= beta(y)
h = lam(beta(y) & -beta(x))
Else
h = lam(beta(x) & -beta(y))
EndIf
k = alfa(x) & alfa(y) & -(1 << h)
If k = 0
h = 0
Else
h = lam(k & -k)
EndIf
j = ((beta(x) >> h) | 1) << h
If j <> beta(x)
l = lam(alfa(x) & ((1 << h) - 1))
x = tau(((beta(x) >> l) | 1) << l)
EndIf
If j <> beta(y)
l = lam(alfa(y) & ((1 << h) - 1))
y = tau(((beta(y) >> l) | 1) << l)
EndIf
If pi(x) <= pi(y)
ProcedureReturn x
Else
ProcedureReturn y
EndIf
EndProcedure
Procedure solve_test_case(m, Array values.i(1), Array queries.i(1), num_queries, Array expected.i(1))
Dim A.i(100)
Dim R.i(100)
Dim B.i(100)
Dim pi.i(100)
Dim beta.i(100)
Dim alfa.i(100)
Dim tau.i(100)
Dim lam.i(100)
A(0) = 2147483647
N = 1 : cnt = 0 : oldx = 0
For i = 1 To m
x = values(i)
If i > 1 And x <> oldx
A(N) = cnt
R(N) = i
N + 1
cnt = 0
EndIf
B(i) = N
cnt + 1
oldx = x
Next
A(N) = cnt
R(N) = m + 1
process(N, A(), pi(), beta(), alfa(), tau(), lam())
PrintN("Queries and Results:")
For q = 1 To num_queries
i1 = queries((q - 1) * 2 + 1)
j1 = queries((q - 1) * 2 + 2)
x1 = B(i1)
y1 = B(j1)
z = 0
If x1 = y1
z = j1 - i1 + 1
Else
If x1 + 1 <> y1
z = A(nca(x1 + 1, y1 - 1, beta(), alfa(), tau(), lam(), pi()))
Else
z = 0
EndIf
If (R(x1) - i1) > z : z = R(x1) - i1 : EndIf
If (A(y1) - R(y1) + j1 + 1) > z : z = A(y1) - R(y1) + j1 + 1 : EndIf
EndIf
PrintN("Query: " + Str(i1) + " " + Str(j1))
PrintN("Result: " + Str(z) + " (Expected: " + Str(expected(q)) + ")")
If z <> expected(q)
PrintN(" WARNING: Result doesn't match expected output")
EndIf
Next
PrintN("")
EndProcedure
OpenConsole()
Dim values.i(10)
Dim queries.i(6)
Dim expected.i(3)
values(1) = -1 : values(2) = -1 : values(3) = 1 : values(4) = 1 : values(5) = 1
values(6) = 1 : values(7) = 3 : values(8) = 10 : values(9) = 10 : values(10) = 10
queries(1) = 2 : queries(2) = 3
queries(3) = 1 : queries(4) = 10
queries(5) = 5 : queries(6) = 10
expected(1) = 1 : expected(2) = 4 : expected(3) = 3
PrintN("Test Case 1:")
PrintN("Size: 10, Queries: 3")
Print("Values:")
For i = 1 To 10
Print(" " + Str(values(i)))
Next
PrintN("")
solve_test_case(10, values(), queries(), 3, expected())
PrintN(#CRLF$ + "Press ENTER to exit"): Input()
CloseConsole()
- Output:
Similar to FreeBASIC entry.
import sys
from typing import List, Tuple
class Node:
def __init__(self):
self.child = 0
self.sib = 0
self.parent = 0
def process(N: int, A: List[int]) -> Tuple[List[int], List[int], List[int], List[int], List[int]]:
pi = [0] * (N + 1)
beta = [0] * (N + 1)
alfa = [0] * (N + 1)
tau = [0] * (N + 1)
lam = [0] * (N + 1)
nodes = [Node() for _ in range(N + 1)]
# Make triply linked tree
t = 0
for v in range(N, 0, -1):
u = 0
while A[v] > A[t] or (A[v] == A[t] and v > t):
u = t
t = nodes[t].parent
if u:
nodes[v].sib = nodes[u].sib
nodes[u].sib = 0
nodes[u].parent = v
nodes[v].child = u
else:
nodes[v].sib = nodes[t].child
nodes[t].child = v
nodes[v].parent = t
t = v
# Begin first traversal
p = nodes[0].child
n = 0
lam[0] = -1
def traversal():
nonlocal p, n
# s3: Compute beta in the easy case
while True:
n += 1
pi[p] = n
tau[n] = 0
lam[n] = 1 + lam[n >> 1]
if nodes[p].child:
p = nodes[p].child
continue
beta[p] = n
break
# s4: Compute tau, bottom-up
while True:
tau[beta[p]] = nodes[p].parent
if nodes[p].sib:
p = nodes[p].sib
return True # Go back to s3
p = nodes[p].parent
# Compute beta in the hard case
if p:
h = lam[n & -pi[p]]
beta[p] = ((n >> h) | 1) << h
else:
return False # Exit traversal
# Perform first traversal
while traversal():
pass
# Begin second traversal
p = nodes[0].child
lam[0] = lam[n]
pi[0] = beta[0] = alfa[0] = 0
def compute_alfa(node):
nonlocal p
# s7: Compute alfa, top-down
alfa[node] = alfa[nodes[node].parent] | (beta[node] & -beta[node])
if nodes[node].child:
compute_alfa(nodes[node].child)
# s8: Continue traversal
if nodes[node].sib:
compute_alfa(nodes[node].sib)
# Perform second traversal
if p:
compute_alfa(p)
return pi, beta, alfa, tau, lam
def nca(x: int, y: int, beta: List[int], alfa: List[int], tau: List[int], lam: List[int], pi: List[int]) -> int:
# Find common height
if beta[x] <= beta[y]:
h = lam[beta[y] & -beta[x]]
else:
h = lam[beta[x] & -beta[y]]
# Find true height
k = alfa[x] & alfa[y] & -(1 << h)
h = lam[k & -k]
# Find beta[z]
j = ((beta[x] >> h) | 1) << h
# Find x' and y'
if j != beta[x]:
l = lam[alfa[x] & ((1 << h) - 1)]
x = tau[((beta[x] >> l) | 1) << l]
if j != beta[y]:
l = lam[alfa[y] & ((1 << h) - 1)]
y = tau[((beta[y] >> l) | 1) << l]
# Find z
z = x if pi[x] <= pi[y] else y
return z
def solve_test_case(n: int, values: List[int], queries: List[Tuple[int, int]]) -> List[int]:
results = []
A = [sys.maxsize] # A[0]
R = [0] * (n + 2)
B = [0] * (n + 2)
N = 1
count = 0
oldx = None
for i in range(1, n + 1):
x = values[i - 1]
if i > 1 and x != oldx:
A.append(count)
R[N] = i
N += 1
count = 0
B[i] = N
count += 1
oldx = x
A.append(count)
R[N] = n + 1
pi, beta, alfa, tau, lam = process(N, A)
for i, j in queries:
x, y = B[i], B[j]
if x == y:
z = j - i + 1
else:
if x + 1 != y:
z = A[nca(x + 1, y - 1, beta, alfa, tau, lam, pi)]
else:
z = 0
z = max(z, max(R[x] - i, A[y] - R[y] + j + 1))
results.append(z)
return results
def main():
# Hard-coded test data
test_cases = [
{
"n": 10,
"values": [-1, -1, 1, 1, 1, 1, 3, 10, 10, 10],
"queries": [(2, 3), (1, 10), (5, 10)],
"expected": [1, 4, 3]
}
]
for idx, test in enumerate(test_cases):
n = test["n"]
values = test["values"]
queries = test["queries"]
expected = test["expected"]
print(f"Test Case {idx + 1}:")
print(f"Size: {n}, Queries: {len(queries)}")
print(f"Values: {' '.join(map(str, values))}")
results = solve_test_case(n, values, queries)
print("Queries and Results:")
for q_idx, ((i, j), result, exp) in enumerate(zip(queries, results, expected)):
print(f"Query: {i} {j}")
print(f"Result: {result} (Expected: {exp})")
if result != exp:
print(" WARNING: Result doesn't match expected output")
print()
if __name__ == "__main__":
main()
- Output:
Test Case 1: Size: 10, Queries: 3 Values: -1 -1 1 1 1 1 3 10 10 10 Queries and Results: Query: 2 3 Result: 1 (Expected: 1) Query: 1 10 Result: 4 (Expected: 4) Query: 5 10 Result: 3 (Expected: 3)
# Schieber-Vishkin Algorithm Implementation in R
# Based on rosettacode.org/wiki/Schieber-Vishkin_algorithm
# Node structure for a triply linked tree
create_node <- function() {
list(child = 0, sib = 0, parent = 0)
}
# Process the input array `a` of size `n` into a triply linked tree
# and return the vectors pi_, beta, alfa, tau, and lam
process <- function(n, a) {
pi_ <- integer(n + 1)
beta <- integer(n + 1)
alfa <- integer(n + 1)
tau <- integer(n + 1)
lam <- integer(n + 1)
# Create n+1 default Node objects
nodes <- vector("list", n + 1)
for (i in 1:(n + 1)) {
nodes[[i]] <- create_node()
}
# Make triply linked tree
t <- 0
for (v in n:1) {
u <- 0
while (a[v + 1] > a[t + 1] || (a[v + 1] == a[t + 1] && v > t)) {
u <- t
t <- nodes[[t + 1]]$parent
}
if (u != 0) {
nodes[[v + 1]]$sib <- nodes[[u + 1]]$sib
nodes[[u + 1]]$sib <- 0
nodes[[u + 1]]$parent <- v
nodes[[v + 1]]$child <- u
} else {
nodes[[v + 1]]$sib <- nodes[[t + 1]]$child
}
nodes[[t + 1]]$child <- v
nodes[[v + 1]]$parent <- t
t <- v
}
# Begin first traversal
p <- nodes[[1]]$child
n_count <- 0
lam[1] <- -1
# First traversal function
traversal <- function() {
while (TRUE) {
# s3: Compute beta in the easy case
n_count <<- n_count + 1
pi_[p + 1] <<- n_count
tau[n_count + 1] <<- 0
lam[n_count + 1] <<- 1 + lam[bitwShiftR(n_count, 1) + 1]
if (nodes[[p + 1]]$child != 0) {
p <<- nodes[[p + 1]]$child
next # Continue to next iteration
}
beta[p + 1] <<- n_count
break
}
# s4: Compute tau, bottom-up
while (TRUE) {
tau[beta[p + 1]] <<- nodes[[p + 1]]$parent
if (nodes[[p + 1]]$sib != 0) {
p <<- nodes[[p + 1]]$sib
return(TRUE)
}
p <<- nodes[[p + 1]]$parent
# Compute beta in the hard case
if (p != 0) {
h <- lam[bitwAnd(n_count, -pi_[p + 1]) + 1]
beta[p + 1] <<- bitwShiftL(bitwOr(bitwShiftR(n_count, h), 1), h)
} else {
return(FALSE) # Exit traversal
}
}
}
# Perform first traversal
while (traversal()) {}
# Begin second traversal
p <- nodes[[1]]$child
lam[1] <- lam[n_count + 1]
pi_[1] <- 0
beta[1] <- 0
alfa[1] <- 0
# Recursive function for second traversal
compute_alfa <- function(node) {
# s7: Compute alfa, top-down
alfa[node + 1] <<- bitwOr(alfa[nodes[[node + 1]]$parent + 1],
bitwAnd(beta[node + 1], -beta[node + 1]))
if (nodes[[node + 1]]$child != 0) {
compute_alfa(nodes[[node + 1]]$child)
}
# s8: Continue traversal
if (nodes[[node + 1]]$sib != 0) {
compute_alfa(nodes[[node + 1]]$sib)
}
}
# Perform second (recursive) traversal if needed
if (p != 0) {
compute_alfa(p)
}
return(list(pi_ = pi_, beta = beta, alfa = alfa, tau = tau, lam = lam))
}
# Compute the nearest common ancestor (NCA) of two nodes x and y
nca <- function(x, y, beta, alfa, tau, lam, pi_) {
# Find common height
if (beta[x + 1] <= beta[y + 1]) {
h <- lam[bitwAnd(beta[y + 1], -beta[x + 1] + 1) + 1]
} else {
h <- lam[bitwAnd(beta[x + 1], -beta[y + 1] + 1) + 1]
}
# Find true height
k <- bitwAnd(bitwAnd(alfa[x + 1], alfa[y + 1]),
bitwNot(bitwShiftL(1, h)) + 1)
h <- lam[bitwAnd(k, -k) + 1]
# Find beta[z]
j <- bitwShiftL(bitwOr(bitwShiftR(beta[x + 1], h), 1), h)
# Find x' and y'
if (j != beta[x + 1]) {
l <- lam[bitwAnd(alfa[x + 1], bitwShiftL(1, h) - 1) + 1]
x <- tau[bitwShiftL(bitwOr(bitwShiftR(beta[x + 1], l), 1), l) + 1]
}
if (j != beta[y + 1]) {
l <- lam[bitwAnd(alfa[y + 1], bitwShiftL(1, h) - 1) + 1]
y <- tau[bitwShiftL(bitwOr(bitwShiftR(beta[y + 1], l), 1), l) + 1]
}
# Find z
if (pi_[x + 1] <= pi_[y + 1]) {
return(x)
} else {
return(y)
}
}
# Solve a test case using Schieber-Vishkin given values and queries
schiebervishkin <- function(n, values, queries) {
results <- integer(length(queries))
a <- c(.Machine$integer.max)
r <- integer(n + 2)
b <- integer(n + 2)
big_n <- 1
count <- 0
oldx <- NULL
for (i in 1:n) {
x <- values[i]
if (i > 1 && x != oldx) {
a <- c(a, count)
r[big_n + 1] <- i
big_n <- big_n + 1
count <- 0
}
b[i] <- big_n
count <- count + 1
oldx <- x
}
a <- c(a, count)
r[big_n + 1] <- n + 1
result_process <- process(big_n, a)
pi_ <- result_process$pi_
beta <- result_process$beta
alfa <- result_process$alfa
tau <- result_process$tau
lam <- result_process$lam
for (t in 1:length(queries)) {
query <- queries[[t]]
i <- query[1]
j <- query[2]
x <- b[i]
y <- b[j]
z <- 0
if (x == y) {
z <- j - i + 1
} else {
if (x + 1 != y) {
z <- a[nca(x + 1, y - 1, beta, alfa, tau, lam, pi_) + 1]
}
z <- max(z, r[x + 1] - i, a[y + 1] - (r[y + 1] - j - 1))
}
results[t] <- z
}
return(results)
}
# Main function to run test cases
main <- function() {
# Hard-coded test data
test_cases <- list(
list(
n = 10,
values = c(-1L, -1L, 1L, 1L, 1L, 1L, 3L, 10L, 10L, 10L),
queries = list(c(2, 3), c(1, 10), c(5, 10)),
expected = c(1L, 4L, 3L)
)
)
for (idx in 1:length(test_cases)) {
test_case <- test_cases[[idx]]
n <- test_case$n
values <- test_case$values
queries <- test_case$queries
expected <- test_case$expected
cat("Test Case", idx, ":\n")
cat("Size:", n, ", Queries:", length(queries), "\n")
cat("Values:", paste(values, collapse = " "), "\n")
results <- schiebervishkin(n, values, queries)
cat("Queries and Results:\n")
for (q_idx in 1:length(queries)) {
query <- queries[[q_idx]]
i <- query[1]
j <- query[2]
result <- results[q_idx]
exp <- expected[q_idx]
cat("Query:", i, j, "\n")
cat("Result:", result, "(Expected:", exp, ")\n")
if (result != exp) {
cat(" WARNING: Result doesn't match expected output\n")
}
}
cat("\n")
}
}
# Run the main function
main()
- Output:
Test Case 1 : Size: 10 , Queries: 3 Values: -1 -1 1 1 1 1 3 10 10 10 Queries and Results: Query: 2 3 Result: 1 (Expected: 1 ) Query: 1 10 Result: 4 (Expected: 4 ) Query: 5 10 Result: 3 (Expected: 3 )
# 20250716 Raku programming solution
# Node class for triply linked tree
class Node { has Int ($.child, $.sib, $.parent) is rw is default(0) }
# Result class to hold algorithm outputs
class Result { has Int (@.pi, @.beta, @.alfa, @.tau, @.lam) }
# Main processing function implementing Schieber-Vishkin algorithm
sub process(Int $n, @a) returns Result {
my Int (@pi, @beta, @alfa, @tau, @lam);
my Node @nodes = Node.new xx ($n + 1);
# Make triply linked tree
my Int $t = 0;
for $n...1 -> $v {
my Int $u = 0;
while @a[$v] > @a[$t] || (@a[$v] == @a[$t] && $v > $t) {
$t = @nodes[ $u = $t ].parent;
}
if $u != 0 {
(@nodes[$v].sib,@nodes[$u].sib,@nodes[$u].parent,@nodes[$v].child) =
@nodes[$u].sib, 0, $v, $u;
} else {
@nodes[$v].sib = @nodes[$t].child;
}
@nodes[@nodes[$t].child = $v].parent = $t;
$t = $v;
}
# First traversal
my Int ($p, $n-count) = @nodes[0].child, 0;
@lam[0] = -1;
# Inner traversal function
sub traversal() returns Bool {
loop {
@pi[$p] = ++$n-count;
@tau[$n-count] = 0;
@lam[$n-count] = 1 + @lam[$n-count +> 1];
if @nodes[$p].child != 0 { $p = @nodes[$p].child and next }
@beta[$p] = $n-count;
last;
}
loop {
@tau[@beta[$p]] = @nodes[$p].parent;
if @nodes[$p].sib != 0 {
$p = @nodes[$p].sib;
return True;
}
$p = @nodes[$p].parent;
if $p != 0 {
my Int $h = @lam[$n-count +& (-@pi[$p])];
@beta[$p] = (($n-count +> $h) +| 1) +< $h;
} else {
return False;
}
}
}
while traversal() { } # Perform first traversal
# Second traversal
( $p, @lam[0], @pi[0], @beta[0], @alfa[0] ) =
@nodes[0].child, @lam[$n-count], 0, 0, 0 ;
# Recursive function for computing alfa
sub compute-alfa(Int $node) {
@alfa[$node] = @alfa[@nodes[$node].parent] +| (@beta[$node] +& (-@beta[$node]));
if @nodes[$node].child != 0 { compute-alfa(@nodes[$node].child) }
if @nodes[$node].sib != 0 { compute-alfa(@nodes[$node].sib) }
}
compute-alfa($p) if $p != 0; # Perform second traversal if needed
return Result.new(:pi(@pi),:beta(@beta),:alfa(@alfa),:tau(@tau),:lam(@lam));
}
# Compute nearest common ancestor
sub nca(Int $x is copy, Int $y is copy, @beta, @alfa, @tau, @lam, @pi) returns Int {
my Int $h = @beta[$x] <= @beta[$y] ?? @lam[@beta[$y] +& (-@beta[$x])]
!! @lam[@beta[$x] +& (-@beta[$y])];
my Int $k = @alfa[$x] +& @alfa[$y] +& (-(1 +< $h));
$h = @lam[$k +& (-$k)];
my Int $j = ((@beta[$x] +> $h) +| 1) +< $h;
if $j != @beta[$x] {
my Int $l = @lam[@alfa[$x] +& ((1 +< $h) - 1)];
$x = @tau[((@beta[$x] +> $l) +| 1) +< $l];
}
if $j != @beta[$y] {
my Int $l = @lam[@alfa[$y] +& ((1 +< $h) - 1)];
$y = @tau[((@beta[$y] +> $l) +| 1) +< $l];
}
return @pi[$x] <= @pi[$y] ?? $x !! $y;
}
# Generic solver function
sub solve-test-case-generic(Int $n, @values, @queries, &executor) {
my Int @a = uint.Range.max; # 2**31 - 1
my Int @r = 0 xx ($n + 2);
my Int @b = 0 xx ($n + 2);
my Int $big-n = 1;
my Int $count = 0;
my $oldx;
for 1..$n -> $i {
my Int $x = @values[$i - 1];
if $i > 1 && (!$oldx.defined || $x != $oldx) {
@a.push($count);
@r[$big-n] = $i;
$big-n++;
$count = 0;
}
@b[$i] = $big-n;
$count++;
$oldx = $x;
}
@a.push($count);
@r[$big-n] = $n + 1;
given my Result $result = process($big-n, @a) {
return executor(@queries, @a, @r, @b, .pi, .beta, .alfa, .tau, .lam)
}
}
# Serial executor
sub run-serial( @queries, @a, @r, @b, @pi, @beta, @alfa, @tau, @lam) {
return @queries.map: -> @query {
my ($i, $j) = @query[0], @query[1]; # keep 1-based
my ($x, $y) = @b[$i], @b[$j];
do if $x == $y { # same block: contiguous run
$j - $i + 1;
} else {
# 1) base = either nca-block or 0 if adjacent segments
my Int $base = ($x + 1 != $y)
?? @a[ nca($x+1, $y-1, @beta, @alfa, @tau, @lam, @pi) ]
!! 0;
# 2) include partial runs at both ends
my Int $left = @r[$x] - $i;
my Int $right = @a[$y] - @r[$y] + $j + 1;
max($base, $left, $right);
}
}
}
# Race executor ( mediocre implementation )
sub run-race(@queries, @a, @r, @b, @pi, @beta, @alfa, @tau, @lam) {
return @queries.batch(1000).race.map({
|(.map: -> @query {
my ($i, $j) = @query[0], @query[1];
my ($x, $y) = @b[$i], @b[$j];
do if $x == $y {
$j - $i + 1;
} else {
my $z = $x+1 != $y ?? @a[nca($x+1,$y-1,@beta,@alfa,@tau,@lam,@pi)]
!! 0;
max($z, @r[$x] - $i, @a[$y] - @r[$y] + $j + 1);
}
})
});
}
# Async executor ( mediocre implementation )
sub run-async(@queries, @a, @r, @b, @pi, @beta, @alfa, @tau, @lam) {
my @promises = @queries.batch(1000).map: -> @chunk {
start {
@chunk.map: -> @query {
my ($i, $j) = @query[0], @query[1];
my ($x, $y) = @b[$i], @b[$j];
do if $x == $y {
$j - $i + 1;
} else {
my $z = $x + 1 != $y
?? @a[nca($x + 1, $y - 1, @beta, @alfa, @tau, @lam, @pi)]
!! 0;
max($z, @r[$x] - $i, @a[$y] - @r[$y] + $j + 1);
}
}
}
}
return await(@promises).flat;
}
sub print-query-results(@queries, @results, @expected, Str $mode) {
say "Queries and Results ($mode):";
for @queries.kv -> $q-idx, @query {
my ($i, $j) = @query[0], @query[1];
my $result = @results[$q-idx];
my $expected = @expected[$q-idx];
say "Query: $i $j";
say "Result: $result (Expected: $expected)";
if $result != $expected {
say " WARNING: Result doesn't match expected output";
}
}
say "";
}
my @test-cases = ({
n => 10,
values => [-1, -1, 1, 1, 1, 1, 3, 10, 10, 10],
queries => [[2, 3], [1, 10], [5, 10]],
expected => [1, 4, 3]
},);
say "Output similar to the Go entry:\n";
for @test-cases.kv -> $idx, %test-case {
say "Test Case {$idx + 1}:";
my @results = solve-test-case-generic( %test-case<n>,
%test-case<values>,
%test-case<queries>,
&run-serial );
say "Result: {@results} (Expected: %test-case<expected>)";
}
say "\nOutput similar to the Julia entry:\n";
my @executors = [
['Sequential', &run-serial],
['Race', &run-race],
['Async', &run-async],
];
for @test-cases.kv -> $idx, %test-case {
say "Test Case {$idx + 1}:";
say "Size: {%test-case<n>}, Queries: {%test-case<queries>.elems}";
say "Values: {%test-case<values>.join(' ')}\n";
for @executors -> $executor {
my ($label, $code) = $executor;
my @results = solve-test-case-generic( %test-case<n>,
%test-case<values>,
%test-case<queries>,
$code );
print-query-results( %test-case<queries>, @results,
%test-case<expected>, $label);
}
}
#`[[[[[[ nothing worthy of attention for now
# Demonstration of different approaches
my Int $n = 8000;
my @values = ^$n .map: { rand < 0.1 ?? -1 !! (1 + floor(rand * 1000)) };
my Int $query-count = 200;
my @queries = (^$query-count).map: { minmax (1..$n).pick, (1..$n).pick };
# Just test performance, don't compare expected outputs
say "Benchmarking on N=$n, Queries=$query-count\n";
for (
[ 'Method 0: Plain serial processing', &run-serial ],
[ 'Method 1: Using .race (data parallelism)', &run-race ],
[ 'Method 2: Using start blocks (async processing)', &run-async ],
) -> ($label, $executor) {
say $label;
my $start-time = now;
my @results = solve-test-case-generic($n, @values, @queries, $executor);
my $elapsed = now - $start-time;
say "Completed in {$elapsed.round(0.001)} seconds\n";
}
#]]]]]]
You may Attempt This Online!
use std::cmp;
#[derive(Clone, Default)]
struct Node {
child: usize,
sib: usize,
parent: usize,
}
fn process(n: usize, a: &mut Vec<i32>) -> (Vec<usize>, Vec<usize>, Vec<usize>, Vec<usize>, Vec<i32>) {
let mut pi = vec![0; n + 1];
let mut beta = vec![0; n + 1];
let mut alfa = vec![0; n + 1];
let mut tau = vec![0; n + 1];
let mut lam = vec![0; n + 1];
lam[0] = -1; // Change this to i32 instead of usize
let mut nodes = vec![Node::default(); n + 1];
// Make triply linked tree
let mut t = 0;
for v in (1..=n).rev() {
let mut u = 0;
while a[v] > a[t] || (a[v] == a[t] && v > t) {
u = t;
t = nodes[t].parent;
}
if u != 0 {
nodes[v].sib = nodes[u].sib;
nodes[u].sib = 0;
nodes[u].parent = v;
nodes[v].child = u;
} else {
nodes[v].sib = nodes[t].child;
}
nodes[t].child = v;
nodes[v].parent = t;
t = v;
}
// Begin first traversal
let mut p = nodes[0].child;
let mut n_count = 0;
// First traversal loop (replaces goto-based control flow)
loop {
// s3: Compute beta in the easy case
n_count += 1;
pi[p] = n_count;
tau[n_count] = 0;
lam[n_count] = 1 + lam[n_count >> 1];
if nodes[p].child != 0 {
p = nodes[p].child;
continue;
}
beta[p] = n_count;
// s4: Compute tau, bottom-up
loop {
tau[beta[p]] = nodes[p].parent;
if nodes[p].sib != 0 {
p = nodes[p].sib;
break; // Go back to s3
}
p = nodes[p].parent;
// Compute beta in the hard case
if p != 0 {
let h = lam[(n_count & (!pi[p] + 1)) as usize];
beta[p] = ((n_count >> h as usize) | 1) << h as usize;
} else {
// Exit traversal
break;
}
}
if p == 0 {
break;
}
}
// Begin second traversal
p = nodes[0].child;
lam[0] = lam[n_count];
pi[0] = 0;
beta[0] = 0;
alfa[0] = 0;
// Recursive function for second traversal
fn compute_alfa(
p: usize,
nodes: &[Node],
alfa: &mut [usize],
beta: &[usize],
) {
// s7: Compute alfa, top-down
alfa[p] = alfa[nodes[p].parent] | (beta[p] & (!beta[p] + 1));
if nodes[p].child != 0 {
compute_alfa(nodes[p].child, nodes, alfa, beta);
}
// s8: Continue traversal
if nodes[p].sib != 0 {
compute_alfa(nodes[p].sib, nodes, alfa, beta);
}
}
// Perform second traversal
if p != 0 {
compute_alfa(p, &nodes, &mut alfa, &beta);
}
(pi, beta, alfa, tau, lam)
}
fn nca(
mut x: usize,
mut y: usize,
beta: &[usize],
alfa: &[usize],
tau: &[usize],
lam: &[i32], // Changed to i32
pi: &[usize],
) -> usize {
// Find common height
let h = if beta[x] <= beta[y] {
lam[(beta[y] & (!beta[x] + 1)) as usize]
} else {
lam[(beta[x] & (!beta[y] + 1)) as usize]
};
// Find true height
let k = alfa[x] & alfa[y] & (!(1 << h as usize) + 1);
let h = lam[(k & (!k + 1)) as usize];
// Find beta[z]
let j = ((beta[x] >> h as usize) | 1) << h as usize;
// Find x' and y'
if j != beta[x] {
let l = lam[(alfa[x] & ((1 << h as usize) - 1)) as usize];
x = tau[((beta[x] >> l as usize) | 1) << l as usize];
}
if j != beta[y] {
let l = lam[(alfa[y] & ((1 << h as usize) - 1)) as usize];
y = tau[((beta[y] >> l as usize) | 1) << l as usize];
}
// Find z
if pi[x] <= pi[y] { x } else { y }
}
fn solve_test_case(
n: usize,
values: &[i32],
queries: &[(usize, usize)],
) -> Vec<i32> {
let mut results = Vec::new();
let mut a = vec![i32::MAX]; // A[0]
let mut r = vec![0; n + 2];
let mut b = vec![0; n + 2];
let mut big_n = 1;
let mut count = 0;
let mut oldx = None;
for i in 1..=n {
let x = values[i - 1];
if i > 1 && Some(x) != oldx {
a.push(count);
r[big_n] = i;
big_n += 1;
count = 0;
}
b[i] = big_n;
count += 1;
oldx = Some(x);
}
a.push(count);
r[big_n] = n + 1;
let (pi, beta, alfa, tau, lam) = process(big_n, &mut a);
for &(i, j) in queries {
let x = b[i];
let y = b[j];
let z = if x == y {
(j - i + 1) as i32
} else {
let mut z = if x + 1 != y {
a[nca(x + 1, y - 1, &beta, &alfa, &tau, &lam, &pi)]
} else {
0
};
z = cmp::max(z, cmp::max(
(r[x] - i) as i32,
a[y] - (r[y] - j - 1) as i32
));
z
};
results.push(z);
}
results
}
fn main() {
// Hard-coded test data
let test_cases = [
(
10,
vec![-1, -1, 1, 1, 1, 1, 3, 10, 10, 10],
vec![(2, 3), (1, 10), (5, 10)],
vec![1, 4, 3]
)
];
for (idx, (n, values, queries, expected)) in test_cases.iter().enumerate() {
println!("Test Case {}:", idx + 1);
println!("Size: {}, Queries: {}", n, queries.len());
print!("Values: ");
for v in values {
print!("{} ", v);
}
println!();
let results = solve_test_case(*n, values, queries);
println!("Queries and Results:");
// Fixed iterator pattern
for q_idx in 0..queries.len() {
let (i, j) = queries[q_idx];
let result = results[q_idx];
let exp = expected[q_idx];
println!("Query: {} {}", i, j);
println!("Result: {} (Expected: {})", result, exp);
if result != exp {
println!(" WARNING: Result doesn't match expected output");
}
}
println!();
}
}
- Output:
Test Case 1: Size: 10, Queries: 3 Values: -1 -1 1 1 1 1 3 10 10 10 Queries and Results: Query: 2 3 Result: 1 (Expected: 1) Query: 1 10 Result: 4 (Expected: 4) Query: 5 10 Result: 3 (Expected: 3)
import scala.collection.mutable.ArrayBuffer
import scala.util.control.Breaks._
object Main {
case class Node(var child: Int = 0, var sib: Int = 0, var parent: Int = 0)
case class Result(pi: Array[Int], beta: Array[Int], alfa: Array[Int], tau: Array[Int], lam: Array[Int])
case class TestCase(n: Int, values: Array[Int], queries: Array[Array[Int]], expected: Array[Int])
case class TraversalState(var p: Int, var n: Int)
def process(N: Int, A: Array[Int]): Result = {
val pi = Array.ofDim[Int](N + 1)
val beta = Array.ofDim[Int](N + 1)
val alfa = Array.ofDim[Int](N + 1)
val tau = Array.ofDim[Int](N + 1)
val lam = Array.ofDim[Int](N + 1)
val nodes = Array.fill(N + 1)(Node())
// Make triply linked tree
var t = 0
for (v <- N to 1 by -1) {
var u = 0
while (A(v) > A(t) || (A(v) == A(t) && v > t)) {
u = t
t = nodes(t).parent
}
if (u != 0) {
nodes(v).sib = nodes(u).sib
nodes(u).sib = 0
nodes(u).parent = v
nodes(v).child = u
} else {
nodes(v).sib = nodes(t).child
}
nodes(t).child = v
nodes(v).parent = t
t = v
}
// Begin first traversal
var p = nodes(0).child
var n = 0
lam(0) = -1
// Using a mutable object to simulate pass-by-reference behavior
val state = TraversalState(p, n)
while (traversal(nodes, state, pi, beta, tau, lam)) {
// Continue traversal
n = state.n
p = state.p
}
// Begin second traversal
p = nodes(0).child
lam(0) = lam(n)
pi(0) = 0
beta(0) = 0
alfa(0) = 0
// Perform second traversal
if (p != 0) {
compute_alfa(nodes, p, alfa, beta)
}
Result(pi, beta, alfa, tau, lam)
}
def traversal(nodes: Array[Node], state: TraversalState, pi: Array[Int], beta: Array[Int], tau: Array[Int], lam: Array[Int]): Boolean = {
// s3: Compute beta in the easy case
breakable({
while (true) {
state.n += 1
pi(state.p) = state.n
tau(state.n) = 0
lam(state.n) = 1 + lam(state.n >> 1)
breakable({
if (nodes(state.p).child != 0) {
state.p = nodes(state.p).child
return true
}
});
beta(state.p) = state.n
break; //break
}
});
// s4: Compute tau, bottom-up
while (true) {
tau(beta(state.p)) = nodes(state.p).parent
if (nodes(state.p).sib != 0) {
state.p = nodes(state.p).sib
return true // Go back to s3
}
state.p = nodes(state.p).parent
// Compute beta in the hard case
if (state.p != 0) {
val h = lam(state.n & -pi(state.p))
beta(state.p) = ((state.n >> h) | 1) << h
} else {
return false // Exit traversal
}
}
false // Should never reach here due to returns above
}
def compute_alfa(nodes: Array[Node], node: Int, alfa: Array[Int], beta: Array[Int]): Unit = {
// s7: Compute alfa, top-down
alfa(node) = alfa(nodes(node).parent) | (beta(node) & -beta(node))
if (nodes(node).child != 0) {
compute_alfa(nodes, nodes(node).child, alfa, beta)
}
// s8: Continue traversal
if (nodes(node).sib != 0) {
compute_alfa(nodes, nodes(node).sib, alfa, beta)
}
}
def nca(x: Int, y: Int, beta: Array[Int], alfa: Array[Int], tau: Array[Int], lam: Array[Int], pi: Array[Int]): Int = {
// Find common height
val h = if (beta(x) <= beta(y)) {
lam(beta(y) & -beta(x))
} else {
lam(beta(x) & -beta(y))
}
// Find true height
val k = alfa(x) & alfa(y) & -(1 << h)
val trueHeight = lam(k & -k)
// Find beta(z)
val j = ((beta(x) >> trueHeight) | 1) << trueHeight
// Find x' and y'
var newX = x
var newY = y
if (j != beta(x)) {
val l = lam(alfa(x) & ((1 << trueHeight) - 1))
newX = tau(((beta(x) >> l) | 1) << l)
}
if (j != beta(y)) {
val l = lam(alfa(y) & ((1 << trueHeight) - 1))
newY = tau(((beta(y) >> l) | 1) << l)
}
// Find z
if (pi(newX) <= pi(newY)) newX else newY
}
def solve_test_case(n: Int, values: Array[Int], queries: Array[Array[Int]]): ArrayBuffer[Int] = {
val results = ArrayBuffer[Int]()
val A = Array.ofDim[Int](n + 2)
A(0) = Int.MaxValue // A(0)
val R = Array.ofDim[Int](n + 2)
val B = Array.ofDim[Int](n + 2)
var N = 1
var count = 0
var oldx: Option[Int] = None
for (i <- 1 to n) {
val x = values(i - 1)
if (i > 1 && (oldx.isEmpty || x != oldx.get)) {
A(N) = count
R(N) = i
N += 1
count = 0
}
B(i) = N
count += 1
oldx = Some(x)
}
A(N) = count
R(N) = n + 1
val result = process(N, A)
val pi = result.pi
val beta = result.beta
val alfa = result.alfa
val tau = result.tau
val lam = result.lam
for (query <- queries) {
val i = query(0)
val j = query(1)
val x = B(i)
val y = B(j)
val z = if (x == y) {
j - i + 1
} else {
val commonLength = if (x + 1 != y) {
A(nca(x + 1, y - 1, beta, alfa, tau, lam, pi))
} else {
0
}
math.max(commonLength, math.max(R(x) - i, A(y) - R(y) + j + 1))
}
results += z
}
results
}
def main(args: Array[String]): Unit = {
// Hard-coded test data
val testCases = List(
TestCase(
10,
Array(-1, -1, 1, 1, 1, 1, 3, 10, 10, 10),
Array(Array(2, 3), Array(1, 10), Array(5, 10)),
Array(1, 4, 3)
)
)
for ((test, idx) <- testCases.zipWithIndex) {
val n = test.n
val values = test.values
val queries = test.queries
val expected = test.expected
println(s"Test Case ${idx + 1}:")
println(s"Size: $n, Queries: ${queries.length}")
print("Values: ")
println(values.mkString(" "))
val results = solve_test_case(n, values, queries)
println("Queries and Results:")
for (q_idx <- queries.indices) {
val query = queries(q_idx)
val result = results(q_idx)
val exp = expected(q_idx)
println(s"Query: ${query(0)} ${query(1)}")
println(s"Result: $result (Expected: $exp)")
if (result != exp) {
println(" WARNING: Result doesn't match expected output")
}
}
println()
}
}
}
- Output:
Test Case 1: Size: 10, Queries: 3 Values: -1 -1 1 1 1 1 3 10 10 10 Queries and Results: Query: 2 3 Result: 1 (Expected: 1) Query: 1 10 Result: 4 (Expected: 4) Query: 5 10 Result: 3 (Expected: 3)
import Foundation
class Node {
var child: Int = 0
var sib: Int = 0
var parent: Int = 0
}
struct Result {
var pi: [Int]
var beta: [Int]
var alfa: [Int]
var tau: [Int]
var lam: [Int]
}
// These variables are used to simulate the nonlocal variables
private var p: Int = 0
private var n: Int = 0
func getP() -> Int {
return p
}
func getN() -> Int {
return n
}
func process(N: Int, A: [Int]) -> Result {
var pi = Array(repeating: 0, count: N + 1)
var beta = Array(repeating: 0, count: N + 1)
var alfa = Array(repeating: 0, count: N + 1)
var tau = Array(repeating: 0, count: N + 1)
var lam = Array(repeating: 0, count: N + 1)
let nodes = Array(repeating: Node(), count: N + 1)
// Make triply linked tree
var t = 0
for v in stride(from: N, to: 0, by: -1) {
var u = 0
while A[v] > A[t] || (A[v] == A[t] && v > t) {
u = t
t = nodes[t].parent
}
if u != 0 {
nodes[v].sib = nodes[u].sib
nodes[u].sib = 0
nodes[u].parent = v
nodes[v].child = u
} else {
nodes[v].sib = nodes[t].child
}
nodes[t].child = v
nodes[v].parent = t
t = v
}
// Begin first traversal
var p = nodes[0].child
var n = 0
lam[0] = -1
while traversal(nodes: nodes, initialP: p, initialN: n, pi: &pi, beta: &beta, tau: &tau, lam: &lam) {
// Continue traversal
n = getN()
p = getP()
}
// Begin second traversal
p = nodes[0].child
lam[0] = lam[n]
pi[0] = 0
beta[0] = 0
alfa[0] = 0
// Perform second traversal
if p != 0 {
compute_alfa(nodes: nodes, node: p, alfa: &alfa, beta: beta)
}
return Result(pi: pi, beta: beta, alfa: alfa, tau: tau, lam: lam)
}
func traversal(nodes: [Node], initialP: Int, initialN: Int, pi: inout [Int], beta: inout [Int], tau: inout [Int], lam: inout [Int]) -> Bool {
p = initialP
n = initialN
// s3: Compute beta in the easy case
while true {
n += 1
pi[p] = n
tau[n] = 0
lam[n] = 1 + lam[n >> 1]
if nodes[p].child != 0 {
p = nodes[p].child
continue
}
beta[p] = n
break
}
// s4: Compute tau, bottom-up
while true {
tau[beta[p]] = nodes[p].parent
if nodes[p].sib != 0 {
p = nodes[p].sib
return true // Go back to s3
}
p = nodes[p].parent
// Compute beta in the hard case
if p != 0 {
let h = lam[n & -pi[p]]
beta[p] = ((n >> h) | 1) << h
} else {
return false // Exit traversal
}
}
}
func compute_alfa(nodes: [Node], node: Int, alfa: inout [Int], beta: [Int]) {
// s7: Compute alfa, top-down
alfa[node] = alfa[nodes[node].parent] | (beta[node] & -beta[node])
if nodes[node].child != 0 {
compute_alfa(nodes: nodes, node: nodes[node].child, alfa: &alfa, beta: beta)
}
// s8: Continue traversal
if nodes[node].sib != 0 {
compute_alfa(nodes: nodes, node: nodes[node].sib, alfa: &alfa, beta: beta)
}
}
func nca(x: Int, y: Int, beta: [Int], alfa: [Int], tau: [Int], lam: [Int], pi: [Int]) -> Int {
// Find common height
var h: Int
if beta[x] <= beta[y] {
h = lam[beta[y] & -beta[x]]
} else {
h = lam[beta[x] & -beta[y]]
}
// Find true height
let k = alfa[x] & alfa[y] & -(1 << h)
h = lam[k & -k]
// Find beta[z]
let j = ((beta[x] >> h) | 1) << h
// Find x' and y'
var x = x
var y = y
if j != beta[x] {
let l = lam[alfa[x] & ((1 << h) - 1)]
x = tau[((beta[x] >> l) | 1) << l]
}
if j != beta[y] {
let l = lam[alfa[y] & ((1 << h) - 1)]
y = tau[((beta[y] >> l) | 1) << l]
}
// Find z
let z = (pi[x] <= pi[y]) ? x : y
return z
}
func solve_test_case(n: Int, values: [Int], queries: [[Int]]) -> [Int] {
var results: [Int] = []
var A = Array(repeating: 0, count: n + 2)
A[0] = Int.max // A[0]
var R = Array(repeating: 0, count: n + 2)
var B = Array(repeating: 0, count: n + 2)
var N = 1
var count = 0
var oldx: Int? = nil
for i in 1...n {
let x = values[i - 1]
if i > 1 && (oldx == nil || x != oldx!) {
A[N] = count
R[N] = i
N += 1
count = 0
}
B[i] = N
count += 1
oldx = x
}
A[N] = count
R[N] = n + 1
let result = process(N: N, A: A)
let pi = result.pi
let beta = result.beta
let alfa = result.alfa
let tau = result.tau
let lam = result.lam
for query in queries {
let i = query[0]
let j = query[1]
let x = B[i]
let y = B[j]
var z: Int
if x == y {
z = j - i + 1
} else {
if x + 1 != y {
z = A[nca(x: x + 1, y: y - 1, beta: beta, alfa: alfa, tau: tau, lam: lam, pi: pi)]
} else {
z = 0
}
z = max(z, max(R[x] - i, A[y] - R[y] + j + 1))
}
results.append(z)
}
return results
}
struct TestCase {
let n: Int
let values: [Int]
let queries: [[Int]]
let expected: [Int]
init(n: Int, values: [Int], queries: [[Int]], expected: [Int]) {
self.n = n
self.values = values
self.queries = queries
self.expected = expected
}
}
// Main program
func main() {
// Hard-coded test data
let testCases: [TestCase] = [
TestCase(
n: 10,
values: [-1, -1, 1, 1, 1, 1, 3, 10, 10, 10],
queries: [[2, 3], [1, 10], [5, 10]],
expected: [1, 4, 3]
)
]
for (idx, test) in testCases.enumerated() {
let n = test.n
let values = test.values
let queries = test.queries
let expected = test.expected
print("Test Case \(idx + 1):")
print("Size: \(n), Queries: \(queries.count)")
print("Values: \(values.map { String($0) }.joined(separator: " "))")
let results = solve_test_case(n: n, values: values, queries: queries)
print("Queries and Results:")
for q_idx in 0..<queries.count {
let query = queries[q_idx]
let result = results[q_idx]
let exp = expected[q_idx]
print("Query: \(query[0]) \(query[1])")
print("Result: \(result) (Expected: \(exp))")
if result != exp {
print(" WARNING: Result doesn't match expected output")
}
}
print()
}
}
main()
- Output:
Test Case 1: Size: 10, Queries: 3 Values: -1 -1 1 1 1 1 3 10 10 10 <It takes too long to complete the calculation>
import "./dynamic" for Struct
import "./math" for Math
var Node = Struct.create("Node", ["child", "sib", "parent"])
var Result = Struct.create("Result", ["pi", "beta", "alfa", "tau", "lam"])
var process = Fn.new { |N, A|
var pi = List.filled(N + 1, 0)
var beta = List.filled(N + 1, 0)
var alfa = List.filled(N + 1, 0)
var tau = List.filled(N + 1, 0)
var lam = List.filled(N + 1, 0)
var nodes = List.filled(N + 1, null)
for (i in 0..N) nodes[i] = Node.new(0, 0, 0)
// Make triply linked tree.
var t = 0
for (v in N..1) {
var u = 0
while (A[v] > A[t] || (A[v] == A[t] && v > t)) {
u = t
t = nodes[t].parent
}
if (u != 0) {
nodes[v].sib = nodes[u].sib
nodes[u].sib = 0
nodes[u].parent = v
nodes[v].child = u
} else {
nodes[v].sib = nodes[t].child
}
nodes[t].child = v
nodes[v].parent = t
t = v
}
// Begin first traversal.
var p = nodes[0].child
var n = 0
lam[0] = -1
var traversal = Fn.new {
// s3: Compute beta in the easy case.
while (true) {
n = n + 1
pi[p] = n
tau[n] = 0
lam[n] = 1 + lam[n >> 1]
if (nodes[p].child != 0) {
p = nodes[p].child
continue
}
beta[p] = n
break
}
// s4: Compute tau, bottom-up.
while (true) {
tau[beta[p]] = nodes[p].parent
if (nodes[p].sib != 0) {
p = nodes[p].sib
return true // go back to s3
}
p = nodes[p].parent
// Compute beta in the hard case.
if (p != 0) {
var h = lam[n & ~(pi[p] - 1)]
beta[p] = ((n >> h) | 1) << h
} else {
return false // exit traversal
}
}
}
// Perform first traversal.
while (traversal.call()) {}
// Begin second traversal.
p = nodes[0].child
lam[0] = lam[n]
pi[0] = beta[0] = alfa[0] = 0
var computeAlfa // recursive
computeAlfa = Fn.new { |node|
// s7: Compute alfa, top-down.
alfa[node] = alfa[nodes[node].parent] | (beta[node] & ~(beta[node] - 1))
if (nodes[node].child != 0) computeAlfa.call(nodes[node].child)
// s8: Continue traversal.
if (nodes[node].sib != 0) computeAlfa.call(nodes[node].sib)
}
// Perform second traversal.
if (p != 0) computeAlfa.call(p)
return Result.new(pi, beta, alfa, tau, lam)
}
var nca = Fn.new { |x, y, beta, alfa, tau, lam, pi|
// Find common height.
var h
if (beta[x] <= beta[y]) {
h = lam[beta[y] & ~(beta[x] - 1)]
} else {
h = lam[beta[x] & ~(beta[y] - 1)]
}
// Find true height.
var k = alfa[x] & alfa[y] & ~((1 << h) - 1)
h = lam[k & ~(k - 1)]
// Find beta[z].
var j = ((beta[x] >> h) | 1) << h
// Find x' and y'.
var l
if (j != beta[x]) {
l = lam[alfa[x] & ((1 << h) - 1)]
x = tau[((beta[x] >> l) | 1) << l]
}
if (j != beta[y]) {
l = lam[alfa[y] & ((1 << h) - 1)]
y = tau[((beta[y] >> l) | 1) << l]
}
// Find z.
var z = pi[x] <= pi[y] ? x : y
return z
}
var solveTestCase = Fn.new { |n, values, queries|
var results = []
var A = [Num.maxSafeInteger]
var R = List.filled(n + 2, 0)
var B = List.filled(n + 2, 0)
var N = 1
var count = 0
var oldx = null
for (i in 1..n) {
var x = values[i - 1]
if (i > 1 && x != oldx) {
A.add(count)
R[N] = i
N = N + 1
count = 0
}
B[i] = N
count = count + 1
oldx = x
}
A.add(count)
R[N] = n + 1
var r = process.call(N, A)
for (t in queries) {
var i = t[0]
var j = t[1]
var x = B[i]
var y = B[j]
var z
if (x == y) {
z = j - i + 1
} else {
if (x + 1 != y) {
z = A[nca.call(x + 1, y - 1, r.beta, r.alfa, r.tau, r.lam, r.pi)]
} else {
z = 0
}
z = Math.max(z, Math.max(R[x] - i, A[y] - R[y] + j + 1))
}
results.add(z)
}
return results
}
// Hard-coded test data.
var testCases = [
{
"n": 10,
"values": [-1, -1, 1, 1, 1, 1, 3, 10, 10, 10],
"queries": [[2, 3], [1, 10], [5, 10]],
"expected": [1, 4, 3]
}
]
var idx = 0
for (test in testCases) {
var n = test["n"]
var values = test["values"]
var queries = test["queries"]
var expected = test["expected"]
System.print("Test Case %(idx + 1):")
System.print("Size: %(n), Queries: %(queries.count)")
System.print("Values: %(values.join(" "))")
var results = solveTestCase.call(n, values, queries)
System.print("Queries and Results:")
for (qIdx in 0...queries.count) {
var q = queries[qIdx]
var i = q[0]
var j = q[1]
var result = results[qIdx]
var exp = expected[qIdx]
System.print("Query: %(i) %(j)")
System.print("Result: %(result) (Expected: %(exp))")
if (result != exp) {
System.print(" WARNING: Result doesn't match expected output")
}
}
idx = idx + 1
System.print()
}
- Output:
Test Case 1: Size: 10, Queries: 3 Values: -1 -1 1 1 1 1 3 10 10 10 Queries and Results: Query: 2 3 Result: 1 (Expected: 1) Query: 1 10 Result: 4 (Expected: 4) Query: 5 10 Result: 3 (Expected: 3)
const std = @import("std");
const print = std.debug.print;
const ArrayList = std.ArrayList;
const Allocator = std.mem.Allocator;
const Node = struct {
child: usize = 0,
sib: usize = 0,
parent: usize = 0,
};
const ProcessResult = struct {
pi: []usize,
beta: []usize,
alfa: []usize,
tau: []usize,
lam: []i32,
};
fn process(allocator: Allocator, n: usize, a: []i32) !ProcessResult {
var pi = try allocator.alloc(usize, n + 1);
var beta = try allocator.alloc(usize, n + 1);
var alfa = try allocator.alloc(usize, n + 1);
var tau = try allocator.alloc(usize, n + 1);
var lam = try allocator.alloc(i32, n + 1);
@memset(pi, 0);
@memset(beta, 0);
@memset(alfa, 0);
@memset(tau, 0);
@memset(lam, 0);
lam[0] = -1;
var nodes = try allocator.alloc(Node, n + 1);
for (nodes) |*node| {
node.* = Node{};
}
// Make triply linked tree
var t: usize = 0;
var v: usize = n;
while (v >= 1) : (v -= 1) {
var u: usize = 0;
while (a[v] > a[t] or (a[v] == a[t] and v > t)) {
u = t;
t = nodes[t].parent;
}
if (u != 0) {
nodes[v].sib = nodes[u].sib;
nodes[u].sib = 0;
nodes[u].parent = v;
nodes[v].child = u;
} else {
nodes[v].sib = nodes[t].child;
}
nodes[t].child = v;
nodes[v].parent = t;
t = v;
}
// Begin first traversal
var p = nodes[0].child;
var n_count: usize = 0;
// First traversal loop
while (true) {
// s3: Compute beta in the easy case
n_count += 1;
pi[p] = n_count;
tau[n_count] = 0;
lam[n_count] = 1 + lam[n_count >> 1];
if (nodes[p].child != 0) {
p = nodes[p].child;
continue;
}
beta[p] = n_count;
// s4: Compute tau, bottom-up
while (true) {
tau[beta[p]] = nodes[p].parent;
if (nodes[p].sib != 0) {
p = nodes[p].sib;
break; // Go back to s3
}
p = nodes[p].parent;
// Compute beta in the hard case
if (p != 0) {
const h = lam[(n_count & (~pi[p] + 1))];
beta[p] = ((n_count >> @intCast(h)) | 1) << @intCast(h);
} else {
// Exit traversal
break;
}
}
if (p == 0) {
break;
}
}
// Begin second traversal
p = nodes[0].child;
lam[0] = lam[n_count];
pi[0] = 0;
beta[0] = 0;
alfa[0] = 0;
// Perform second traversal
if (p != 0) {
computeAlfa(p, nodes, alfa, beta);
}
defer allocator.free(nodes);
return ProcessResult{
.pi = pi,
.beta = beta,
.alfa = alfa,
.tau = tau,
.lam = lam,
};
}
fn computeAlfa(p: usize, nodes: []const Node, alfa: []usize, beta: []const usize) void {
// s7: Compute alfa, top-down
alfa[p] = alfa[nodes[p].parent] | (beta[p] & (~beta[p] + 1));
if (nodes[p].child != 0) {
computeAlfa(nodes[p].child, nodes, alfa, beta);
}
// s8: Continue traversal
if (nodes[p].sib != 0) {
computeAlfa(nodes[p].sib, nodes, alfa, beta);
}
}
fn nca(
x_param: usize,
y_param: usize,
beta: []const usize,
alfa: []const usize,
tau: []const usize,
lam: []const i32,
pi: []const usize,
) usize {
var x = x_param;
var y = y_param;
// Find common height
var h = if (beta[x] <= beta[y])
lam[(beta[y] & (~beta[x] + 1))]
else
lam[(beta[x] & (~beta[y] + 1))];
// Find true height
const k = alfa[x] & alfa[y] & (~(@as(usize, 1) << @intCast(h)) + 1);
h = lam[(k & (~k + 1))];
// Find beta[z]
const j = ((beta[x] >> @intCast(h)) | 1) << @intCast(h);
// Find x' and y'
if (j != beta[x]) {
const l = lam[(alfa[x] & ((@as(usize, 1) << @intCast(h)) - 1))];
x = tau[((beta[x] >> @intCast(l)) | 1) << @intCast(l)];
}
if (j != beta[y]) {
const l = lam[(alfa[y] & ((@as(usize, 1) << @intCast(h)) - 1))];
y = tau[((beta[y] >> @intCast(l)) | 1) << @intCast(l)];
}
// Find z
return if (pi[x] <= pi[y]) x else y;
}
fn solveTestCase(
allocator: Allocator,
n: usize,
values: []const i32,
queries: []const [2]usize,
) ![]i32 {
var results = ArrayList(i32).init(allocator);
defer results.deinit();
var a = ArrayList(i32).init(allocator);
defer a.deinit();
try a.append(std.math.maxInt(i32)); // A[0]
var r = try allocator.alloc(usize, n + 2);
defer allocator.free(r);
var b = try allocator.alloc(usize, n + 2);
defer allocator.free(b);
@memset(r, 0);
@memset(b, 0);
var big_n: usize = 1;
var count: i32 = 0;
var oldx: ?i32 = null;
for (1..n + 1) |i| {
const x = values[i - 1];
if (i > 1 and (oldx == null or x != oldx.?)) {
try a.append(count);
r[big_n] = i;
big_n += 1;
count = 0;
}
b[i] = big_n;
count += 1;
oldx = x;
}
try a.append(count);
r[big_n] = n + 1;
const process_result = try process(allocator, big_n, a.items);
defer {
allocator.free(process_result.pi);
allocator.free(process_result.beta);
allocator.free(process_result.alfa);
allocator.free(process_result.tau);
allocator.free(process_result.lam);
}
for (queries) |query| {
const i = query[0];
const j = query[1];
const x = b[i];
const y = b[j];
const z = if (x == y)
@as(i32, @intCast(j - i + 1))
else blk: {
var z_val: i32 = if (x + 1 != y)
a.items[nca(x + 1, y - 1, process_result.beta, process_result.alfa, process_result.tau, process_result.lam, process_result.pi)]
else
0;
z_val = @max(z_val, @max(
@as(i32, @intCast(r[x] - i)),
a.items[y] - @as(i32, @intCast(r[y] - j - 1))
));
break :blk z_val;
};
try results.append(z);
}
return results.toOwnedSlice();
}
pub fn main() !void {
var gpa = std.heap.GeneralPurposeAllocator(.{}){};
defer _ = gpa.deinit();
const allocator = gpa.allocator();
// Hard-coded test data
const TestCase = struct {
n: usize,
values: []const i32,
queries: []const [2]usize,
expected: []const i32,
};
const test_cases = [_]TestCase{
TestCase{
.n = 10,
.values = &[_]i32{ -1, -1, 1, 1, 1, 1, 3, 10, 10, 10 },
.queries = &[_][2]usize{ [_]usize{ 2, 3 }, [_]usize{ 1, 10 }, [_]usize{ 5, 10 } },
.expected = &[_]i32{ 1, 4, 3 },
},
};
for (test_cases, 0..) |test_case, idx| {
print("Test Case {}:\n", .{idx + 1});
print("Size: {}, Queries: {}\n", .{ test_case.n, test_case.queries.len });
print("Values: ", .{});
for (test_case.values) |v| {
print("{} ", .{v});
}
print("\n", .{} );
const results = try solveTestCase(allocator, test_case.n, test_case.values, test_case.queries);
defer allocator.free(results);
print("Queries and Results:\n", .{});
for (test_case.queries, 0..) |query, q_idx| {
const i = query[0];
const j = query[1];
const result = results[q_idx];
const exp = test_case.expected[q_idx];
print("Query: {} {}\n", .{ i, j });
print("Result: {} (Expected: {})\n", .{ result, exp });
if (result != exp) {
print(" WARNING: Result doesn't match expected output\n", .{});
}
}
print("\n", .{} );
}
}
- Output:
Test Case 1: Size: 10, Queries: 3 Values: -1 -1 1 1 1 1 3 10 10 10 Queries and Results: Query: 2 3 Result: 1 (Expected: 1) Query: 1 10 Result: 4 (Expected: 4) Query: 5 10 Result: 3 (Expected: 3)