ST表模板

2024-08-28 01:44
文章标签 模板 st

本文主要是介绍ST表模板,希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!

P3865 【模板】ST 表 && RMQ 问题 - 洛谷 | 计算机科学教育新生态 (luogu.com.cn)

思路:区间最大值,模板题。

int n,m;
int arr[100005];
int f[100005][25];     (1<<20)=1e6
void init(){                                o(nlogn)for(int i=1;i<=n;i++) f[i][0]=arr[i];for(int j=1;j<=20;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]);}}
}
inline int query(int l,int r){         o(1)int k=log2(r-l+1);return max(f[l][k],f[r-(1<<k)+1][k]);
}
【模板】ST 表 && RMQ 问题
https://www.luogu.com.cn/problem/P3865
void solve(){cin>>n>>m;for(int i=1;i<=n;i++) cin>>arr[i];init();while(m--){int l,r; cin>>l>>r;cout<<query(l,r)<<endl;}
}

P2251 质量检测 - 洛谷 | 计算机科学教育新生态 (luogu.com.cn)

思路:区间最小值,模板题。

int n,m;
int arr[1000006];
int f[1000006][25];   (1<<20)=1e6
void init(){for(int i=1;i<=n;i++) f[i][0]=arr[i];for(int j=1;j<=20;j++){for(int i=1;i+(1<<j)-1<=n;i++){f[i][j]=min(f[i][j-1],f[i+(1<<(j-1))][j-1]);}}
}
int query(int l,int r){int k=log2(r-l+1);return min(f[l][k],f[r-(1<<k)+1][k]);
}
P2251 质量检测
https://www.luogu.com.cn/problem/P2251
void solve(){cin>>n>>m;for(int i=1;i<=n;i++) cin>>arr[i];init();for(int i=1;i+m-1<=n;i++){int l=i,r=i+m-1;cout<<query(l,r)<<endl;}
}

P2880 [USACO07JAN] Balanced Lineup G - 洛谷 | 计算机科学教育新生态 (luogu.com.cn)

思路:区间极差,也是模板题。

int n,q;
int arr[50004];
int mx[50004][25];
int mi[50004][25];
void init(){for(int i=1;i<=n;i++) mx[i][0]=arr[i],mi[i][0]=arr[i];for(int j=1;j<=20;j++){     枚举区间长度,因为是2^j,所以永远是偶数for(int i=1;i+(1<<j)-1<=n;i++){ 枚举区间起点,i+(1<<j)-1<=n保证了当前枚举的区间起点及长度不会超出nmx[i][j]=max(mx[i][j-1],mx[i+(1<<(j-1))][j-1]);mi[i][j]=min(mi[i][j-1],mi[i+(1<<(j-1))][j-1]);}}
}
int query(int l,int r){int k=log2(r-l+1);return max(mx[l][k],mx[r-(1<<k)+1][k])-min(mi[l][k],mi[r-(1<<k)+1][k]);
}
纯板子--区间询问极差
P2880 [USACO07JAN] Balanced Lineup G
https://www.luogu.com.cn/problem/P2880
void solve(){cin>>n>>q;for(int i=1;i<=n;i++) cin>>arr[i];init();while(q--){int l,r; cin>>l>>r;cout<<query(l,r)<<endl;}
}

[ABC352D] Permutation Subsequence - 洛谷 | 计算机科学教育新生态 (luogu.com.cn)

思路: 思维题,换个角度(下标)维护区间最大最小值。思想类似用树状数组求逆序对中,桶的作用 转换之后实际上就是求区间长度为k的最小极差。

int n,k;
int arr[200005];
int mx[200005][25];
int mi[200005][25];
void init(){for(int i=1;i<=n;i++) mx[i][0]=arr[i],mi[i][0]=arr[i];for(int j=1;j<=20;j++){for(int i=1;i+(1<<j)-1<=n;i++){mx[i][j]=max(mx[i][j-1],mx[i+(1<<(j-1))][j-1]);mi[i][j]=min(mi[i][j-1],mi[i+(1<<(j-1))][j-1]);}}
}
int query(int l,int r){int x=log2(r-l+1);return max(mx[l][x],mx[r-(1<<x)+1][x])-min(mi[l][x],mi[r-(1<<x)+1][x]);
}
思维题,换个角度(下标)维护区间最大最小值。思想类似用树状数组求逆序对中,桶的作用
转换之后实际上就是求区间长度为k的最小极差
[ABC352D] Permutation Subsequence
https://www.luogu.com.cn/problem/AT_abc352_d
void solve(){cin>>n>>k;for(int i=1;i<=n;i++){int x; cin>>x;arr[x]=i;}init();int ans=INT_MAX;for(int i=1;i+k-1<=n;i++) ans=min(ans,query(i,i+k-1));cout<<ans;
}

