これは方針は割とすぐ着いたな。
https://yukicoder.me/problems/no/2223
問題
整数列Xの美しさとは、以下を意味するものとする。
ある部分列を選び、各要素をその部分列の中央値で置き換える。その後得られるX全体の中央値を考える。
部分列の全選び方のうち、最終的な中央値の最小値が美しさとなる。
整数列Aが与えられる。
クエリとして部分列が指定されるので、その部分列の美しさを求めよ。
解法
各クエリを並列二分探索で解く。
以下、美しさがB以下か?という問題を考えよう。
Aの各要素を、Bより大きいなら1、B以下なら-1で置き換えよう。
各クエリにおいて、クエリで指定された部分列のうち、さらに一部の部分列を単一要素の1で置き換えたとき、得られる数列の総和が負であれば、美しさがB以下にできる。
となると、部分列のうち総和が最大となるものを1で置き換えるのが最適である。
これは、SegTreeで求めることが出来る。
int N,Q; int A[505050]; int L[505050],R[505050]; int ret[505050]; vector<int> cand[505050]; struct D { int Lma,Rma,ma,sum; }; template<class V,int NV> class SegTree_1 { public: vector<V> val; V comp(V a,V b){ if(b.sum==-1<<20) return a; if(a.sum==-1<<20) return b; V c; c.Lma=max(a.Lma,a.sum+b.Lma); c.Rma=max(a.Rma+b.sum,b.Rma); c.ma=max({a.ma,b.ma,a.Rma+b.Lma}); c.sum=a.sum+b.sum; return c; } SegTree_1(){val=vector<V>(NV*2);}; 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,-1<<20}; 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)); } }; SegTree_1<D,1<<16> st; void solve() { int i,j,k,l,r,x,y; string s; cin>>N>>Q; FOR(i,N) cin>>A[i]; FOR(i,Q) { cin>>L[i]>>R[i]; L[i]--; ret[i]=N; cand[N].push_back(i); } for(int span=1<<15;span>=1;span/=2) { for(int cur=N;cur>span;cur-=span*2) if(cand[cur].size()) { vector<int> c=cand[cur]; cand[cur].clear(); FOR(i,N) { if(A[i]<=cur-span) { st.val[(1<<16)+i]={-1,-1,-1,-1}; } else { st.val[(1<<16)+i]={1,1,1,1}; } } for(i=(1<<16)-1;i>=1;i--) st.val[i]=st.comp(st.val[i*2],st.val[i*2+1]); FORR(i,c) { D d=st.getval(L[i],R[i]); if(d.sum<0||d.sum-d.ma+1<0) ret[i]-=span; cand[ret[i]].push_back(i); } } } FOR(i,Q) cout<<ret[i]<<endl; }
まとめ
久々に並列二分探索した気がする。