admin 管理员组

文章数量: 887017

RMQ

RMQ可用于区间求最大值或区间求最小值。

2个数组，一个为a[i],即所给数列，一个为dp[i][j],为区间最值。

init：

dp[i][j]代表，以i为起点，长度为（1<<j）数列的最值。

for(int i=1;i<=n;i++)
{dp[i][0]=a[i];lg[i]=lg[i/2]+1;///lg[i]相当与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为起点,(1<<j)长度的最小值，即区间[i,i+(j<<1)]的最值。}

query：

查询区间最值

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，原来括号是匹配的，if(s[l]==s[r])没变化，if(s[l]==')'&&s[r]=='(')不改变。

当s[l]=='(',s[r]==')',这个交换时，[l,r]区间的和减了2，所以只要区间最小大于等于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");///这里求区间[l,r-1]，若是求[l,r]和还是不变的else printf("Yes\n");}}return 0;
}

 

本文标签： RMQ

版权声明：本文标题：RMQ 内容由网友自发贡献，该文观点仅代表作者本人， 转载请联系作者并注明出处：http://www.freenas.com.cn/jishu/1688399730h215360.html， 本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如发现本站有涉嫌抄袭侵权/违法违规的内容，一经查实，本站将立刻删除。