最后的散块不能和整块扔一起吧。
by _LiMLE_ @ 2022-08-19 18:25:58
写这么复杂还不如直接用 ST 表
by 幸存者 @ 2022-08-19 18:38:12
@[幸存者](/user/549357) 我st表已经过了...只是刚学分块想练一下
by TempestJueMu @ 2022-08-19 18:45:53
```cpp
#include<cstdio>
#include<bits/stdc++.h>
#include<cmath>
using namespace std;
int n,m,bl,idj,idk;
int a[100001];
int st[318],ed[318],bel[100001],siz[318];
int s1[318][318],s2[318][318],s3[318][318],s4[318][317*317+2];
int mp[318][318],tot=1;
inline int read()
{
int x=0,f=1;char ch=getchar();
while (ch<'0'||ch>'9'){if (ch=='-') f=-1;ch=getchar();}
while (ch>='0'&&ch<='9'){x=x*10+ch-48;ch=getchar();}
return x*f;
}
inline int max(int a,int b){return a>b?a:b;}
void init()
{
for(int i=1;i<=1000;i++){
if(i*i>=n){
bl=i;
break;
}
}
for(int i=0;i<=bl;++i)
for(int j=0;j<=bl;++j)
mp[i][j]=tot++;
for(int i=1;i<=n;i++){
bel[i]=((i-1)/(bl-1)+1);
ed[bel[i]]=i;
// cout<<i<<" "<<bel[i]<<endl;
}
for(int i=n;i>=1;i--){
st[bel[i]]=i;
siz[bel[i]]++;
}
ed[bl]=n;
// for(int j=st[bl];j<=ed[bl];++j)bel[j]=bl;
for(int i=1;i<=bl;++i)
{
for(int j=st[i];j<=ed[i];++j)
{
idj=j%siz[i];
s1[i][idj]=max(a[j],s1[i][idj-1>=0?idj-1:idj-1+siz[i]]);
}
for(int j=ed[i];j>=st[i];--j)
{
idj=j%siz[i];
// cout<<a[j]<<endl;
s2[i][idj]=max(a[j],s2[i][idj+1<siz[i]?idj+1:idj+1-siz[i]]);
// cout<<i<<" "<<j<<" "<<idj<<" "<<s2[i][idj]<<endl;
}
}
for(int i=1;i<=bl;++i)
for(int j=i;j<=bl;++j)
s3[i][j]=max(s3[i][j-1],s1[j][ed[j]%(siz[j])]);
for(int i=1;i<=bl;++i)
for(int j=st[i];j<=ed[i];++j)
{
idj=j%siz[i];
for(int k=j;k<=ed[i];++k)
{
idk=k%siz[i];
s4[i][mp[idj][idk]]=max(s4[i][mp[idj][idk-1>=0?idk-1:idk-1+siz[i]]],a[k]);
}
}
}
int query(int l,int r)
{
if(bel[l]==bel[r])return s4[bel[l]][mp[l%siz[bel[l]]][r%siz[bel[l]]]];
int ans=0;
ans=max(ans,s2[bel[l]][l%siz[bel[l]]]);
// cout<<ans<<endl;
ans=max(ans,s1[bel[r]][r%siz[bel[r]]]);
// cout<<ans<<endl;
ans=max(ans,s3[bel[l]+1][bel[r]-1]);
// cout<<ans<<endl;
return ans;
}
int main()
{
scanf("%d%d",&n,&m);
for(int i=1;i<=n;++i)
a[i]=read();
init();
for(int i=1,l,r;i<=m;++i)
l=read(),r=read(),printf("%d\n",query(l,r));
return 0;
}
```
AC了，主要问题就是你的最后一块散块不能扔整块里。
然后数组卡一下
by _LiMLE_ @ 2022-08-19 19:08:51
@[_LiMLE_](/user/480934) tql orz
by TempestJueMu @ 2022-08-19 19:09:51
sto \_LiMLE\_ ors
by 寻逍遥2006 @ 2022-08-19 19:09:57