競技プログラミングをするんだよ

ICPC国内予選突破を目標に一日一問題以上解いていきます。

CodeChef April long Challenge 2015 Chef and Array(FRMQ)

注:この記事はCodeChef終了後に更新しています。
RMQの手法が沢山あることを知ることができた問題です。
空間計算量O(N)の方法もあるらしいですがちょっと難しそうだったのでわかりやすいスパーステーブルに逃げました。

- 問題概要

N個の数字が与えられます
M個の区間クエリに対して区間最大値を出力せよという問題です。(おおざっぱ

- 解法

M個の最大値が10^8なのでクエリに規則性あるかなと思ったのですが思いつかなかったので毎回最大値を求める方針で解きました。
区間最大値といえばパッと思いつくのがSegment Treeです。
これは値の挿入、最大値取り出しがO(\log N)で行えます。しかし最大値取り出しにO(\log N)ということは満点がもらえません。
なんとか最大値取り出しをO(1)で行いたいです。ここでこの問題ではデータ構造の更新が必要ないことに着目します。
SparseTableというデータ構造を使うと事前準備O(N \log N),最大値取り出しO(1)で行うことができます。
しかしこのSparseTable、空間計算量をO(N \logN)必要とするのですがNの最大は10^5なので結構メモリも食います。
メモリをたくさん食うということは配列のアドレス計算のコストもそこそこ必要で、ただでさえ計算量がO(M)=10^8でギリギリなのでなんとか定数時間を削りたいのです。
ていうか実際にTLE多発してます。
定数を削るためにソースコードでは二次元配列のところを一次元に直して手動でアドレス計算したりcinをscanfに変えたりクエリのx,yのMOD計算を引き算に変えたりなど色々試行錯誤して、
最終的に配列の添え字を入れ替えたら間に合うようになりました。ページングとかそのへんの影響だと思いますがよく分かってません。
スパーステーブルの説明は割愛させていただきます。
最上位オンビットの取得にgcc専用関数の__builtin_ctzを使っています。これを使わないときつかった気がします。

- ソースコード

#include<stdio.h>
#define LL long long
void construct_table(int N,int *num,int *left_table,int *right_table){
	int i,j;
	for(i=0;i<N;i++)left_table[i] = right_table[i] = num[i];
	for(i=1;i<17;i++){
		for(j=0;j<N;j++){
			if (j + (1 << i) - 1 < N){
				if(left_table[(j)+((i - 1)<<17)]>left_table[((j + (1 << (i - 1))))+((i - 1)<<17)])
				    left_table[(j)+(i<<17)] =left_table[(j)+((i - 1)<<17)];
				else left_table[(j)+(i<<17)] =left_table[((j + (1 << (i - 1))))+((i - 1)<<17)];
			}
			if (j - (1 << i) + 1 >= 0){
				if(right_table[(j)+((i - 1)<<17)]>right_table[((j - (1 << (i - 1))))+((i - 1)<<17)])
				    right_table[(j)+(i<<17)] =right_table[(j)+((i - 1)<<17)];
				else  right_table[(j)+(i<<17)] =right_table[((j - (1 << (i - 1))))+((i - 1)<<17)];
			}
		}
	}
}
 
int left_table[(100000)+((17)<<17)];
int right_table[(100000)+((17)<<17)];
int main(void){
    int N;
    int num[100000];
    int l,r,_x, _y, x, y,M,i;
	LL res = 0;
	scanf("%d", &N);
	for(i=0;i<N;i++)scanf("%d", &num[i]);
	construct_table(N,num,left_table,right_table);//construct_tree();
 
	scanf("%d %d %d", &M, &x, &y);
	if(N<20)
	while (M--){
		if(x>y)_x=y,_y=x;
		else _x=x,_y=y;
		l=left_table[(_x)+((32-__builtin_clz(_y - _x)-1)<<17)];
		r=right_table[(_y)+((32-__builtin_clz(_y - _x)-1)<<17)];
		if(l>r)
			res+=l;
			else
			res+=r;		
		x = (x + 7) % (N - 1);
		y = (y + 11) % (N);
	}
	else
	while (M--){
		if(x>y)_x=y,_y=x;
		else _x=x,_y=y;
		//res += max(left_table[_x][bitsize[_y - _x]], right_table[_y][bitsize[_y - _x]]);
		l=left_table[(_x)+((32-__builtin_clz(_y - _x)-1)<<17)];
		r=right_table[(_y)+((32-__builtin_clz(_y - _x)-1)<<17)];
		
		res+=(l>r?l:r);	
		x +=7;
		y +=11;
		if(x>=N-1)x-=(N-1);
		if(y>=N)y-=N;
	}
	printf("%lld\n",res);
	return 0;
}