kmjp's blog

競技プログラミング参加記です

Codeforces ECR #064 : E. Special Segments of Permutation

今見るとあまり迷わないかな…と思ったけどそこそこ手間取ってた。
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が気になる解法。