APTX博客

  • ACGN
  • Coding
  • DevOps
  • Daily
  • Share
  • Bangumi
APTX Blog
A Moe Blog Set Up By ミズキ
  1. 首页
  2. OI
  3. 正文

#C/C++#数据结构:ST表模板

2018年9月8日 1591点热度 0人点赞 0条评论

简介

ST表用于区间RMQ问题,它可以做到O(nlogn)预处理,O(1)查询最值。相比线段树,更加有利于静态数据的最值问题。主要是利用倍增的思想。

洛谷:P3865

模板

#include <cstdio>
#include <cstring>
#include <cstdlib>
#include <cmath>
#include <algorithm>
#include <iostream>
#include <vector>
using namespace std;

const int MAXN = 1e6 + 10;

int Max[MAXN][22];
int Min[MAXN][22];

int n,m;

void QST();
int QueryMax(int ,int );
int QueryMin(int ,int );

int main() {
	scanf("%d%d",&n,&m);
	QST();
	for(int i = 1;i <= m;++i) {
		int l,r;
		scanf("%d%d",&l,&r);
		printf("%d\n",QueryMax(l,r));
	}
	return 0;
}

void QST() {
	for(int i = 1;i <= n;++i) scanf("%d",&Max[i][0]);
	for(int i = 1;i <= n;++i) Min[i][0] = Max[i][0];
	for(int j = 1;j <= 21;++j)
		for(int i = 1;i + (1 << j)- 1 <= n;++i) {
			Max[i][j] = max(Max[i][j - 1],Max[i + (1 << (j - 1))][j - 1]);
			Min[i][j] = min(Min[i][j - 1],Min[i + (1 << (j - 1))][j - 1]);
		}
}

int QueryMax(int l,int r) {
	int k = log2(r - l + 1);
	return max(Max[l][k],Max[r - (1 << k) + 1][k]);
}

int QueryMin(int l,int r) {
	int k = log2(r - l + 1);
	return min(Min[l][k],Min[r - (1 << k) + 1][k]);
}

 

 

本作品采用 知识共享署名-非商业性使用-相同方式共享 4.0 国际许可协议 进行许可
标签: C/C++ C++ logn 数据结构 模板 洛谷
最后更新:2018年12月1日

神楽坂 みずき

萌萌萌,好萌!

点赞
< 上一篇
下一篇 >

文章评论

razz evil exclaim smile redface biggrin eek confused idea lol mad twisted rolleyes wink cool arrow neutral cry mrgreen drooling persevering
取消回复

神楽坂 みずき

萌萌萌,好萌!

搜索
最新 热点 随机
最新 热点 随机
站点域名变更通知 私たちの居る理由 《サクラノ詩》VI 章 直哉与蓝对话 从《AMRITA》到《HELLO WORLD》── 野﨑まど世界观下的个体与世界的真实感 几种云端 VSCode/类 VSCode 方案对比与部署 Summer Pockets REFLECTION BLUE 豪華限定版 早期予約色紙付き/通販・店舗対応版
#不明觉厉#红芯浏览器,国产自主内核? Claris:2014-2018/12份专辑/8.3G无损歌曲 MMPI(明尼苏达多相人格问卷)临床量表 #洛谷#C/C++P3367并查集的使用及其实现 C/C++:Prim+堆优化最小生成树模板 Nginx:301永久重定向配置以及自动跳转https配置
标签聚合
C++ 日常 C/C++ HTML 动漫 洛谷 OI ST
分类
  • ACGN
  • Coding
  • Daily
  • DevOps
  • OI
  • Share

COPYRIGHT © 2017-2022 APTX博客. ALL RIGHTS RESERVED.

Theme Kratos Made By Seaton Jiang