yukicoder : No.3059 Range Tournament

落ち着いて解けば解けたな…。
https://yukicoder.me/problems/no/3059

問題

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

• 順列Pの部分列が指定される。この数列をQとする。
• Qの先頭2要素を比較し、小さい方を取り除いて大きい方を末尾に回す。この処理を|Q|=1になるまで繰り返す。

全クエリを処理したとき、各整数値に対し、末尾に回された回数の総和を求めよ。

解法

|Q|が2の累乗であれば、このクエリはトーナメント表で各人の勝利回数を数えるのと同じである。
これを拡張して|Q|が2の累乗でない場合を考える。

f(n,d,L) := Pのうちn番から始まって連続するL*(2^d)人のうち、d回勝利したLの人の並び
とする。この状態でトーナメントを進めるとどうなるかを考える。

• Lが偶数の場合、f(n,d+1,L/2)が残る。
• Lが奇数の場合、f(n+floor(L/2)*2,d,1)の後に、f(n,d+1,floor(L/2))が続く

後者の場合、f(n+floor(L/2)*2^(d+1),d,1)とf(n,d+1,1)の対戦結果を考え、f(n+2^(d+1),floor(L/2)-1)の後にその勝者が続く
と考えると、Qの状態は高々2つのf(*,*,*)の並びで表現できる。
あとは累積和を使い、d回戦での勝利回数をそれぞれ数え上げればよい。

int N;
int P[202020];
int S[20][1202020];
ll cnt[202020];
template<class V,int NV> class RMQ {
private:
	V table[NV+1][1<<NV];
	int LG[1<<NV];
	int NV2;
public:
	static V const def=-(1<<30);
	V comp(V l,V r){ return max(l,r);};
	RMQ() {
		int i,x;
		NV2=1<<NV;
		LG[1]=0;
		for(i=2;i<NV2;i++) LG[i]=LG[i/2]+1;
		FOR(i,NV) FOR(x,NV2) table[i][x]=def;
	}
	void set(int x,V v){ table[0][x]=v;}
	void build(int MV=-1) { //MVはサイズ指定
		if(MV==-1) MV=NV2;
		int i,j,x,y;
		FOR(i,NV) FOR(x,MV) table[i+1][x]=comp(table[i][x],(x+(1<<i)<MV)?table[i][x+(1<<i)]:def);
	}
	V query(int L,int R) { //[L,R),
		L=max(0,L), R=min(R,NV2);
		if(R<=L) return def;
		int WL=LG[R-L];
		return comp(table[WL][L],table[WL][R-(1<<WL)]);
	}
	
};

RMQ<int,18> rmq;
int Q;

void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>N;
	FOR(i,N) {
		cin>>P[i];
		rmq.set(i,P[i]);
	}
	rmq.build(N);
	
	cin>>Q;
	while(Q--) {
		cin>>x>>y;
		deque<array<int,3>> D;
		D.push_back({x-1,y-x+1,0});
		while(D.size()) {
			auto p=D.front();
			D.pop_front();
			int len=p[1];
			int lv=p[2];
			if((len>>lv)>1) {
				
				S[lv][p[0]]++;
				x=((len>>(lv+1))<<(lv+1));
				S[lv][p[0]+x]--;
				if((len>>lv)%2) {
					D.push_front({p[0]+x,1<<lv,lv});
				}
				D.push_back({p[0],x,lv+1});
				continue;
			}
			if(D.empty()) break;
			auto q=D.front();
			D.pop_front();
			int len2=q[1];
			int lv2=q[2];
			if(len2>>lv2>1) {
				D.push_front({q[0]+(1<<lv2),len2-(1<<lv2),lv2});
			}
			q[1]=1<<lv2;
			x=rmq.query(p[0],p[0]+(1<<lv));
			y=rmq.query(q[0],q[0]+(1<<lv2));
			if(x>y) {
				cnt[x]++;
				D.push_back(p);
			}
			else {
				cnt[y]++;
				D.push_back(q);
			}
		}
	}
	
	FOR(i,19) {
		FOR(j,N) if(S[i][j]) {
			S[i][j+(2<<i)]+=S[i][j];
			x=rmq.query(j,j+(2<<i));
			cnt[x]+=S[i][j];
		}
	}
	FOR(i,N) cout<<cnt[i+1]<<endl;
}

まとめ

トーナメント表に関するこの考え方のテクは覚えておこう…。