P2866 [USACO06NOV] Bad Hair Day S - 洛谷 | 计算机科学教育新生态 (luogu.com.cn)

思路:ST表+二分

法二:ST表,比单调栈麻烦,ST表预处理的是每个区间最大值,然后枚举i,二分区间右端点,进行o(1)查询[i+1,mid]是否合法
题目理解为每头牛向右看,有多少个比自己矮的,遇到第一个>=自己的就不算了.
int n;
int arr[80004];
法一:单调栈--题目理解为每个牛向左看,能看到多少个比自己高的,那么就是从左到右维护单调递减的栈
P2866 [USACO06NOV] Bad Hair Day S
https://www.luogu.com.cn/problem/P2866
void solve(){cin>>n;for(int i=1;i<=n;i++) cin>>arr[i];stack<int> stk;int ans=0;for(int i=1;i<=n;i++){if(stk.size()&&arr[i]<stk.top()) ans+=stk.size();else if(stk.size()&&arr[i]>=stk.top()){     取等,因为是从右往左看,同等身高的不能算while(stk.size()&&arr[i]>=stk.top()) stk.pop();ans+=stk.size();}stk.emplace(arr[i]);}cout<<ans;
}int n;
int arr[80004];
int f[80004][25];
void init(){for(int i=1;i<=n;i++) f[i][0]=arr[i];for(int j=1;j<=20;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]);  1<<(j-1)}}
}
int query(int l,int r){    o(1)int k=log2(r-l+1);return max(f[l][k],f[r-(1<<k)+1][k]);
}
法二:ST表,比单调栈麻烦,ST表预处理的是每个区间最大值,然后枚举i,二分区间右端点,进行o(1)查询[i+1,mid]是否合法
题目理解为每头牛向右看,有多少个比自己矮的,遇到第一个>=自己的就不算了.
P2866 [USACO06NOV] Bad Hair Day S
https://www.luogu.com.cn/problem/P2866
void solve(){cin>>n;for(int i=1;i<=n;i++) cin>>arr[i];init();int ans=0;for(int i=1;i<=n-1;i++){   o(nlogn)int l=i+1,r=n,res=i;while(l<=r){int mid=(l+r)>>1;if(query(i+1,mid)<arr[i]){res=mid;l=mid+1;}else r=mid-1;}ans+=res-i;}cout<<ans;
}

P7167 [eJOI2020 Day1] Fountain - 洛谷 | 计算机科学教育新生态 (luogu.com.cn)

思路: 标签:倍增,ST表,应该再加个二分标签。

ST表用作二分找第i个盘的下一个盘,然后建图 建图之后倍增。

倍增的过程跟lca的初始化过程同理。

int n,q;
pair<int,int> arr[100005];
int mx[100005][25];
int nex[100005];
void init1(){for(int i=1;i<=n;i++) mx[i][0]=arr[i].first;for(int j=1;j<=20;j++){for(int i=1;i+(1<<j)-1<=n;i++){mx[i][j]=max(mx[i][j-1],mx[i+(1<<(j-1))][j-1]);}}
}
int query(int l,int r){int k=log2(r-l+1);return max(mx[l][k],mx[r-(1<<k)+1][k]);
}
pair<int,int> f[100005][25];   f[i][j]定义为,从第i个点往下跳2^j步,为<累计水容量,到达的层数编号>
void init2(){           往下跳--倍增for(int i=1;i<=n;i++) f[i][0]={arr[i].second+arr[nex[i]].second,nex[i]};for(int j=1;j<=20;j++){for(int i=1;i+(1<<j)-1<=n;i++){int halfIdx=f[i][j-1].second;f[i][j].first=f[i][j-1].first+f[halfIdx][j-1].first-arr[halfIdx].second;f[i][j].second=f[halfIdx][j-1].second;}}
}
标签:倍增,ST表,,应该再加个二分标签
ST表用作二分找第i个盘的下一个盘,然后建图
建图之后倍增,跟lca的初始化过程同理
基本上是一发入魂(最后输出答案的地方判错了一点,导致全wa)!!无敌了,第一次写倍增。
P7167 [eJOI2020 Day1] Fountain
https://www.luogu.com.cn/problem/P7167
void solve(){                   好题,好题.倍增入门题.cin>>n>>q;for(int i=1;i<=n;i++) cin>>arr[i].first>>arr[i].second;   <直径,容量>init1();for(int i=1;i<=n;i++){    o(nlogn)  n次二分,每次check是o(1)的int l=i+1,r=n,res=0;while(l<=r){int mid=(l+r)>>1;if(query(i+1,mid)>arr[i].first){res=mid;r=mid-1;}else l=mid+1;}nex[i]=res;   建图}init2();while(q--){int x,v; cin>>x>>v;if(v<=arr[x].second) cout<<x<<endl;else{int cur=x;j从大到小for(int j=20;j>=0;j--){if(f[cur][j].second!=0&&f[cur][j].first<=v){v-=f[cur][j].first;cur=f[cur][j].second;v+=arr[cur].second;}}if(v<=arr[cur].second) cout<<cur<<endl; v<=arr[cur].second 而不是v==0else cout<<nex[cur]<<endl;}}
}

