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; }
難しや。