Deltix Round Autumn 2021 : F. Interesting Sections

これは割と典型かもな…。
https://codeforces.com/contest/1609/problem/F

問題

整数列Aが与えられる。部分列のうち、以下を満たすものは何通りか。
部分列中最大値と最小値のpopcountが等しい。

解法

分割統治の要領で解く。
区間の中央から左と右に部分列の範囲を伸ばしていくとき、尺取り法の要領で、左端を定めたときに、最小値・最大値を更新しない範囲でどこまで右端を伸ばせるかを見て行くとよい。

int N;
ll A[1010101];
int P[1010101];
ll miA[1010101];
ll maA[1010101];
ll ret;
int step;
void dfs(int L,int R) {
	
	if(R-L<=1) {
		ret+=R-L;
		return;
	}
	
	int M=(L+R)/2;
	int i,j;
	miA[M-1]=maA[M-1]=A[M-1];
	for(i=M-2;i>=L;i--) {
		miA[i]=min(miA[i+1],A[i]);
		maA[i]=max(maA[i+1],A[i]);
	}
	miA[M]=maA[M]=A[M];
	for(i=M+1;i<R;i++) {
		miA[i]=min(miA[i-1],A[i]);
		maA[i]=max(maA[i-1],A[i]);
	}
	
	int D[60]={};
	int L1=M,L2=M;
	
	miA[M]=maA[M]=A[M];
	for(i=M;i<R;i++) {
		int pma=__builtin_popcountll(maA[i]);
		int pmi=__builtin_popcountll(miA[i]);
		while(L1>L&&maA[L1-1]<=maA[i]) L1--, D[__builtin_popcountll(miA[L1])]++;
		while(L2>L1&&miA[L2-1]>=miA[i]) L2--, D[__builtin_popcountll(miA[L2])]--;
		if(L1==M) continue;
		if(pma==pmi) ret+=M-L2;
		ret+=D[pma];
	}
	
	ZERO(D);
	
	int R1=M-1,R2=M-1;
	miA[M-1]=maA[M-1]=A[M-1];
	for(i=M-1;i>=L;i--) {
		int pma=__builtin_popcountll(maA[i]);
		int pmi=__builtin_popcountll(miA[i]);
		while(R1+1<R&&maA[R1+1]<maA[i]) R1++, D[__builtin_popcountll(miA[R1])]++;
		while(R2<R1&&miA[R2+1]>=miA[i]) R2++, D[__builtin_popcountll(miA[R2])]--;
		if(R1==M-1) continue;
		if(pma==pmi) ret+=R2-(M-1);
		ret+=D[pma];
	}
	
	
	dfs(L,M);
	dfs(M,R);
	
}


void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>N;
	FOR(i,N) {
		cin>>A[i];
		P[i]=__builtin_popcountll(A[i]);
	}
	dfs(0,N);
	cout<<ret<<endl;
}

まとめ

Eより素直な問題かも。