RMQ可用于區(qū)間求最大值或區(qū)間求最小值。

2個(gè)數(shù)組，一個(gè)為a[i],即所給數(shù)列，一個(gè)為dp[i][j],為區(qū)間最值。

init：

dp[i][j]代表，以i為起點(diǎn)，長度為（1<<j）數(shù)列的最值。

for(int i=1;i<=n;i++) {dp[i][0]=a[i];lg[i]=lg[i/2]+1;///lg[i]相當(dāng)與2的lg[i]次方為i;也可以試試log(); } for(int j=1;(1<<j)<=n;j++) ///for(int i=1;i<=n;i++){if(i+(1<<j-1)>n) break;dp[i][j]=min(dp[i][j-1],dp[i+(1<<j-1)][j-1]);///比較dp[i][j-1],dp[i+(1<<j-1)][j-1]的最值，一半一半的查找。///查詢以i為起點(diǎn),(1<<j)長度的最小值，即區(qū)間[i,i+(j<<1)]的最值。}

query：

查詢區(qū)間最值

int RMQ(int l,int r) {int k=lg[r-l+1];return min(dp[l][k],dp[r-(1<<k)+1][k]);///別忘了要加1 }

csu1809：把"("看為1,")"看為-1，原來括號(hào)是匹配的，if(s[l]==s[r])沒變化，if(s[l]==')'&&s[r]=='(')不改變。

當(dāng)s[l]=='(',s[r]==')',這個(gè)交換時(shí)，[l,r]區(qū)間的和減了2，所以只要區(qū)間最小大于等于2即可。

#include<iostream> #include<cstdio> #define maxn 100010 using namespace std; int dp[maxn][20],lg[maxn]; char s[maxn]; int RMQ(int l,int r) {int k=lg[r-l+1];return min(dp[l][k],dp[r-(1<<k)+1][k]);///attention } int main() {int n,m;while(scanf("%d%d",&n,&m)!=EOF){scanf("%s",s+1);int x=0;lg[0]=-1;for(int i=1;i<=n;i++){if(s[i]=='(') x++;else x--;dp[i][0]=x;lg[i]=lg[i/2]+1;}for(int j=1;(1<<j)<=n;j++)for(int i=1;i<=n;i++){if(i+(1<<j-1)>n) break;dp[i][j]=min(dp[i][j-1],dp[i+(1<<j-1)][j-1]);}while(m--){int l,r;scanf("%d%d",&l,&r);if(l>r) swap(l,r);if(s[l]==s[r]||s[l]==')'){printf("Yes\n");continue;}if(RMQ(l,r-1)<2) printf("No\n");///這里求區(qū)間[l,r-1]，若是求[l,r]和還是不變的else printf("Yes\n");}}return 0; }

?

總結(jié)

以上是生活随笔為你收集整理的RMQ---csu1809的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。