luogu 3865 【模板】ST表-白红宇

luogu 3865 【模板】ST表

阅读量：4668 次

发布时间：2019-06-09

本文共 1037 字，大约阅读时间需要 3 分钟。

我太菜了

今天才学会现场脑补ST表静态RMQ

1 #include
      
        2 #include
       
         3 #include
        
          4 #include
         
           5 #include
          
            6 #include
           
             7 #include
            
              8 #include
              9 #include
              
               10 #define ll long long11 #define inf 214748361112 #define MAXN 10101013 #define MOD 100000014 using namespace std;15 inline int read()16 {17 int x=0,f=1;char ch=getchar();18 while(!isdigit(ch)) { if(ch=='-') f=-1;ch=getchar();}19 while(isdigit(ch)) {x=x*10+ch-'0';ch=getchar();}20 return x*f;21 }22 int n,Q,f[MAXN][22];23 int main()24 {25 n=read(),Q=read();26 for(int i=1;i<=n;i++) f[i][0]=read();27 for(int i=1;i<=20;i++)28 for(int j=1;j<=n;j++)29 {30 if((1<
               
                n+1) break;31 f[j][i]=max(f[j][i-1],f[j+(1<<(i-1))][i-1]);32 }33 /*for(int i=1;i<=n;i++)34 for(int j=0;j<=16;j++) printf("%d %d %d\n",i,j,f[i][j]);*/35 int a,b,t,k;36 while(Q--)37 {38 a=read(),b=read();t=b-a+1;39 for(int i=20;i>=0;i--)40 if(t&(1<