由于要求全部子区间都存在唯一元素,所以最初可以判断 是否符合,直接暴力for,然后记录只出现一次的元素的下标,存进一个vector里面,我们可以发现,只要包含唯一元素的区间,肯定符合条件,因为在区间
唯一,所以其他区间该元素肯定也唯一,就像分治一样,以这些唯一元素为分界点,递归其剩余区间。例如区间
,出现3个唯一元素下标为
,那么我们需要递归4个区间,
判断是否符合,因为这样做复杂度很迷,所以需要加上一个判断,读入的时候只要出现相邻元素一样,直接输出
#include <cctype>
#include <cfloat>
#include <cmath>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <ctime>
#include <algorithm>
#include <deque>
#include <fstream>
#include <functional>
#include <iomanip>
#include <iostream>
#include <istream>
#include <iterator>
#include <list>
#include <map>
#include <ostream>
#include <queue>
#include <set>
#include <sstream>
#include <stack>
#include <string>
#include <utility>
#include <vector>
#define ll long long
#define pll pair<long long,long long>
#define P pair<int,int>
#define PP pair<P,P>
#define eps 1e-4
#define It set<node>::iterator
using namespace std;
const int maxn=2e5+10;
int cnt[maxn],A[maxn],pos[maxn];
bool solve(int l, int r) {
// cout<<l<<' '<<r<<endl;
for (int i=l; i<=r; i++) cnt[A[i]]++;
vector<int> G;
for (int i=l; i<=r; i++) {
if (cnt[A[i]]==1) G.push_back(i);
cnt[A[i]]=0;
}
if (G.empty()) return false;
int L=l;
int len=G.size();
for (int i=0; i<len; i++) {
if (L<G[i]-1) {
if (!solve(L,G[i]-1)) return false;
}
L=G[i]+1;
}
if (L<r) return solve(L,r);
return true;
}
int main() {
// freopen("in.txt","r",stdin);
int n;
scanf("%d",&n);
bool ok=true;
for (int i=1; i<=n; i++) {
scanf("%d",&A[i]);
if (i!=1&&A[i]==A[i-1]) ok=false;
pos[i]=A[i];
}
if (!ok) {
printf("fuchong");
return 0;
}
sort(pos+1,pos+n+1);
int tot=unique(pos+1,pos+n+1)-pos-1;
for (int i=1; i<=n; i++) {
A[i]=lower_bound(pos+1,pos+tot+1,A[i])-pos;
}
bool flag=solve(1,n);
if (!flag) printf("fuchong");
else printf("chong");
return 0;
}


京公网安备 11010502036488号