yukicoder : No.1786 Maximum Suffix Median (Online)

なるほど…。
https://yukicoder.me/problems/no/1786

問題

整数列Aの要素が、1つずつ与えられる。
要素が与えられるたび、(確定済みの)AのSuffixにおけるMedianの最大値を求めよ。

解法

現時点でのAの要素数をN、解をXとする。
すると

• A[N]≦X
• A[N-1]....A[N-2K]の間にX以下のものがK個以上

であるXの最小値となる。

後者は言い換えるとA[N-1]...A[N-2K]のうち大きいものK個を取り除いた時の最大値といえる。
そこで、これを以下のように処理する。

multiset Sを用意し、A[N-1]とA[N]を追加してSを取り除く。
残されたSの最大値がA[N]を追加したときの解。

以下のコードでは、A[N]を受け取った時点でSに2回A[N]を追加している。
これはA[N]を受け取ったときとA[N+1]を受け取ったときで2回A[N]を追加するのをまとめて行っているだけ。

int N;
int ret=0;

void solve() {
	int i,j,k,l,r,x,y; string s;
	
	multiset<int> S;
	S.insert(0);
	cin>>N;
	FOR(i,N) {
		cin>>x;
		x^=ret;
		S.insert(x);
		S.insert(x);
		S.erase(S.find(*S.rbegin()));
		ret=*S.rbegin();
		cout<<ret<<endl;
		
	}
}

まとめ

こういうのさっと思い浮かばないな。