P1816 忠诚
题目描述
老管家是一个聪明能干的人。他为财主工作了整整10年，财主为了让自已账目更加清楚。要求管家每天记k次账，由于 管家聪明能干，因而管家总是让财主十分满意。但是由于一些人的挑拨，财主还是对管家产生了怀疑。于是他决定用一种特别的方法来判断管家的忠诚，他把每次的 账目按1，2，3…编号，然后不定时的问管家问题，问题是这样的：在a到b号账中最少的一笔是多少？为了让管家没时间作假他总是一次问多个问题。
输入输出格式
输入格式：
输入中第一行有两个数m,n表示有m(m<=100000)笔账,n表示有n个问题，n<=100000。
第二行为m个数,分别是账目的钱数
后面n行分别是n个问题,每行有2个数字说明开始结束的账目编号。
输出格式：
输出文件中为每个问题的答案。具体查看样例。
输入输出样例
输入样例#1：
10 3
1 2 3 4 5 6 7 8 9 10
2 7
3 9
1 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，改成正确的之后，秒解这个弱智不等式。。
上代码
#include <bits/stdc++.h>
const int INF = 0x3f3f3f3f;
const int MAXN = + ;
inline void read(int &x){
x = ;char ch = getchar();char c = ch;
while(ch > '' || ch < '')c = ch, ch = getchar();
while(ch <= '' && ch >= '')x = x * + ch - '',ch = getchar();
if(c == '-') x = -x;
}
inline int min(int a,int b){return a > b ? b : a;}
inline int max(int a,int b){return a > b ? a : b;}
int stlist[MAXN][],n,m;
void stwork(){
int M = ;
while( << (M + ) <= n)M ++;
for(int i = ;i <= M;i ++){
for(int j = n;j > ;j --){
stlist[j][i] = stlist[j][i - ];
if(j + ( << (i - )) <= n)stlist[j][i] = min(stlist[j][i], stlist[j + ( << (i - ))][i - ]);
}
}
}
int stfind(int l, int r){
int M = ;
while( << (M + ) <= (r - l + ))M ++;
return min(stlist[l][M], stlist[r - ( << M) + ][M]);//[l, l + 2 ^ M - 1],[r - ( 2 ^ M - 1), r] ,
}
int main(){
read(n);read(m);
for(int i = ;i <= n;i ++)read(stlist[i][]);
stwork();
for(int i = ;i <= m;i ++)
{
int tmp1,tmp2;
read(tmp1);read(tmp2);
printf("%d ", stfind(tmp1, tmp2));
}
return ;
}