なるほど…。
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; } }
まとめ
こういうのさっと思い浮かばないな。