#include<iostream> #include<cmath> #include<cstdio> #include<cstdlib> #define maxn 100010 #define maxm 2000010 using namespace std; template<typename T> inline void read(T &x){ x=0; bool flag=0; char c=getchar(); for(;!isdigit(c);c=getchar()) if(c=='-') flag=1; for(;isdigit(c);c=getchar()) x=x*10+(c^48); if(flag) x=-x; } int n,m,a[maxn],l,r,f[maxn][20]; int len,c,ans; inline void ST(){ for(int i=1;i<=n;i++) f[i][0]=a[i]; for(int j=1;j<=19;j++){//相当于区间DP，注意j一定要在i外面 for(int i=1;i+(1<<j)-1<=n;i++){//范围为[i,i+(2^j)-1],所以保证i+(2^j)-1<=n不越界 f[i][j]=max(f[i][j-1],f[i+(1<<(j-1))][j-1]); } } } int main(){ read(n);read(m); for(int i=1;i<=n;i++) read(a[i]); ST(); for(int i=1;i<=m;i++) { read(l),read(r); len=r-l+1; c=log2(len);//满足2^c<=len的最大的c,把原区间拆成[l,l+2^c-1]and[r-(2^c)+1,r]这两段区间 ans=max(f[l][c],f[r-(1<<c)+1][c]); cout<<ans<<endl; } return 0; }
区间最值问题，预处理O(nlogn),以O(1)的时间复杂度在线回答“区间[l,r]之间的数的最大值是多少”
因为[l,l+2^c-1]和[r-(2^c)+1,r]有交集，所以ans的计算不会漏东西(有交集不影响结果，只要不会少算某一部分就好了)
·“有交集”的证明：
∵2^c<=len
∴2^(c+1)>len
∴2^(c+1)-1>=len
∴[l,l+2^c-1]和[r-(2^c)+1,r]有交集，证毕
被洛谷P3865卡常卡死了qaq
贴一个爆改n遍终于过了的惨不忍睹的代码：
#include<iostream> #include<cmath> #include<cstdio> #include<cstdlib> #define maxn 100010 #define maxm 2000010 using namespace std; inline int read(void) { int x=0,f=1;char ch=getchar(); while (!isdigit(ch)){if (ch=='-') f=-1;ch=getchar();} while (isdigit(ch)){x=x*10+ch-48;ch=getchar();} return x*f; } int n,m,a[maxn],l,r,f[20][maxn]; int len,c,ans; //inline void ST(){ // for(int i=1;i<=n;i++) f[i][0]=a[i]; // for(int j=1;j<=19;j++){//相当于区间DP，注意j一定要在i外面 // for(int i=1;i+(1<<j)-1<=n;i++){//范围为[i,i+(2^j)-1],所以保证i+(2^j)-1<=n不越界 // f[i][j]=max(f[i][j-1],f[i+(1<<(j-1))][j-1]); // } // } //} int main(){ n=read();m=read(); for(int i=1;i<=n;i++) a[i]=read(); // ST(); for(int i=1;i<=n;i++) f[0][i]=a[i]; for(int j=1;j<=17;j++){//相当于区间DP，注意j一定要在i外面 for(int i=1;i+(1<<j)-1<=n;i++){//范围为[i,i+(2^j)-1],所以保证i+(2^j)-1<=n不越界 f[j][i]=max(f[j-1][i],f[j-1][i+(1<<(j-1))]); } } for(int i=1;i<=m;i++) { l=read(),r=read(); // len=r-l+1; c=log2(r-l+1);//满足2^c<=len的最大的c,把原区间拆成[l,l+2^c-1]and[r-(2^c)+1,r]这两段区间 // ans=max(f[l][c],f[r-(1<<c)+1][c]); printf("%d ",max(f[c][l],f[c][r-(1<<c)+1])); } return 0; }
·upd：卡常小技巧：论怎样从4.91s->886ms
1.不要cin/cout!!!输入输出很多的时候用时能翻好几倍!!!切记快读+printf!!!
2.f的两维换一下也能快很多，比如这样：f[maxn][20]->f[20][maxn](亲测有效）
原理大概这样：
访问内存是连续的。