当前位置：首页 > news >正文

Y1——ST表

news 来源：原创 2025/9/12 13:13:17

知识点

ST表

只能询问，不能修改

ST表的预处理：

使用了DP的思想，设a是要求区间最值的数列，f(i,j)表示从第i个数起连续2^j个数中的最大值

状态转移方程

f [ i , j ]=max( f [ i , j-1 ], f [ i + 2 ^ j-1,j - 1])

建立ST表

void build(){//建立ST表，时间复杂度O(nlogn)
   for(int i=1;i<=n;i++){
       f[i][0]=a[i];
   }
   for(int j=1;(1<<j)<=n;j++){//枚举区间长度
       for(int i=1;i+(i<<j)-1<=n;i++){//枚举区间左端点
           f[i][j]=max(f[i][j-1],f[i+(1<<j-1)][j-1]);
       }
   }
}

查询区间信息

int query(int l,int r)//查询区间[l,r]的信息（最大值、最小值……）
int k=log2(r-l+1);
return max(f[l][k],f[r-(1<<k)+1][k]);
}

题题题题

平衡的阵容

题目描述

每天,农夫John的n(1≤n≤5×10^4)头牛总是按同一序列排队。有一天, John 决定让一些牛们玩一场飞盘比赛。他准备找一群在队列中位置连续的牛来进行比赛。但是为了避免水平悬殊，牛的身高不应该相差太大。JohnJohn 准备了q(1≤q≤1.8×10^5)个可能的牛的选择和所有牛的身高hi(1≤hi≤106,1≤i≤n)hi(1≤hi≤106,1≤i≤n)。他想知道每一组里面最高和最低的牛的身高差。

输入格式
第一行两个数n,q。接下来n行，每行一个数hi。再接下来q行，每行两个整数a和b，表示询问第a头牛到第b头牛里的最高和最低的牛的身高差。

输出格式
输出共q行，对于每一组询问，输出每一组中最高和最低的牛的身高差。

样例输入

6 3

1

7

3

4

2

5

1 5

4 6

2 2

样例输出

6

3

0

代码

#include<iostream>
#include<cstdio>
#include<cmath>
using namespace std;
const int N=5e4+5;
int n,q,a,b,h[N],f[N][20],f1[N][20]; 
void build(){//建立ST表，时间复杂度O(nlogn) for(int i=1;i<=n;i++){f[i][0]=h[i];f1[i][0]=h[i];}for(int j=1;(1<<j)<=n;j++){//枚举区间长度 for(int i=1;i+(1<<j)-1<=n;i++){//枚举区间左端点 f[i][j]=max(f[i][j-1],f[i+(1<<j-1)][j-1]); f1[i][j]=min(f1[i][j-1],f1[i+(1<<j-1)][j-1]);} } 
}
int query(int l,int r){//查询区间[l,r]的信息（最大值、最小值……） int k=log2(r-l+1);int maxx=max(f[l][k],f[r-(1<<k)+1][k]);int minn=min(f1[l][k],f1[r-(1<<k)+1][k]);return maxx-minn;
}
int main(){ios::sync_with_stdio(false);cin.tie(0),cout.tie(0); cin>>n>>q;for(int i=1;i<=n;i++){cin>>h[i];} build();for(int i=1;i<=q;i++){cin>>a>>b;cout<<query(a,b)<<"\n";}return 0;
}

GCD

时间限制：2秒内存限制：128M

题目描述

给你一个 N(N≤100,000)N(N≤100,000) 个整数序列：a1,⋯,an(0<ai≤1000,000,000)a1,⋯,an(0<ai≤1000,000,000)。有 Q(Q≤100,000)Q(Q≤100,000) 个查询。对于每个查询 l,rl,r，您必须计算 gcd(al,,al+1,⋯,ar)gcd(al,,al+1,⋯,ar) 并计算对的数量(l′,r′)(1≤l<r≤N)(l′,r′)(1≤l<r≤N)，使得 gcd(al′,al′+1,⋯,ar′)gcd(al′,al′+1,⋯,ar′) 等于 gcd(al,al+1,⋯,ar)gcd(al,al+1,⋯,ar)。

输入描述

第一行输入包含一个数字TT，代表你需要解决的测试用例的数量。

每个 casecase 的第一行包含一个数字N(N≤100,000)N(N≤100,000)，表示整数的数量。

第二行包含 NN 个整数，a1,⋯,an(0<ai≤1000,000,000)a1,⋯,an(0<ai≤1000,000,000)。

第三行包含一个数字Q(Q≤100,000)Q(Q≤100,000)，表示查询的数量。

对于接下来的 QQ 行，第 ii 行包含两个数字，代表 li,rili,ri，代表第 ii 个查询。

输出描述

对于每个casecase，需要在开头输出“Case #t:”。（不带引号，tt表示测试用例的编号，从11开始）。

对于每个查询，您需要在一行中输出两个数字。第一个数字代表 gcd(al,al+1,⋯,ar)gcd(al,al+1,⋯,ar)，第二个数字代表对 (l′,r′)(l′,r′) 的数量，使得 gcd(al′,al′+1,⋯,ar′)gcd(al′,al′+1,⋯,ar′) 等于 gcd(al,al+1,⋯,ar)gcd(al,al+1,⋯,ar)。