思路:
如果在区间[l,r]之间有一个位置p,a[p]是唯一的,那么容易知道,左端点取[l,p-1],右端点取[p+1,r]都满足要求 即都是好序列,
那么只需要考虑两个区间是不是分别满足子区间都是好序列都可以。
所以处理出来离每个数字左右两端最近的位置,dfs即可。
#include<bits/stdc++.h> using namespace std; typedef long long ll; map<int,int> mp; int a[1<<18],l[1<<18],r[1<<18]; bool dfs(int ll,int rr){ if(ll>=rr) return 1; int i=ll,j=rr; while(i<=j){ if(l[i]<ll && r[i]>rr) return dfs(ll,i-1)&&dfs(i+1,rr); if(l[j]<ll && r[j]>rr) return dfs(ll,j-1)&&dfs(j+1,rr); i++,j--; } return 0; } int main(){ int n;cin>>n; 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; } mp.clear(); for(int i=n;i;i--){ if(!mp[a[i]]) r[i]=1e9; else r[i]=mp[a[i]]; mp[a[i]]=i; } int flag=dfs(1,n); puts(flag?"chong":"fuchong"); return 0; }