【BZOJ 3325】[Scoi2013] 密码

题目传送门：http://www.lydsy.com/JudgeOnline/problem.php?id=3325
离线版题目：http://paste.ubuntu.com/18029355/
数据生成器：http://paste.ubuntu.com/18029394/

最近都在做字符串，所以接触了一点逆向字符串的题目，于是这题就会做啦！
这类给你字符串结构的过程数组，叫你统计方案数/构造符合要求的字符串，说到底就是给了你一堆字符等与不等的关系
而你就需要根据具体数据结构的特点来处理这些关系
比如说这道题，我上周六想了半个小时，一点思路都没有，觉得提供的关系可能是O(n^2)的。
但今天再来想的时候发现，相等关系可以用和manacher时间复杂度一样的整法证到时O(n)的
而不等关系很明显是O(n)的，于是保存好关系，并查集缩一缩点就搞好啦！
基本上1A！ 撒花！ *★,°*:.☆\(￣▽￣)/$:*.°★*

#include<iostream>
#include<cstdio>
#include<set>
#define SITR set<int>::iterator
using namespace std;

inline int read(){
	char c=getchar(); int buf=0,f=1;
	while (c<'0'||c>'9'){if(c=='-')f=-1;c=getchar();}
	while (c<='9'&&c>='0'){buf=buf*10+c-'0';c=getchar();}
	return buf*f;
}

const int MAXN = 100000+9;
const int SIGMA_SIZE = 26;

int ld[MAXN],lo[MAXN],fa[MAXN];
int n,mx=1,vout[MAXN],col[MAXN];
set<int> Q[MAXN];

inline int find(int w){
	int f=fa[w],tmp;
	while (fa[f] != f) f=fa[f];
	while (w != f) tmp=fa[w],fa[w]=f,w=tmp;
	return f;
}

inline void connect(int a, int b){
	int f1=find(a), f2=find(b);
	if (f1 != f2) fa[f1] = f2;
}

inline void discon(int a, int b){
	Q[fa[a]].insert(fa[b]);
	Q[fa[b]].insert(fa[a]);
}

int main(){
	n = read(); 
	for (int i=1;i<=n;i++) fa[i] = i; 
	for (int i=1;i<=n;i++) ld[i] = (read()-1)/2;
	for (int i=1;i<n;i++)  lo[i] = read()/2;
	
	for (int i=1;i<=n;i++){
		for (int j=max(mx-i+1,1);j<=ld[i];j++)
			connect(i+j,i-j);	
		mx = max(mx, i+ld[i]);
		
		for (int j=max(mx-i+1,1);j<=lo[i];j++)
			connect(i+j,i-j+1);		
		mx = max(mx, i+lo[i]);
	}
	for (int i=1;i<=n;i++)  fa[i]=find(i);
	for (int i=1;i<=n;i++){ if (i-ld[i] > 1 && i+ld[i] < n) discon(i+ld[i]+1,i-ld[i]-1); if (i-lo[i] > 0 && i+lo[i] < n) 
			discon(i+lo[i]+1,i-lo[i]);
	}
	
	for (int i=1;i<=n;i++){
		if (vout[fa[i]]) continue;
		else {
			for (SITR j=Q[fa[i]].begin();j!=Q[fa[i]].end();j++)
				col[vout[*j]] = i;
			for (int j=1;j<=SIGMA_SIZE;j++)
				if (col[j] < i) {vout[fa[i]] = j; break;}
		}
	}
	
	for (int i=1;i<=n;i++) putchar(vout[fa[i]]+'a'-1);
	
	return 0;
}