4326191_wa.cpp

北大大牛代码 1240道题的原代码 超级权威

#include <vector>
#include <stdio.h>
#include <algorithm>

using namespace std;

inline bool leq(int a1, int a2, int b1, int b2) // lexicographic order
{ return(a1 < b1 || a1 == b1 && a2 <= b2); } // for pairs

inline bool leq(int a1, int a2, int a3, int b1, int b2, int b3)
{ return(a1 < b1 || a1 == b1 && leq(a2,a3, b2,b3)); } // and triples

// stably sort a[0..n-1] to b[0..n-1] with keys in 0..K from r
static void radixPass(int* a, int* b, int* r, int n, int K)
{ // count occurrences
	int* c = new int[K + 1]; // counter array
	for (int i = 0; i <= K; i++) c[i] = 0; // reset counters
	for (int i = 0; i < n; i++) c[r[a[i]]]++; // count occurrences
	for (int i = 0, sum = 0; i <= K; i++) // exclusive prefix sums
	{
		int t = c[i];
		c[i] = sum; 
		sum += t;
	}
	for (int i = 0; i < n; i++) b[c[r[a[i]]]++] = a[i]; // sort
	delete [] c;
}
// find the suffix array SA of T[0..n-1] in {1..K}^n
// require T[n]=T[n+1]=T[n+2]=0, n>=2
void suffixArray(int* T, int* SA, int n, int K) 
{
	int n0=(n+2)/3, n1=(n+1)/3, n2=n/3, n02=n0+n2;
	int* R = new int[n02 + 3]; R[n02]= R[n02+1]= R[n02+2]=0;
	int* SA12 = new int[n02 + 3]; SA12[n02]=SA12[n02+1]=SA12[n02+2]=0;
	int* R0 = new int[n0];
	int* SA0 = new int[n0];
	//******* Step 0: Construct sample ********
	// generate positions of mod 1 and mod 2 suffixes
	// the "+(n0-n1)" adds a dummy mod 1 suffix if n%3 == 1
	
	for (int i=0, j=0; i < n+(n0-n1); i++) if (i%3 != 0) R[j++] = i;
	
	//******* Step 1: Sort sample suffixes ********
	// lsb radix sort the mod 1 and mod 2 triples
	radixPass(R , SA12, T+2, n02, K);
	radixPass(SA12, R , T+1, n02, K);
	radixPass(R , SA12, T , n02, K);
	// find lexicographic names of triples and
	// write them to correct places in R
	int name = 0, c0 = -1, c1 = -1, c2 = -1;

	for (int i = 0; i < n02; i++) 
	{
		if (T[SA12[i]] != c0 || T[SA12[i]+1] != c1 || T[SA12[i]+2] != c2)
		{
			name++;
			c0 = T[SA12[i]];
			c1 = T[SA12[i]+1];
			c2 = T[SA12[i]+2];
		}
		if (SA12[i] % 3 == 1)
		{
			R[SA12[i]/3] = name; 
		} // write to R1
		else
		{
			R[SA12[i]/3 + n0] = name; 
		} // write to R2
	}
	// recurse if names are not yet unique
	if (name < n02) 
	{
		suffixArray(R, SA12, n02, name);
		// store unique names in R using the suffix array
		for (int i = 0; i < n02; i++) R[SA12[i]] = i + 1;
	}
	else // generate the suffix array of R directly
	{
		for (int i = 0; i < n02; i++) SA12[R[i] - 1] = i;
	}
	//******* Step 2: Sort nonsample suffixes ********
	// stably sort the mod 0 suffixes from SA12 by their first character
	for (int i=0, j=0; i < n02; i++) if (SA12[i] < n0) R0[j++] = 3*SA12[i];
	radixPass(R0, SA0, T, n0, K);
	//******* Step 3: Merge ********
	// merge sorted SA0 suffixes and sorted SA12 suffixes
	for (int p=0, t=n0-n1, k=0; k < n; k++) 
	{
#define GetI() (SA12[t] < n0 ? SA12[t] * 3 + 1 : (SA12[t] - n0) * 3 + 2)
		int i = GetI(); // pos of current offset 12 suffix
		int j = SA0[p]; // pos of current offset 0 suffix
		if (SA12[t] < n0 ? // different compares for mod 1 and mod 2 suffixes
			leq(T[i], R[SA12[t] + n0], T[j], R[j/3]) :
			leq(T[i],T[i+1],R[SA12[t]-n0+1], T[j],T[j+1],R[j/3+n0]))
		{ // suffix from SA12 is smaller
			SA[k] = i; t++;
			if (t == n02) // done --- only SA0 suffixes left
			{
				for (k++; p < n0; p++, k++) SA[k] = SA0[p];
			}
		}
		else
		{ // suffix from SA0 is smaller
			SA[k] = j; p++;
			if (p == n0) // done --- only SA12 suffixes left
			{
				for (k++; t < n02; t++, k++) SA[k] = GetI();
			}
		}
	}
	delete [] R; delete [] SA12; delete [] SA0; delete [] R0;
}

int n, a[200010], sa[200010], t[200010], pos[200010], b[200010];
vector <int> v;

int find(int num)
{
	int min = 0, max = v.size() - 1;
	int mid;

	while (min <= max)
	{
		mid = (min + max) >> 1;
		if (v[mid] < num)
			min = mid + 1;
		else
		{
			if (v[mid] > num)
				max = mid - 1;
			else
				return mid + 1;
		}
	}
	return -1;
}

int main()
{
	int i;

	scanf("%d", &n);

	for (i = 0; i < n; i++)
	{
		scanf("%d", &t[i]);
		a[n - i - 1] = t[i];
	}
	if (n == 3)
	{
		printf("%d\n%d\n%d\n", t[0], t[1], t[2]);
		return 0;
	}
	sort(t, t + n - 2);
	int cnt = 0;
	v.clear();
	v.push_back(t[0]);
	for (i = 1; i < n - 2; i++)
	{
		if (t[i] != t[i - 1])
		{
			v.push_back(t[i]);
		}
	}

	for (i = 2; i < n; i++)
	{
		b[i] = find(a[i]);
	}

	b[n] = b[n + 1] = b[n + 2] = 0;

	suffixArray(&b[2], sa, n - 2, v.size() + 1);

	int r;
	
	r = sa[0];
	r += 2;

	for (int j = r; j < n; j++)
		printf("%d\n", a[j]);

	if (r == 2)
	{
		printf("%d\n%d\n", a[1], a[0]);
		return 0;
	}
	for (i = 1; i < r; i++)
	{
		t[i] = a[i];
	}
	sort(&t[1], &t[1] + r - 1);
	v.clear();
	v.push_back(t[1]);
	for (i = 2; i < r; i++)
	{
		if (t[i] != t[i - 1])
		{
			v.push_back(t[i]);
		}
	}
	for (i = 1; i < r; i++)
	{
		b[i] = find(a[i]);
	}
	b[r] = b[r + 1] = b[r + 2] = 0;

	suffixArray(&b[1], sa, r - 1, v.size() + 1);

	int q = sa[0] + 1;

	if (q == r - 1 && a[q] == a[q - 1])
	{
		if (a[0] > a[q])
		{
			int v = a[r - 1];
			while (q > 0 && a[q] == v)
				q--;
			q++;
		}
	}
	for (i = q; i < r; i++)
		printf("%d\n", a[i]);
	for (i = 0; i < q; i++)
		printf("%d\n", a[i]);
	return 0;
}