RMQ算法,

st表,dp思想

直接上代码吧,

1 #include 
     
       2 #include 
      
        3 #include 
       
         4 #include 
        
          5  6 using namespace std; 7 typedef long long ll; 8 typedef unsigned long long ull; 9 10 #define MAXN 10000111 int stmax[MAXN][21];12 int stmin[MAXN][21];13 int a[MAXN];14 int n,q;15 16 void rmq(int n) {17     for (int j=1; j<20; j++) {18         for (int i=1; i<=n; i++) {19             if (i+(1<
         
          <=n) {20                 stmax[i][j]=max(stmax[i][j-1],stmax[i+(1<<(j-1))][j-1]);21                 stmin[i][j]=min(stmin[i][j-1],stmin[i+(1<<(j-1))][j-1]);22             }23         }24     }25 }26 int ask(int l,int r) {27     int k=log(r-l+1)/log(2);28     int maxans=max(stmax[l][k],stmax[r-(1<
          
           >n>>q;35 for (int i=1;i<=n;i++) {36 cin>>a[i];37 stmax[i][0]=a[i];38 stmin[i][0]=a[i];39 }40 rmq(n);41 for (int i=1,l,r;i<=q;i++) {42 cin>>l>>r;43 ask(l,r);44 }45 46 return 0;47 }
          
         
        
       
      
     

RMQ还有扩展应用,

#include 
     
      #include 
      
       #include 
       
        #include 
        
         #include 
         
          #include 
          
           using namespace std;typedef long long LL;LL mod = 1e9+7;LL cnt;int s[100005],n,q;int sta[100005][20],sto[100005][20];int aska(int l,int r) { int L=r-l+1; int t = log2(L); return sta[l][t] & sta[r-(1<
          
         
        
       
      
     

扩展之后RMQ可以求一个序列一段区间连续按位与,按位或的值

按位与对应区间最小值

按位或对应区间最大值