ちょっとオーバースペックな解法。
https://atcoder.jp/contests/abc237/tasks/abc237_g
問題
1~Nの順列Pが与えられる。
以下のクエリが計Q個与えられる。
- 区間[L,R]が指定されるので、P[L]...P[R]を昇順にソートする
- 区間[L,R]が指定されるので、P[L]...P[R]を降順にソートする
最終的にP中でXが格納されているindexを答えよ。
解法
色々な値が格納された数列をソートするのはつらいので、
- Pの各要素を、X以上かどうかで0/1に置き換えた数列Q
- Pの各要素を、Xよりかどうかで0/1に置き換えた数列R
それぞれを考えよう。
QもRも0/1だけで構成されるので、ソート処理は区間内の総和と区間内の値の更新ができるSegTreeがあればソートできる。
最終的にQ[i]=1でR[i]=0であるindex iがあれば、それは解となる。
int N,Q,X; int P[2][202020]; int C[202020],L[202020],R[202020]; template<class V,int NV> class SegTree_MulAdd { public: vector<V> sum,mul,add; // sum stores val after muladd SegTree_MulAdd(){sum.resize(NV*2,0); mul.resize(NV*2,1); add.resize(NV*2,0);}; V getval(int x,int y,int l=0,int r=NV,int k=1) { if(r<=x || y<=l) return 0; if(x<=l && r<=y) return sum[k]; x=max(x,l); y=min(y,r); V ret=getval(x,y,l,(l+r)/2,k*2)+getval(x,y,(l+r)/2,r,k*2+1); return ret*mul[k]+add[k]*(y-x); } void propagate(int k,int s) { mul[k*2]*=mul[k]; add[k*2]*=mul[k]; sum[k*2]*=mul[k]; add[k*2]+=add[k]; sum[k*2]+=add[k]*s/2; mul[k*2+1]*=mul[k]; add[k*2+1]*=mul[k]; sum[k*2+1]*=mul[k]; add[k*2+1]+=add[k]; sum[k*2+1]+=add[k]*s/2; mul[k]=1; add[k]=0; } void domul(int x,int y,V v,int l=0,int r=NV,int k=1) { if(l>=r) return; if(x<=l && r<=y) { mul[k]*=v; add[k]*=v; sum[k]*=v; } else if(l < y && x < r) { propagate(k,r-l); domul(x,y,v,l,(l+r)/2,k*2); domul(x,y,v,(l+r)/2,r,k*2+1); sum[k]=sum[k*2]+sum[k*2+1]; } } void doadd(int x,int y,V v,int l=0,int r=NV,int k=1) { if(l>=r) return; if(x<=l && r<=y) { add[k]+=v; sum[k]+=(r-l)*v; } else if(l < y && x < r) { propagate(k,r-l); doadd(x,y,v/mul[k],l,(l+r)/2,k*2); doadd(x,y,v/mul[k],(l+r)/2,r,k*2+1); sum[k]=sum[k*2]+sum[k*2+1]; } } }; SegTree_MulAdd<int, 1<<18> st[2]; void solve() { int i,j,k,l,r,x,y; string s; cin>>N>>Q>>X; FOR(i,N) { cin>>x; st[0].doadd(i,i+1,(int)(x>=X)); st[1].doadd(i,i+1,(int)(x>X)); } FOR(i,Q) { int C,L,R; cin>>C>>L>>R; L--; FOR(j,2) { x=st[j].getval(L,R); st[j].domul(L,R,0); if(C==1) { st[j].doadd(R-x,R,1); } else { st[j].doadd(L,L+x,1); } } } FOR(i,N) { if(st[0].getval(i,i+1)!=st[1].getval(i,i+1)) cout<<i+1<<endl; } }
まとめ
昔yukicoder向けに作った区間乗算・区間加算・区間和が計算できるSegTree、ちょくちょく役に立ってるな。