RMQ(区间最值查询),可以用线段树和ST表解决
#include <iostream> #include <cmath> #include <stdio.h> using namespace std; const int N = 50010; int a[N]; int n,m; int Fmax[N][20]; int Fmin[N][20]; void init() { for(int i=1;i<N;i++)Fmax[i][0]=Fmin[i][0]=a[i]; int k=log2(n); for(int j=1;j<=k;j++) for(int i=1;i<=n-(1<<j)+1;i++) { Fmax[i][j]=max(Fmax[i][j-1],Fmax[i+(1<<j-1)][j-1]); Fmin[i][j]=min(Fmin[i][j-1],Fmin[i+(1<<j-1)][j-1]); } } int RMQ(int l,int r) { int k=log2(r-l+1); int m1=max(Fmax[l][k],Fmax[r-(1<<k)+1][k]); int m2=min(Fmin[l][k],Fmin[r-(1<<k)+1][k]); return m1-m2; } signed main() { cin>>n>>m; for(int i=1;i<=n;i++)scanf("%d",a+i); init(); while(m--) { int l,r; scanf("%d%d",&l,&r); printf("%d\n",RMQ(l,r)); } }
#include <iostream> #include <cmath> #include <stdio.h> using namespace std; const int N = 100010; int a[N],cnt[N]={0}; int n,m; int f[N][20]; int lg2[N]; void init_log() { lg2[0]=-1; for(int i=1;i<N;i++)lg2[i]=lg2[i>>1]+1; } void init_ST() { for(int i=1;i<=n;i++)f[i][0]=cnt[i]; for(int j=1;j<=lg2[n];j++) for(int i=1;i+(1<<j)-1<N;i++) f[i][j]=max(f[i][j-1],f[i+(1<<j-1)][j-1]); } int RMQ(int l,int r) { int k=lg2[r-l+1]; return max(f[l][k],f[r-(1<<k)+1][k]); } void solve() { scanf("%d",&m); for(int i=1;i<=n;i++) { scanf("%d",a+i); if(a[i]!=a[i-1])cnt[i]=1; else cnt[i]=cnt[i-1]+1; } init_ST(); while (m -- ){ int l,r; scanf("%d%d",&l,&r); int t=l; while(a[t]==a[l-1]&&t<=r)t++; if(t>r)printf("%d\n",t-l); else printf("%d\n",max(t-l,RMQ(t,r))); } } signed main() { init_log(); while(cin>>n,n)solve(); }
#include <iostream> using namespace std; const int N = 200010; int f[3][N][20]; char s[N]; signed main() { int n,m; cin>>n>>m; cin>> s+1 ; for(int j=0;j<3;j++) for(int i=1;i<=n;i++) { if(s[i]=='W')f[j][i][0]=1; else if(s[i]=='L') { if(!j)f[j][i][0]=0; else f[j][i][0]=-1; } else f[j][i][0]=0; } //类似于区间DP 初始化ST表 for(int j=1;j<=20;j++) for(int i=1;i+(1<<j)-1<=n;i++) for(int k=0;k<3;k++) f[k][i][j]=f[k][i][j-1]+f[(k+f[k][i][j-1])%3][i+(1<<j-1)][j-1]; // query ST int l,r,x; while(m--) { scanf("%d%d%d",&l,&r,&x); for(int j=20;j>=0;j--) { if(l+(1<<j)-1>r)continue; x+=f[x%3][l][j]; l+=(1<<j); } printf("%d\n",x); } }