厦门大学程序设计大赛月赛 A. 环鸽的CHONG

题目大意:给定n个元素的序列，判断序列的所有连续的子序列是否全是好序列。
好序列:序列存在唯一元素-------存在 满足序列中其他所有元素 ， .

分析:考虑对区间进行分治.
首先是最大的区间 我们需要找到区间内唯一的元素，假如位置为 ,那么连续区间的左端点在
选取,区间右端点在选取，所构成的区间一定是好区间，当然也包括 作为左区间边界或者右区间边界构成的区间，这些都是好序列.
那么我们下一步要知道的是区间 区间中连续的子序列是否满足好序列.
那么这个就是分治的递归.
对于当前区间我们要找到是否有元素在该区间是唯一，然后进行分治判断即可.
判断是否唯一，显然我们要预处理对于每一个元素作为唯一元素的连续区间 ， 对应左区间为元素上一次出现的位置， 右区间为元素下一次出现的位置.dfs的时候进行遍历判断即可.
当然我们可以特判一下如果序列中有相邻元素相同，那么直接判断不是好序列.

#include<bits/stdc++.h>
using namespace std;

typedef long long ll;
map<int,int> mp;
const int maxn=2e5+10;
int a[maxn],l[maxn],r[maxn];

bool dfs( int ls,int rs )
{
    if( ls>=rs ) return true;
    int i=ls;
    while( i<=rs )
    {
        if( l[i]<ls && r[i]>rs )
        return dfs(ls,i-1) && dfs(i+1,rs);
        i++;
    }
    return false;
}

int main()
{
    int n;
    cin>>n;
    bool flag=true;
    for( int i=1;i<=n;i++ )
    {
        cin>>a[i];
        if( !mp[a[i]] ) l[i]=0;
        else l[i]=mp[a[i]];
        mp[a[i]]=i;
        if( a[i]==a[i-1] ) flag=false;
    }
    mp.clear();
    for( int i=n;i;i-- )
    {
        if( !mp[a[i]] ) r[i]=n+1;
        else r[i]=mp[a[i]];
        mp[a[i]]=i;
    }
    if( !flag ) puts("fuchong");
    else puts( dfs(1,n) ? "chong" : "fuchong" );
    return 0;

}