【BZOJ 3790】神奇项链

题目传送门:http://www.lydsy.com/JudgeOnline/problem.php?id=3790
离线版题目:http://paste.ubuntu.com/17470379/
吐槽:板题,直接上代码不解释

#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;

const int MAXN = 120000;

char pat[MAXN],chr[MAXN];
int n,l[MAXN],r[MAXN],len[MAXN],ord[MAXN];

namespace FenwickTree{
	#define BIT FenwickTree
	#define low(x) (x&(-x))
	#define INF 1000000000
	int arr[MAXN],buf[MAXN];

	inline void init(){
		for (int i=1;i<=n;i++)
			arr[i] = buf[i] = INF;
	}

	inline int query(int left, int right){
		if (right < left) return INF; else { int ret = INF; while (right >= left){
				if (right-low(right)+1>=left) ret = min(ret,arr[right]),right-=low(right);
				else ret = min(ret,buf[right]), right--;
			}
			return ret;
		}
	}

	inline void modify(int pos, int nv){
		if (buf[pos] > nv) {
			buf[pos] = nv;
			for (int i=pos;i<=n;i+=low(i)) if (arr[i] > nv) arr[i] = nv;
				else break;
		} else return;
	}
};

inline bool sort_cmp(const int &A, const int &B){
	return r[A] < r[B];
}

inline int manacher(){
	int m=n*2+1,itr=0;
	for (int i=1;i<=n;i++)
		chr[i*2-1] = '@',
		chr[i*2] = pat[i];
	chr[m] = '@'; chr[m+1] = '#'; chr[0] = '$';

	for (int i=1,p1,p2;i<=m;i++){ if (itr+len[itr] > i)  len[i] = min(len[2*itr-i],itr+len[itr]-i);
		else len[i] = 0;
		p1 = i-len[i]; p2 = i+len[i];
		while (chr[--p1] == chr[++p2]) len[i]++;
		if (itr+len[itr] < i+len[i]) itr = i;
	}

	for (int i=1;i<=m;i++)
		r[i] = i+len[i],
		l[i] = i-len[i],
		ord[i] = i;
	sort(ord+1,ord+m,sort_cmp);

	n = m; BIT::init(); BIT::modify(1,0);
	for (int j=1,i=ord[j],tmp;j<=n;j++,i=ord[j]){
		tmp = BIT::query(l[i],r[i]-1)+1;
		BIT::modify(r[i],tmp);
	}

	return BIT::query(m-1,m)-1;
}

int main(){
	while (~scanf("%s",pat+1)){
		n = strlen(pat+1);
		printf("%dn",manacher());
	}
	return 0;
}