首页 > 代码库 > 【模板】ST表 洛谷P1816 忠诚
【模板】ST表 洛谷P1816 忠诚
P1816 忠诚
题目描述
老管家是一个聪明能干的人。他为财主工作了整整10年，财主为了让自已账目更加清楚。要求管家每天记k次账，由于 管家聪明能干，因而管家总是让财主十分满意。但是由于一些人的挑拨，财主还是对管家产生了怀疑。于是他决定用一种特别的方法来判断管家的忠诚，他把每次的 账目按1，2，3…编号，然后不定时的问管家问题，问题是这样的：在a到b号账中最少的一笔是多少？为了让管家没时间作假他总是一次问多个问题。
输入输出格式
输入格式：输入中第一行有两个数m,n表示有m(m<=100000)笔账,n表示有n个问题，n<=100000。
第二行为m个数,分别是账目的钱数
后面n行分别是n个问题,每行有2个数字说明开始结束的账目编号。
输出格式：输出文件中为每个问题的答案。具体查看样例。
输入输出样例
输入样例#1：
10 31 2 3 4 5 6 7 8 9 102 73 91 10
输出样例#1：
2 3 1
被线段树骗了进来。。。线段树写RMQ太水了，树状数组写RMQ更水，于是顺手温习了一遍ST表。
stlist[i][j]表示区间[i, i + 1 << j - 1]内的极值
初始状态：stlist[i][0] = num[i]
令M = log2 (n),n为元素个数 最好写成循环，打个表。这里偷懒没有打表，小心被无比黑心的出题人卡常（不过这种常数也太难卡了吧。。。）
状态转移方程：stlist[i][j] = max/min{stlist[i][j - 1], stlist[i + 1 <<(j - 1)][j - 1]} 算一算，区间分别是[i, i + 1 << (j - 1) - 1]和[i + 1 << (j - 1), i + 1 << j - 1],
合起来正好是stlist[i][j]表示的区间。这个比较好记，记住stlist[i][j - 1]，以及stlist[x][j - 1],区间连续性，x很容易推出来
查询的时候，令M = log2（r - l + 1）,即(r - l + 1)/2 < 2^M <= r - l + 1（区间长度）
查询区间[l,r]: max/min{stlist[l][M], stlist[r - 1 << M + 1][M]} 区间正好是[l, l + 1 << M - 1],[r - (1 << M - 1), r]
只需证 l + 2^M - 1 > r - 2^M + 1 + 1 即证2^M > （r - l + 1）/2 + 1 显然
我本来证不出来，拿去找MOdalao，换了三次不等式全是错的，后来发现我L和1混了然后少加了一个1，改成正确的之后，秒解这个弱智不等式。。
上代码
1 #include <bits/stdc++.h> 2 const int INF = 0x3f3f3f3f; 3 const int MAXN = 100000 + 10; 4 inline void read(int &x){ 5 x = 0;char ch = getchar();char c = ch; 6 while(ch > ‘9‘ || ch < ‘0‘)c = ch, ch = getchar(); 7 while(ch <= ‘9‘ && ch >= ‘0‘)x = x * 10 + ch - ‘0‘,ch = getchar(); 8 if(c == ‘-‘) x = -x; 9 }10 inline int min(int a,int b){return a > b ? b : a;}11 inline int max(int a,int b){return a > b ? a : b;}12 int stlist[MAXN][20],n,m;13 void stwork(){14 int M = 0;15 while(1 << (M + 1) <= n)M ++;16 for(int i = 1;i <= M;i ++){17 for(int j = n;j > 0;j --){18 stlist[j][i] = stlist[j][i - 1];19 if(j + (1 << (i - 1)) <= n)stlist[j][i] = min(stlist[j][i], stlist[j + (1 << (i - 1))][i - 1]);20 }21 }22 }23 int stfind(int l, int r){24 int M = 0;25 while(1 << (M + 1) <= (r - l + 1))M ++;26 return min(stlist[l][M], stlist[r - (1 << M) + 1][M]);//[l, l + 2 ^ M - 1],[r - ( 2 ^ M - 1), r] ,27 }28 int main(){29 read(n);read(m);30 for(int i = 1;i <= n;i ++)read(stlist[i][0]);31 stwork();32 for(int i = 1;i <= m;i ++)33 {34 int tmp1,tmp2;35 read(tmp1);read(tmp2);36 printf("%d ", stfind(tmp1, tmp2));37 } 38 return 0;39 }
【模板】ST表 洛谷P1816 忠诚
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。