竹子听

3月29日 自己的模板RMQ

#include<cstdio>

#include<cstring>

int n,s[1000][4],word[1000],N;

int Log(int x)

{

int c=1;

while(x!=1) x=x>>1,c++;

return c;

}

int max(int x,int y)

{

if(x>=y) return x;

else return y;

}

int main()

{

scanf("%d",&n),N=Log(n);

memset(s,0,sizeof(int));

memset(word,0,sizeof(int));

for(int i=1;i<=n;i++)  scanf("%d",&word[i]);

for(int i=1;i<=n;i++)  s[i][0]=word[i];

//这里调了很久的原因就是为了调试方便把数组开小了，刚刚超了一位，所以最后一位没有清零

for(int j=1;j<=N;j++)

for(int i=1;i<=n;i++)

if(i+(1<<j)-1<=n)//这里很迷的就是不大括号就会出错，这是什么鬼优先级啊

s[i][j]=max(s[i][j-1],s[i+(1<<(j-1))][j-1]);//式子写对了但切记要打括号

//查询的时候用循环比较方便，先把二进制的表打好了，因为一定是递减的，在循环里面从大往小的减，注意很可能出错的地方就是衔接的地方要记得加减1，然后取最大就Ok了

}