题目背景
这是一道ST表经典题——静态区间最大值
请注意最大数据时限只有0.8s，数据强度不低，请务必保证你的每次查询复杂度为 O(1)
题目描述
给定一个长度为 N 的数列，和 M 次询问，求出每一次询问的区间内数字的最大值。
输入输出格式
输入格式：
第一行包含两个整数 N,M，分别表示数列的长度和询问的个数。
第二行包含 N 个整数（记为 ai ），依次表示数列的第 i 项。
接下来 M 行，每行包含两个整数 li,ri，表示查询的区间为 [li,ri]
输出格式：
输出包含 M行，每行一个整数，依次表示每一次询问的结果。
输入输出样例
说明
对于30%的数据，满足： 1≤N,M≤10
对于70%的数据，满足： 1≤N,M≤10^5
对于100%的数据，满足： 1≤N≤10^5,1≤M≤10^6,ai∈[0,10^9],1≤li≤ri≤N
题解
这道题在遥远的远古写过ST
/*
qwerta
P3865 【模板】ST表
Accepted
100
代码 C++，0.55KB
提交时间 2018-03-01 16:26:10
耗时/内存
1552ms, 9921KB
*/
#include<cmath>
#include<cstdio>
#include<iostream>
using namespace std;
int f[][];
int main()
{
int x,y,m,n,i,j;
//scan
scanf("%d%d",&n,&m);
for(i=;i<=n;i++)
scanf("%d",&f[i][]);
//build
for(j=;(<<j)<=n;j++)
for(i=;i+(<<j)-<=n;i++)
f[i][j]=max(f[i][j-],f[i+(<<(j-))][j-]);
//search
for(i=;i<=m;i++)
{
scanf("%d%d",&x,&y);
j=log2(y-x+);
//cout<<x<<" "<<j<<" "<<f[x][j]<<" "<<f[y-(1<<j)+1][j]<<endl;
printf("%d\n",max(f[x][j],f[y-(<<j)+][j]));
}
return ;
}
然后为了测树剖中间的动态区间最值有没有写错（emmm），把那一段粘过来试了一下
预处理nlogn，修改logn
嗯
/*
qwerta
P3865 【模板】ST表
Accepted
100
代码 C++，1.19KB
提交时间 2018-09-11 16:07:47
耗时/内存
1972ms, 6084KB
*/
#include<cstdio>
#include<iostream>
using namespace std;
const int MAXN=1e5+;
struct qaq{
int l,r,v;
}a[*MAXN];
int val[MAXN];
void build(int i,int ll,int rr)
{
a[i].l=ll;
a[i].r=rr;
if(ll==rr){a[i].v=val[ll];return;}
int mid=(ll+rr)>>;
build((i<<),ll,mid);
build(((i<<)|),mid+,rr);
a[i].v=max(a[(i<<)].v,a[((i<<)|)].v);
return;
}
void add(int i,int x,int k)
{
if(a[i].l==a[i].r){a[i].v=k;return;}
int mid=(a[i].l+a[i].r)>>;
if(x<=mid)add((i<<),x,k);
else add(((i<<)|),x,k);
a[i].v=max(a[(i<<)].v,a[((i<<)|)].v);
return;
}
int ans;
void find(int i,int ll,int rr)
{
if(a[i].l==ll&&a[i].r==rr){ans=max(ans,a[i].v);return;}
int mid=(a[i].l+a[i].r)>>;
if(rr<=mid)find((i<<),ll,rr);
else if(mid+<=ll)find(((i<<)|),ll,rr);
else {find((i<<),ll,mid);find(((i<<)|),mid+,rr);}
return;
}
int main()
{
//freopen("a.in","r",stdin);
int n,m;
scanf("%d%d",&n,&m);
for(int i=;i<=n;++i)
scanf("%d",&val[i]);
build(,,n);
for(int i=;i<=m;++i)
{
int l,r;
scanf("%d%d",&l,&r);
ans=;
find(,l,r);
printf("%d\n",ans);
}
return ;
}
根本没有慢多少！