ST表

这是一种神奇的数据结构，用nlogn的空间与nlongn的预处理得出O(1)的区间最大最小值(无修)

那么来看看这个核心数组：ST[][]

ST[i][j]表示从i到i+(1<<j)的范围内的最大/最小值

那么来看看代码吧。

1 #include 
      
        2 #include 
       
         3 using namespace std; 4 int ST[100010][21],n; 5 void makeST() 6 { 7     for(int j=1;j<=20;j++) 8     { 9         for(int i=1;i+(1<
        
         <=n;i++)  ST[i][j]=min(ST[i][j-1],ST[i+(1<<(j-1))][j-1]);10     }11     return;12 }13 int getpow(int x)14 {15    int ans=0;16    while((1<
         
          <=x) ans++;17    return ans-1;18 }19 int main()20 {21     int m;22     scanf("%d%d",&n,&m);23     for(int i=1;i<=n;i++)24     {25         scanf("%d",&ST[i][0]);26     }27     makeST();28     int x,y;29     while(m--)30     {31         scanf("%d%d",&x,&y);32         int t=getpow(y-x+1);33         printf("%d ",min(ST[x][t],ST[y-(1<

P1816 忠诚

1 #include 
       
         2 #include 
        
          3 using namespace std; 4 int ST[100010][21],n; 5 void makeST() 6 { 7     for(int j=1;j<=20;j++) 8     { 9         for(int i=1;i+(1<
         
          <=n;i++)  ST[i][j]=max(ST[i][j-1],ST[i+(1<<(j-1))][j-1]);10     }11     return;12 }13 int getpow(int x)14 {15    int ans=0;16    while((1<
          
           <=x) ans++;17    return ans-1;18 }19 int main()20 {21     int m;22     scanf("%d%d",&n,&m);23     for(int i=1;i<=n;i++)24     {25         scanf("%d",&ST[i][0]);26     }27     makeST();28     int x,y;29 30     while(m--)31     {32         scanf("%d%d",&x,&y);33         int t=getpow(y-x+1);34         printf("%d\n",max(ST[x][t],ST[y-(1<