kmjp's blog

競技プログラミング参加記です

Codeforces ECR #033: F. Subtree Minimum Query

Eと比べこちらは実装重め。
http://codeforces.com/contest/893/problem/F

問題

N頂点の根付き木が与えられる。
各頂点には整数値が振られている。

この木に関し以下のM個のクエリに答えよ。
クエリは頂点XとパラメータKで設定される。
XのSubTree内でXからの距離がK以下の頂点のうち、振られた整数値の最小値を求めよ。

解法

RMQとダブリングで解く。
まず、各頂点についてダブリングの要領でSubTree内における自身から距離2^0、2^1、2^2、…以内の頂点の値の最小値を求めよう。

各クエリに関して複数のKが2の累乗のクエリに分解して解く。
例えばK=10=1010bだとする。
まずXからは距離8以内の頂点に関して、先のダブリングの結果を用いて最小値を得る。
あとは距離9,10の対処だが、Xから距離8の頂点群に対し、それぞれさらに距離2の範囲の最小値を求め、その全体の最小値を求めればよい。

このためには、Xから距離8の頂点群に対しRMQを求められるようにデータ構造を組んでおく必要がある。
これは幅優先探索で頂点にIDを振っていくと、対象の頂点群が連番になるのでRMQが適用できるようになる。
また、EulerTour順のIDも別途保持しておくと、RMQにおける探索範囲も高速に求められる。

RMQをSegTreeで処理する場合、各クエリに関し、RMQをlog(K)回行うのと、その都度EulerTourからの探索範囲検索とRMQがいずれもO(logN)かかる。
ダブリングがO(NlogN)、RMQ構築がO(Nlog^2N)、クエリ処理がO(MlogKlogN)かな。

int N,root,M;
int A[101010];
int X,K;

template<class V,int NV> class SegTree_1 {
public:
	vector<V> val;
	static V const def=1<<30;
	V comp(V l,V r){ return min(l,r);};
	
	SegTree_1(){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]=v;
		while(entry>1) entry>>=1, val[entry]=comp(val[entry*2],val[entry*2+1]);
	}
};

SegTree_1<int,1<<18> dst[21];

int id=1;
int D[101010];
int L[101010];
int R[101010];
int P[20][101010];

int dmi[20][101010];
int ID[101010];
int rev[101010];
vector<pair<int,int>> V[201010];
vector<int> E[101010];

void dfs(int cur,int pre,int d) {
	P[0][cur]=pre;
	if(pre==-1) P[0][cur]=cur;
	D[cur]=d;
	rev[id]=cur;
	L[cur]=id;
	V[d].push_back({id,0});
	id++;
	
	FORR(e,E[cur]) if(e!=pre) dfs(e,cur,d+1);
	
	R[cur]=id;
}

void solve() {
	int i,j,k,l,r,x,y; string s;
	
	scanf("%d%d",&N,&root);
	root--;
	FOR(i,N) {
		scanf("%d",&A[i]);
		FOR(j,20) dmi[j][i]=A[i];
	}
	FOR(i,N-1) {
		scanf("%d%d",&x,&y);
		E[x-1].push_back(y-1);
		E[y-1].push_back(x-1);
	}
	
	dfs(root,-1,0);
	id=1;
	FOR(i,N+1) {
		FORR(v,V[i]) ID[rev[v.first]]=v.second=id++;
	}
	FOR(j,N) {
		dmi[0][P[0][j]]=min(dmi[0][P[0][j]],A[j]);
	}
	FOR(i,19) {
		FOR(j,N) {
			P[i+1][j]=P[i][P[i][j]];
			dmi[i+1][j]=min(dmi[i+1][j],dmi[i][j]);
			dmi[i+1][P[i][j]]=min(dmi[i+1][P[i][j]],dmi[i][j]);
		}
		FOR(j,N) dst[i].update(ID[j],dmi[i][j]);
	}
	
	
	int ret=0;
	scanf("%d",&M);
	while(M--) {
		scanf("%d%d",&X,&K);
		X=(X+ret)%N;
		K=(K+ret)%N;
		
		ret=A[X];
		int TL=L[X],TR=R[X];
		int dep=D[X];
		for(j=18;j>=0;j--) if(K&(1<<j)) {
			auto it=lower_bound(ALL(V[dep]),make_pair(L[X],0));
			auto it2=lower_bound(ALL(V[dep]),make_pair(R[X],0));
			if(it!=it2) {
				it2--;
				x=it->second;
				y=it2->second+1;
				ret=min(ret,dst[j].getval(x,y));
			}
			dep+=1<<j;
		}
		_P("%d\n",ret);
	}
}

まとめ

実装はともかく、わかってしまえばアイデアはそれほど複雑ではない。