「LuoguP3865」【模板】ST表（线段树

题目背景

这是一道ST表经典题——静态区间最大值

请注意最大数据时限只有0.8s，数据强度不低，请务必保证你的每次查询复杂度为

题目描述

给定一个长度为

输入输出格式

输入格式：

第一行包含两个整数

第二行包含

接下来

输出格式：

输出包含

输入输出样例

输入样例#1： 复制

8 8
9 3 1 7 5 6 0 8
1 6
1 5
2 7
2 6
1 8
4 8
3 7
1 8

输出样例#1： 复制

说明

对于30%的数据，满足：

对于70%的数据，满足： $1≤N,M≤10^5$

对于100%的数据，满足： $1≤N≤10^5,1≤M≤10^6,ai∈[0,10^9],1≤li≤ri≤N$

 1 /*
 2     qwerta
 3     P3865 【模板】ST表
 4     Accepted
 5     100
 6     代码 C++，0.55KB
 7     提交时间 2018-03-01 16:26:10
 8     耗时/内存
 9     1552ms, 9921KB
10 */
11 #include<cmath>
12 #include<cstdio>
13 #include<iostream>
14 using namespace std;
15 int f[100007][20];
16 int main()
17 {
18     int x,y,m,n,i,j;
19     //scan
20     scanf("%d%d",&n,&m);
21     for(i=1;i<=n;i++)
22     scanf("%d",&f[i][0]);
23     //build
24     for(j=1;(1<<j)<=n;j++)
25     for(i=1;i+(1<<j)-1<=n;i++)
26     f[i][j]=max(f[i][j-1],f[i+(1<<(j-1))][j-1]);
27     //search
28     for(i=1;i<=m;i++)
29     {
30         scanf("%d%d",&x,&y);
31         j=log2(y-x+1);
32         //cout<<x<<" "<<j<<" "<<f[x][j]<<" "<<f[y-(1<<j)+1][j]<<endl;
33         printf("%d
",max(f[x][j],f[y-(1<<j)+1][j]));
34     }
35     return 0;
36 }

然后为了测树剖中间的动态区间最值有没有写错（emmm），把那一段粘过来试了一下

预处理nlogn，修改logn

嗯

 1 /*
 2     qwerta
 3     P3865 【模板】ST表
 4     Accepted
 5     100
 6     代码 C++，1.19KB
 7     提交时间 2018-09-11 16:07:47
 8     耗时/内存
 9     1972ms, 6084KB
10 */
11 #include<cstdio>
12 #include<iostream>
13 using namespace std;
14 const int MAXN=1e5+7;
15 struct qaq{
16     int l,r,v;
17 }a[8*MAXN];
18 int val[MAXN];
19 void build(int i,int ll,int rr)
20 {
21     a[i].l=ll;
22     a[i].r=rr;
23     if(ll==rr){a[i].v=val[ll];return;}
24     int mid=(ll+rr)>>1;
25     build((i<<1),ll,mid);
26     build(((i<<1)|1),mid+1,rr);
27     a[i].v=max(a[(i<<1)].v,a[((i<<1)|1)].v);
28     return;
29 }
30 void add(int i,int x,int k)
31 {
32     if(a[i].l==a[i].r){a[i].v=k;return;}
33     int mid=(a[i].l+a[i].r)>>1;
34     if(x<=mid)add((i<<1),x,k);
35     else add(((i<<1)|1),x,k);
36     a[i].v=max(a[(i<<1)].v,a[((i<<1)|1)].v);
37     return;
38 }
39 int ans;
40 void find(int i,int ll,int rr)
41 {
42     if(a[i].l==ll&&a[i].r==rr){ans=max(ans,a[i].v);return;}
43     int mid=(a[i].l+a[i].r)>>1;
44     if(rr<=mid)find((i<<1),ll,rr);
45     else if(mid+1<=ll)find(((i<<1)|1),ll,rr);
46     else {find((i<<1),ll,mid);find(((i<<1)|1),mid+1,rr);}
47     return;
48 }
49 int main()
50 {
51     //freopen("a.in","r",stdin);
52     int n,m;
53     scanf("%d%d",&n,&m);
54     for(int i=1;i<=n;++i)
55     scanf("%d",&val[i]);
56     build(1,1,n);
57     for(int i=1;i<=m;++i)
58     {
59         int l,r;
60         scanf("%d%d",&l,&r);
61         ans=0;
62         find(1,l,r);
63         printf("%d
",ans);
64     }
65     return 0;
66 }

根本没有慢多少！

「LuoguP3865」 【模板】ST表 （线段树

题目背景

题目描述

输入输出格式

输入输出样例

说明

题解

「LuoguP3865」【模板】ST表（线段树