今見るとあまり迷わないかな…と思ったけどそこそこ手間取ってた。
https://codeforces.com/contest/1156/problem/E
問題
PのPermutationが与えられる。
区間[L...R]のうち、P[L]+P[R]=max(P[L...R])となるものは何通りか。
解法
Pを大きい順に処理していこう。
今処理対象の区間を[L,R]とし、最大値がP[M]であるとする。
この時、Mを含む区間[L',R']のうち、L≦L'≦M≦R'≦RとなるL',R'を列挙することを考える。
MがLに近いなら左端L'、Rに近いなら右端R'を総当たりし、対応する右端・左端の数を列挙しよう。
その後、区間[L,M-1]、[M+1,R]を再帰的に処理していく。
int N; int P[202020]; int rev[202020]; ll ret; void dfs(int L,int R,set<int>& S) { if(R-L<=2) return; set<int> S2; int M=rev[*S.rbegin()]; S.erase(*S.rbegin()); int x; if(M-L>R-M) { for(x=M+1;x<R;x++) { S.erase(P[x]); S2.insert(P[x]); } for(x=M+1;x<R;x++) { ret+=S.count(P[M]-P[x]); } dfs(L,M,S); dfs(M+1,R,S2); } else { for(x=L;x<M;x++) { S.erase(P[x]); S2.insert(P[x]); } for(x=L;x<M;x++) { ret+=S.count(P[M]-P[x]); } dfs(L,M,S2); dfs(M+1,R,S); } } void solve() { int i,j,k,l,r,x,y; string s; cin>>N; set<int> V; FOR(i,N) { cin>>P[i]; rev[P[i]]=i; V.insert(P[i]); } dfs(0,N,V); cout<<ret<<endl; }
まとめ
ちょっとTLEが気になる解法。