3035464_ac_1467ms_22120k.cc

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

#include <stdio.h>
#include <string.h>
#define MAX 1000001

int heap[MAX];
int lenth, cnt, n;
char str[MAX];
int len[MAX], pos[MAX], next[MAX], prev[MAX], left[MAX], right[MAX], ns[MAX];

int cmp(int a,int b)
{
	return (len[a]>len[b])||(len[a]==len[b]&&left[a]<left[b]);
}

void push(int p)
{
	int i;

	i = pos[p];
	while(i!=1&&cmp(p,heap[i>>1]))
	{
		heap[i] = heap[i>>1];
		pos[heap[i]] = i;
		i = i>>1;
	}
	heap[i] = p;
	pos[p] = i;
}

int pop()
{
	int ret, r;
	int par, chi;

	par = 1;chi = 2;
	ret = heap[1];
	r = heap[n--];
	while(chi<=n)
	{
		if(chi<n&&cmp(heap[chi+1],heap[chi]))
		{
			chi++;
		}
		if(cmp(heap[chi],r))
		{
			heap[par] = heap[chi];
			pos[heap[par]] = par;
			par = chi;
			chi = chi << 1;
		}
		else
		{
			break;
		}
	}
	heap[par] = r;
	pos[r] = par;
	return ret;
}

int main()
{
	int i, j, id, tmp;
	int a, b;

	scanf("%s",str);
	cnt = 0;
	n = 0;
	lenth = strlen(str);
	for(i = 0; i < lenth; i++)
	{
		j = i;
		while(j<lenth&&str[j]==str[i])
			j++;
		len[cnt] = j-i;
		left[cnt] = i;
		right[cnt] = j-1;
		ns[cnt] = -1;
		next[cnt] = cnt+1;
		prev[cnt] = cnt-1;
		heap[++n] = cnt;
		pos[cnt] = n;
		push(cnt);
		cnt++;
		i = j-1;
	}
	while(1)
	{
		if(n==0)
		{
			break;
		}
		id = pop();
		if(len[id]==1)
		{
			break;
		}
		tmp = id;
		printf("%c",str[left[tmp]]);
		while(tmp!=-1)
		{
			for(i = left[tmp]; i <= right[tmp]; i++)
			{
				printf(" %d",i+1);
			}
			tmp = ns[tmp];
		}
		printf("\n");
		a = prev[id];b = next[id];
		prev[b] = a;
		next[a] = b;
		if(a<0||b==cnt||str[left[a]]!=str[left[b]])
		{
			continue;
		}
		len[a] += len[b];
		tmp = a;
		while(ns[tmp]!=-1)
		{
			tmp = ns[tmp];
		}
		ns[tmp] = b;
		next[a] = next[b];
		prev[next[b]] = a;
		push(a);
		len[b] = 2100000000;
		push(b);
		pop();
	}
	return 0;
}