Solution to UVa 11235 using Schieber-Vishkin algorithm

vishkin.c

#include <stdio.h>
#include <stdlib.h>
#include <limits.h>

#define forn(i,n) for(i=0; i<(n); i++)
#define forsn(i,s,n) for(i=(s); i<(n); i++)

#define MAXN 100001
int N, A[MAXN], pi[MAXN], beta[MAXN], alfa[MAXN], tau[MAXN], lam[MAXN];
struct node {
	int child, sib, parent;
};
#define CHILD(v) nodes[v].child
#define SIB(v) nodes[v].sib
#define PARENT(v) nodes[v].parent

void process(void) {
	int u,v,p,h,n,t;
	struct node *nodes = calloc(N+1,sizeof(*nodes));

	/* make triply linked tree */
	t = 0;
	for(v=N; v>0; v--) {
		u = 0;
		while(A[v]>A[t] || (A[v]==A[t] && v>t)) {
			u = t;
			t = PARENT(t);
		}
		if(u) {
			SIB(v) = SIB(u);
			SIB(u) = 0;
			PARENT(u) = v;
			CHILD(v) = u;
		} else
			SIB(v) = CHILD(t);
		CHILD(t) = v;
		PARENT(v) = t;
		t = v;
	}

	/* begin first traversal */
	p = CHILD(0);
	n = 0;
	lam[0] = -1;

s3: /* compute beta in the easy case */
	n++;
	pi[p] = n;
	tau[n] = 0;
	lam[n] = 1+lam[n>>1];
	if(CHILD(p)) {
		p = CHILD(p);
		goto s3;
	}
	beta[p] = n;

s4: /* compute tau, bottom-up */
	tau[beta[p]] = PARENT(p);
	if(SIB(p)) {
		p = SIB(p);
		goto s3;
	}
	p = PARENT(p);

	/* compute beta in the hard case */
	if(p) {
		h = lam[n & -pi[p]];
		beta[p] = ((n>>h)|1)<<h;
		goto s4;
	}

	/* begin second traversal */
	p = CHILD(0);
	lam[0] = lam[n];
	pi[0] = beta[0] = alfa[0] = 0;

s7: /* compute alfa, top-down */
	alfa[p] = alfa[PARENT(p)] | (beta[p] & -beta[p]);
	if(CHILD(p)) {
		p = CHILD(p);
		goto s7;
	}

s8:	/* continue to traverse */
	if(SIB(p)) {
		p = SIB(p);
		goto s7;
	} else {
		p = PARENT(p);
		if(p) goto s8;
	}
	free(nodes);
}

int nca(int x, int y) {
	int h,k,j,l,z;

	/* 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 = (pi[x] <= pi[y]) ? x : y;
	return z;
}

int max(int a, int b) {
	return a > b ? a : b;
}

int main(void) {
	int n,i,j,q,Q,x,y,oldx,count,z;
	int R[MAXN],B[MAXN];
	for(;;) {
		scanf("%d", &n);
		if(!n) break;
		scanf("%d", &Q);
		A[0] = INT_MAX;
		N=1, count=0;
		forsn(i,1,n+1) {
			scanf("%d", &x);
			if(i>1 && x!=oldx) {
				A[N] = count;
				R[N] = i;
				N++;
				count = 0;
			}
			B[i] = N;
			count++;
			oldx = x;
		}
		A[N] = count;
		R[N] = i;
		process();
		forn(q,Q) {
			scanf("%d%d", &i, &j);
			x=B[i], y=B[j];
			if(x == y) {
				z = j-i+1;
			} else {
				z = (x+1 != y) ? A[nca(x+1,y-1)] : 0;
				z = max(z, max(R[x]-i, A[y]-R[y]+j+1));
			}
			printf("%d\n", z);
		}
	}
	return 0;
}