st表 && csp37 第四题 集体锻炼

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​)，其中 gcd⁡gcd 表示最大公约数。特别地，当 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=ln​f([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。

语言和编译选项

• 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;
}