to be continue...

这篇关于ST表模板的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!



http://www.chinasem.cn/article/1113374

相关文章

poj3468(线段树成段更新模板题)

题意:包括两个操作:1、将[a.b]上的数字加上v;2、查询区间[a,b]上的和 下面的介绍是下解题思路: 首先介绍  lazy-tag思想:用一个变量记录每一个线段树节点的变化值,当这部分线段的一致性被破坏我们就将这个变化值传递给子区间,大大增加了线段树的效率。 比如现在需要对[a,b]区间值进行加c操作,那么就从根节点[1,n]开始调用update函数进行操作,如果刚好执行到一个子节点,

C++11第三弹:lambda表达式 | 新的类功能 | 模板的可变参数

🌈个人主页: 南桥几晴秋 🌈C++专栏: 南桥谈C++ 🌈C语言专栏: C语言学习系列 🌈Linux学习专栏: 南桥谈Linux 🌈数据结构学习专栏: 数据结构杂谈 🌈数据库学习专栏: 南桥谈MySQL 🌈Qt学习专栏: 南桥谈Qt 🌈菜鸡代码练习: 练习随想记录 🌈git学习: 南桥谈Git 🌈🌈🌈🌈🌈🌈🌈🌈🌈🌈🌈🌈🌈�

poj 1258 Agri-Net(最小生成树模板代码)

感觉用这题来当模板更适合。 题意就是给你邻接矩阵求最小生成树啦。~ prim代码:效率很高。172k...0ms。 #include<stdio.h>#include<algorithm>using namespace std;const int MaxN = 101;const int INF = 0x3f3f3f3f;int g[MaxN][MaxN];int n

uva 1342 欧拉定理(计算几何模板)

题意: 给几个点,把这几个点用直线连起来,求这些直线把平面分成了几个。 解析: 欧拉定理: 顶点数 + 面数 - 边数= 2。 代码: #include <iostream>#include <cstdio>#include <cstdlib>#include <algorithm>#include <cstring>#include <cmath>#inc

uva 11178 计算集合模板题

题意: 求三角形行三个角三等分点射线交出的内三角形坐标。 代码: #include <iostream>#include <cstdio>#include <cstdlib>#include <algorithm>#include <cstring>#include <cmath>#include <stack>#include <vector>#include <

poj 2104 and hdu 2665 划分树模板入门题

题意: 给一个数组n(1e5)个数,给一个范围(fr, to, k),求这个范围中第k大的数。 解析: 划分树入门。 bing神的模板。 坑爹的地方是把-l 看成了-1........ 一直re。 代码: poj 2104: #include <iostream>#include <cstdio>#include <cstdlib>#include <al

最大流、 最小费用最大流终极版模板

最大流  const int inf = 1000000000 ;const int maxn = 20000 , maxm = 500000 ;struct Edge{int v , f ,next ;Edge(){}Edge(int _v , int _f , int _next):v(_v) ,f(_f),next(_next){}};int sourse , mee

C++语法知识点合集:11.模板

文章目录 一、非类型模板参数1.非类型模板参数的基本形式2.指针作为非类型模板参数3.引用作为非类型模板参数4.非类型模板参数的限制和陷阱:5.几个问题 二、模板的特化1.概念2.函数模板特化3.类模板特化(1)全特化(2)偏特化(3)类模板特化应用示例 三、模板分离编译1.概念2.模板的分离编译 模版总结 一、非类型模板参数 模板参数分类类型形参与非类型形参 非类型模板

Smarty模板引擎工作机制(一)

深入浅出Smarty模板引擎工作机制,我们将对比使用smarty模板引擎和没使用smarty模板引擎的两种开发方式的区别,并动手开发一个自己的模板引擎,以便加深对smarty模板引擎工作机制的理解。 在没有使用Smarty模板引擎的情况下,我们都是将PHP程序和网页模板合在一起编辑的,好比下面的源代码: <?php$title="深处浅出之Smarty模板引擎工作机制";$content=

Smarty模板执行原理

为了实现程序的业务逻辑和内容表现页面的分离从而提高开发速度,php 引入了模板引擎的概念,php 模板引擎里面最流行的可以说是smarty了,smarty因其功能强大而且速度快而被广大php web开发者所认可。本文将记录一下smarty模板引擎的工作执行原理,算是加深一下理解。 其实所有的模板引擎的工作原理是差不多的,无非就是在php程序里面用正则匹配将模板里面的标签替换为php代码从而将两者