はなたの日記

プログラミング(C言語)の勉強をしています。超初心者です。

DSL_2_D Range Update Query (RUQ)

問題
Range Update Query (RUQ) | Aizu Online Judge

RUQです。以前このDSLの問題を何問か解きましたが、その時に参考にしたサイトを再び参考にしました。
kujira16.hateblo.jp
分かり易すぎますね。独学者には非常にありがたいです。

findは簡単に実装できたのですが、updateでやや手こずりました。

else {/*update*/
	scanf("%d %d %d",&x,&y,&z);
	if(lazy[x/b]!=-1)update(x/b);
	for(i=x;i<=(x/b+1)*b-1;i++)a[i]=z;
		
	for(i=x/b+1;i<y/b;i++)lazy[i]=z;
		
	if(lazy[y/b]!=-1)update(y/b);
	for(i=y/b*b;i<=y;i++)a[i]=z;
}

(上のupdateという関数はlazyの内容を伝搬する関数のことです)
a[x]からa[y]をzにアップデートする時、updateの範囲が広いときは上の感じでもよさそうなのですが
a[x]とa[y]が同じバケットにいるときに不都合が起きてしまいます。

else {/*update*/
	scanf("%d %d %d",&x,&y,&z);
	if(lazy[x/b]!=-1)update(x/b);
	for(i=x;i<=MIN(y,(x/b+1)*b-1);i++)a[i]=z;
		
	for(i=x/b+1;i<y/b;i++)lazy[i]=z;
		
	if(lazy[y/b]!=-1)update(y/b);
	for(i=MAX(x,y/b*b);i<=y;i++)a[i]=z;
}

1番目と3番目のforを工夫しました。
1番目のforは、右端をMIN(y,(x/b+1)*b-1)とすることで、xとyが同じバケットの時は右端がyになります。
3番目のforは、スタートをMAX(x,y/b*b)とすることで、xとyが同じバケットの時はスタートがxになります。

#include<stdio.h>
#include<math.h>
#include<limits.h>
#define MIN(a, b) ((a) < (b) ? (a) : (b))
#define MAX(a, b) ((a) > (b) ? (a) : (b))
#define LARGE 100001

int a[LARGE];
int lazy[LARGE];
int b,n;

void update(int x){

	for(int i=x*b;i<=MIN(n-1,(x+1)*b-1);i++){
		a[i]=lazy[x];
	}
	lazy[x]=-1;
	
	return;
}

int main(){

	int q,i,j,com;
	int x,y,z;
	
	scanf("%d %d",&n,&q);
	
	b=sqrt(n);
	
	for(i=0;i<n;i++){
		a[i]=INT_MAX;
		lazy[i]=-1;
	}
	
	for(j=0;j<q;j++){
	
		scanf("%d",&com);
		
		if(com==1){/*find*/
			scanf("%d",&x);
			if(lazy[x/b]!=-1)update(x/b);
			printf("%d\n",a[x]);
		}
		
		else {/*update*/
			scanf("%d %d %d",&x,&y,&z);
			if(lazy[x/b]!=-1)update(x/b);
			for(i=x;i<=MIN(y,(x/b+1)*b-1);i++)a[i]=z;
			
			for(i=x/b+1;i<y/b;i++)lazy[i]=z;
			
			if(lazy[y/b]!=-1)update(y/b);
			for(i=MAX(x,y/b*b);i<=y;i++)a[i]=z;
		}
		
	}
	
	return 0;
	
}

難しや。