st表
通常的思维上每次求区域l,r中的最大值都需要遍历一下这个区间[l,r],时间复杂度是o(N); 然后N次询问就会达到O(N^2)的时间复杂度。 ST表的作用就是用NlogN的时间预处理之后,每次查询都是O(1)的时间复杂度就可以将区间最值表示出来 1.预处理
int f[N][25];
void pre()
{
for(int i = 1; i <= n; i++)
f[i][0] = a[i];
int t = log(n) / log(2) + 1;
for(int i = 1; i < t; i++)
for(int j = 1; j <= n - (1 << i) + 1; j++)
f[j][i] = max(f[j][i-1],f[j+(1<<(i-1))][i-1]);
}
2查询
int ask(int l, int r)
{
int k = log2(r - l + 1);
return max(f[l][k], f[r - (1 << k) + 1][k]);
}
题目背景
这是一道 ST 表经典题——静态区间最大值
请注意最大数据时限只有 0.8s,数据强度不低,请务必保证你的每次查询复杂度为 O(1)。若使用更高时间复杂度算法不保证能通过。
如果您认为您的代码时间复杂度正确但是 TLE,可以尝试使用快速读入:
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;
}
函数返回值为读入的第一个整数。
快速读入作用仅为加快读入,并非强制使用。
题目描述
给定一个长度为 N 的数列,和 M 次询问,求出每一次询问的区间内数字的最大值。
输入格式
第一行包含两个整数 N,M,分别表示数列的长度和询问的个数。
第二行包含 N 个整数(记为 ai),依次表示数列的第 i 项。
接下来 M 行,每行包含两个整数 li,ri,表示查询的区间为 [li,ri]。
输出格式
输出包含 M 行,每行一个整数,依次表示每一次询问的结果。
输入输出样例
输入 #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复制
9 9 7 7 9 8 7 9
说明/提示
对于 30% 的数据,满足 1≤N,M≤10。
对于 70% 的数据,满足 1≤N,M≤105。
对于 100% 的数据,满足 1≤N≤105,1≤M≤2×106,ai∈[0,109],1≤li≤ri≤N。\
#include <bits/stdc++.h>
using namespace std;
#define int long long
#define IOS ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
#define endl '\n'
const int N = 1e6 + 10;
const int mod = 998244353;
int n, m,a[N];
int f[N][25];
int MOD(int x)
{
return ((x % mod) + mod) % mod;
}
void pre()
{
for(int i = 1; i <= n; i++)
f[i][0] = a[i];
int t = log(n) / log(2) + 1;
for(int i = 1; i < t; i++)
for(int j = 1; j <= n - (1 << i) + 1; j++)
f[j][i] = max(f[j][i-1],f[j+(1<<(i-1))][i-1]);
}
int ask(int l, int r)
{
int k = log2(r - l + 1);
return max(f[l][k], f[r - (1 << k) + 1][k]);
}
signed main()
{
IOS;
cin >> n >> m;
for(int i = 1; i <= n; i++) cin >> a[i];
pre();
while(m--)
{
int x, y;
cin >> x >> y;
cout << ask(x, y) << endl;
}
}
时间限制: 1.0 秒
空间限制: 512 MiB
相关文件: 题目目录
题目背景
西西艾弗岛上弗艾西西大学的同学们正在集体锻炼。
题目描述
现在一共有 nn 个弗艾西西大学的同学站成一排,同学们的体魄各有不同,第 ii 个同学具有力量值 aiai。
在集体锻炼的过程中,老师会指定队列中连续一段同学,让他们协作完成一项运动。这项运动的强度由这些同学的力量值决定,具体而言,假设老师选择了第 ll 到第 rr 个同学,所进行运动的强度就是 gcd(al,al+1,…,ar)gcd(al,al+1,…,ar),其中 gcdgcd 表示最大公约数。特别地,当 l=rl=r 时,我们认为运动的强度就等于 alal。
基于以上的事实,老师规定对一个区间 [l,r][l,r],它的体育价值 f([l,r])=l×r×gcd(al,al+1,…,ar)f([l,r])=l×r×gcd(al,al+1,…,ar)。
老师想求所有区间的体育价值之和,即 ∑l=1n∑r=lnf([l,r])∑l=1n∑r=lnf([l,r])。
因为人实在太多了,老师不能自己算,于是希望你能帮他写一个程序来计算。如果你写出这个程序,他就会给你加平时分。答案很大,你只需要求出其对 998244353998244353 取模的结果即可。
输入格式
从标准输入读入数据。
输入的第一行为一个整数 nn,表示同学的数量。
接下来一行 nn 个整数 a1,a2,…,ana1,a2,…,an,代表 nn 个同学的力量值。
输出格式
输出到标准输出。
输出一行一个整数表示所有区间的体育价值之和对 998244353998244353 取模的结果。
样例1输入
5
10 2 6 6 8
样例1输出
586
样例2输入
20
7 6 5 5 17 18 13 3 11 12 7 9 16 15 5 19 20 13 14 6
样例2输出
57254
子任务
本题采用捆绑测试,你只有通过一个子任务中的所有测试点才能得到该子任务的分数。
- 子任务一(3030 分):保证 n≤1000n≤1000 且 ai≤105ai≤105;
- 子任务二(2020 分):保证 n≤105n≤105 且 ai≤10ai≤10;
- 子任务三(3030 分):保证 n,ai≤105n,ai≤105;
- 子任务四(2020 分):无特殊限制。
对于所有数据,保证 1≤n,ai≤1061≤n,ai≤106。
语言和编译选项
# | 名称 | 编译器 | 额外参数 | 代码长度限制 |
---|---|---|---|---|
0 | g++ | g++ |
-O2 -DONLINE_JUDGE |
65536 B |
1 | gcc | gcc |
-O2 -DONLINE_JUDGE |
65536 B |
2 | java | javac |
65536 B | |
3 | python3 | python3 |
65536 B |
GCD 是单调不增的:
增加一个元素,GCD 不会变大。
所以对于固定的
l
,往右延伸r
,每一个 GCD 值最多只会出现log(a[i])
次。利用这个性质,我们可以从
r = l
开始,向右延伸,跳过多个区间,而不是每次只移动r++
,从而达到更优复杂度。将多项式累加变为公式:
使用等差和公式一次性计算区间贡献。
模块 技术/思路 复杂度 区间 GCD 查询 稀疏表 RMQ O(n log n)
预处理,O(1)
查询区间贡献统计 GCD 区间段 + 等差和 近似 O(n log A)
答案合并 数学技巧 快速准确
#include <bits/stdc++.h>
using namespace std;
#define LL long long
#define IOS ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
#define endl '\n'
const int N = 1e6 + 10;
const int mod = 998244353;
int n, m,a[N];
int f[N][25];
LL ans;
LL MOD(LL x)
{
return ((x % mod) + mod) % mod;
}
void pre()
{
for(int i = 1; i <= n; i++)
f[i][0] = a[i];
int t = log2(n) + 1;
for(int i = 1; i < t; i++)
for(int j = 1; j <= n - (1 << i) + 1; j++)
f[j][i] = __gcd(f[j][i-1],f[j+(1<<(i-1))][i-1]);
}
int ask(int l, int r)
{
int k = log2(r - l + 1);
return __gcd(f[l][k], f[r - (1 << k) + 1][k]);
}
signed main()
{
IOS;
cin >> n ;
for(int i = 1; i <= n; i++) cin >> a[i];
pre();
for(int l = 1; l <= n; l++)
{
int r = l;
int gys = a[l];
while(r <= n)
{
int ll = r, rr = n;
while(ll < rr)
{
int mid = (ll + rr + 1) >> 1;
if(ask(l, mid) == gys)
ll = mid;
else rr = mid - 1;
}
LL sum = ( (LL)(ll + r) * (ll - r + 1 )) / 2;
ans = MOD(ans + 1ll * MOD(l)* MOD(sum) * MOD(gys));
r = rr + 1;
gys = __gcd(gys, a[r]);
}
}
cout << MOD(ans) << endl;
}