E2. Three Blocks Palindrome (hard version)
我们考虑一种最优构造
对于一个数x 我们肯定要的是他的前几个 再最后几个 中间选最多的一个数
这样显然是最优的
我们枚举x 再枚举前面要的长度
中间选的最多的一个数可以通过logn求解
总的时间复杂度是O(nvlogn)
int n,a[N];
vector<int>st[201];
int find(int i,int x){return lower_bound(all(st[i]),x)-st[i].begin();}
int find1(int i,int x) {return upper_bound(all(st[i]), x) - st[i].begin();}
int query(int l,int r){
int res=0;
for(int i=1;i<=201;i++)
res=max(res,find1(i,r)-find(i,l));
return res;
}
void solve(){
cin>>n;
for(int i=1;i<=200;i++)st[i].clear();
for(int i=1;i<=n;i++){
cin>>a[i];
st[a[i]].push_back(i);
}
int ans=1;
for(int x=1;x<=200;x++){
for(int len=1;len<=st[x].size();len++){
int l=st[x][len-1],r=st[x][st[x].size()-len];
if(l>=r)break;
ans=max(ans,len*2+query(l+1,r-1));
}
}
cout<<ans<<endl;
}
标签:634,int,Codeforces,st,query,ans,return,Div,bound
From: https://www.cnblogs.com/ycllz/p/16852850.html