はなたの日記

ギターのコードについて書きます

DSL_2_A Range Minimum Query (RMQ)

C

問題
Range Minimum Query (RMQ) | データ構造ライブラリ | Aizu Online Judge

一度解いたことがあるのですが、その時はめっちゃふつーにやって解けてしまった気がする。
今回は平方分割？というやり方でやってみた。参考にしたのは前回のと同じ。

www.slideshare.net

平方分割は非常に考えが分かり易く、「これならすぐできるっしょ！」と思って実装してみたのですが、かなりミスをしてしまい、時間がかかりました。

#include<stdio.h>
#include<math.h>
#include<limits.h>
#define MAX 100000


int min(int a,int b){
 if(a < b)return a;
 return b;
}


int main(){
 int n,q,i,com,j,mini;
 int x,y;
 int A[MAX];
 int B[MAX];
 int b,L,R;

 scanf("%d %d",&n,&q);
 b=floor(sqrt(n));

 for(i=0;i<n;i++){
   A[i]=INT_MAX;
   B[i]=INT_MAX;
 }


 for(i=0;i<q;i++){

   scanf("%d %d %d",&com,&x,&y);

   if(com==0){/*update*/
     A[x]=y;
     mini=A[(x/b)*b];
     R=min((x/b+1)*b-1,n-1);
     for(j=(x/b)*b+1;j<=R;j++)mini=min(mini,A[j]);
     B[x/b]=mini;

   }

   else if(com==1){/*find*/
     if(x==y)printf("%d\n",A[x]);

     else{
       L=x/b; R=y/b; mini=INT_MAX;
       if(L==R){
         for(j=x;j<=y;j++)mini=min(mini,A[j]);
         printf("%d\n",mini);
       }else{
         for(j=x;j<(L+1)*b;j++)mini=min(mini,A[j]);
         for(j=L+1;j<R;j++)mini=min(mini,B[j]);
         for(j=R*b;j<=y;j++)mini=min(mini,A[j]);
         printf("%d\n",mini);
       }
     }

   }

 }

return 0;
}

updateの方はバケットの更新で、n-1より大きい値（配列の外）も考慮してしまった。
findはL==R（左端と右端が同じバケットにある時）の場合分けを忘れていた。

まだまだ勉強する必要があるなあと思った。