一道神题 (holyshit)
Time Limit:1000ms Memory Limit:128MB
题目描述
LYK有n个数ai。
它想找两段互不相交的区间。
要求：不存在一个数在这两段区间中总共的出现次数超过1次。
LYK想使得取出的两段区间的长度的和尽可能大。
问这个值最大是多少。
输入格式(holyshit.in)
第一行一个数n。
接下来一行n个数ai。
输出格式(holyshit.out)
一个数表示可能的最大值是多少
输入样例
10
//代码效果参考： http://www.zidongmutanji.com/zsjx/176575.html3 1 2 1 2 4 5 4 5 6
输出样例
6
样例解释
取区间【1,3】和【8,10】是最优的。
数据范围
对于20%的数据n<=10。
对于40%的数据n<=50。
对于60%的数据n<=200。
对于100%的数据2<=n<=2000，1<=ai<=n。
g【i】【j】 表示 【i,j】取一段子区间，没有元素重复，使得子区间长度最长 n^2
g【i】【j-1】 g【i+1】【j】 【i,j】没有元素重复
1 for (i=n; i>=1; i--){
2 for (j=1; j<=n; j++) v【j】=false; FLAG=true;
3 for (j=i; j<=n; j++){
4 if (v【a【j】】) FLAG=false;
5 v【a【j】】=true;
6 if (FLAG) g【i】【j】=j-i+1; else g【i】【j】=max(g【i+1】【j】,g【i】【j-1】);
7 }
8 }
先把所有符合条件的区间全部搞出来，由这些区间取扩展到g更大
【A,B】是合法的， 则 g【A】【B】=B-A+1 g【l】【r】 l=B 都有g【l】【r】>=B-A+1 n^2
先枚举第一段区间的右端点r，当l=1时，求出所有×的位置，并求出第二段区间能取的最大长度。
随着l往右走，部分×被解锁，更新第二段区间的最大长度（并查集实现），然后更新答案。
f【i】表示在并查集树上的父亲，i的祖先就表示从i出发向右最近×的位置。
x这个位置被解锁了，getf(x+1)表示新增的区间右端点在哪里， 更新f呢，f【x】=getf(x+1);
