yukicoder : No.3305 Shift Sort

ライブラリ化されていると割と簡単。
https://yukicoder.me/problems/no/3305

問題

整数Bに対し、区間[L,R]を指定すると、B[R]をB[L]の左に移動させることができるとする。

1～Nの順列Aが与えらえる。
以下のクエリに答えよ。

• 区間[L...R]が指定される。A[L..R]を昇順にするには、最少で何回上記移動を行う必要があるか。

解法

数列の1要素を1手でいくらでも左に移動できる。
よって、数列中の各要素について、左側に自身より大きな値がある場合、その要素は移動が必須である。

まずあらかじめ以下を求めておく。
f(n) := A[m]＞A[n]となる、m＜nのうち最大値。なお、そのようなmがない場合は-inf

各クエリの解は、f(L),f(L+1),....,f(R)のうち、L以上の値の個数となる。
これは、区間内における指定された数値以下の値を持つ要素数を求めるSegTreeを使えばO(log^2N)で計算できる。

int N,Q;
int A[202020],pre[202020];

template<class V,int NV> class SegTree_ma {
public:
	vector<V> val;
	static V const def=0;
	V comp(V l,V r){ return max(l,r);};
	
	SegTree_ma(){val=vector<V>(NV*2,def);};
	V getval(int x,int y,int l=0,int r=NV,int k=1) { // x<=i<y
		if(r<=x || y<=l) return def;
		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, V v) {
		entry += NV;
		val[entry]=comp(v,val[entry]); //上書きかチェック
		while(entry>1) entry>>=1, val[entry]=comp(val[entry*2],val[entry*2+1]);
	}
};
SegTree_ma<int,1<<20> st;

template<class V,int NV> class SegTree_1 {
public:
	vector<vector<V>> val;
	static V const def=0;
	V comp(V l,V r){ return max(l,r);};
	
	SegTree_1(){val.resize(NV*2);};
	V getval(int x,int y,V v,int l=0,int r=NV,int k=1) { // x<=i<y
		if(r<=x || y<=l) return 0;
		if(x<=l && r<=y) {
			return lower_bound(ALL(val[k]),v+1)-val[k].begin();
		}
		return getval(x,y,v,l,(l+r)/2,k*2)+getval(x,y,v,(l+r)/2,r,k*2+1);
	}
	void set(int entry,V v) {
		val[entry+NV].clear();
		val[entry+NV].push_back(v);
	}
	void build() {
		for(int i=2*NV-1;i>=NV;i--) sort(ALL(val[i]));
		for(int i=NV-1;i>=1;i--) {
			val[i].clear();
			int a=0,b=0;
			int x=i*2,y=i*2+1;
			while(a<val[x].size() || b<val[y].size()) {
				if(a==val[x].size()) {
					val[i].push_back(val[y][b++]);
				}
				else if(b==val[y].size()) {
					val[i].push_back(val[x][a++]);
				}
				else if(val[x][a]<val[y][b]) {
					val[i].push_back(val[x][a++]);
				}
				else {
					val[i].push_back(val[y][b++]);
				}
			}
		}
	}
};
SegTree_1<int,1<<18> st2;

void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>N>>Q;
	FOR(i,N) {
		cin>>A[i];
		st.update(i,A[i]);
		pre[i]=-1;
		for(j=20;j>=0;j--) if(pre[i]+(1<<j)<=i&&st.getval(pre[i]+(1<<j),i)>=A[i]) pre[i]+=1<<j;
		st2.set(i,pre[i]);
	}
	st2.build();
	while(Q--) {
		int L,R;
		cin>>L>>R;
		L--;
		cout<<(R-L)-st2.getval(L,R,L-1)<<endl;
	}
	
}

まとめ

ShiftというよりRotate？