Codeforces #727 Div2 : F. Strange Array

またややこしい問題設定だなぁ。
https://codeforces.com/contest/1539/problem/F

問題

整数列Aが与えられる。
各要素iのstrangenessは以下のように定義される。
iを含むAの連続部分列A[L...R]を抜き出し、昇順にソートする。
その中央値とA[i]の差の絶対値を考える。その値が最大となるようなA[L...R]の選び方をできるとき、その値がstrangenessとなる。

各要素のstrangenessを求めよ。

解法

今値vを見ているとき、できるだけv未満の値を多く含むような区間の選び方と、逆にv以上の値を多く含むような区間の選び方をそれぞれ求めよう。
これはSegTreeを使い、A[i]の区間に対し

• prefixのうちv以上/v未満の値が超過する個数の最大値
• suffixのうちv以上/v未満の値が超過する個数の最大値
• 区間内の部分区間を選んだ時、v以上/v未満の値が超過する個数の最大値

を管理していけばよい。そうすると、A[i]を含む最適なA[L...R]の区間が求められる。

A[i]の小さい順または大きい順に、SegTreeを更新しながら上記値を求めればよい。

template<class V,int NV> class SegTree_1 {
public:
	vector<V> val;
	V comp(V l,V r){
		int a=max(get<0>(l),get<2>(l)+get<0>(r));
		int b=max(get<1>(r),get<2>(r)+get<1>(l));
		int c=get<2>(l)+get<2>(r);
		return {a,b,c};
	};
	
	SegTree_1(){val=vector<V>(NV*2,{0,0,0});};
	V getval(int x,int y,int l=0,int r=NV,int k=1) { // x<=i<y
		if(r<=x || y<=l) return {0,0,0};
		if(x<=l && r<=y) return val[k];
		return comp(getval(x,y,l,(l+r)/2,k*2),getval(x,y,(l+r)/2,r,k*2+1));
	}
	void update(int entry, int v) {
		entry += NV;
		val[entry]={max(0,v),max(0,v),v};
		while(entry>1) entry>>=1, val[entry]=comp(val[entry*2],val[entry*2+1]);
	}
};
SegTree_1<tuple<int,int,int>,1<<18> st;

int N;
int A[202020];
vector<int> ev[202020];
int ret[202020];


void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>N;
	FOR(i,N) {
		cin>>A[i];
		A[i]--;
		ev[A[i]].push_back(i);
		st.update(i,1);
	}
	FOR(i,N) {
		FORR(a,ev[i]) chmax(ret[a],(get<1>(st.getval(0,a))+get<0>(st.getval(a+1,N))+1)/2);
		FORR(a,ev[i]) st.update(a,-1);
	}
	FOR(i,N) st.update(i,1);
	for(i=N-1;i>=0;i--) {
		FORR(a,ev[i]) chmax(ret[a],(get<1>(st.getval(0,a))+get<0>(st.getval(a+1,N))+0)/2);
		FORR(a,ev[i]) st.update(a,-1);
	}
	FOR(i,N) cout<<ret[i]<<" ";
	cout<<endl;
	
		
	
	
}

まとめ

問題文の理解に手間取った。