RMQ
可能是我见过最没啥用的DSA
ST表从入门到入门 ->GO
POJ3368 UVA11235
注意补全的思想,每次query从频率1的算起
WA了两发在t越界的情况
G++ 1200+ms C++ 600+ms
#include<bits/stdc++.h>
using namespace std;
const int maxn = 1e5+11;
struct RMQ{
int st[maxn][20];
void init(int a[],int n){
for(int i = 1; i <= n; i++) st[i][0]=a[i];
for(int j = 1; (1<<j) <= n; j++){
for(int i = 1; i+(1<<j)-1 <= n; i++){
st[i][j]=max(st[i][j-1],st[i+(1<<(j-1))][j-1]);
}
}
}
int query(int l,int r){
if(l>r)return 0;
int k=log2(r-l+1);
return max(st[l][k],st[r-(1<<k)+1][k]);
}
}rmq;
int a[maxn],f[maxn],n,q,l,r,t;
int main(){
while(scanf("%d",&n)!=EOF){
if(n==0) break; else scanf("%d",&q);
memset(f,0,sizeof f);
for(int i = 1; i <= n; i++){
scanf("%d",&a[i]);
if(a[i]==a[i-1]) f[i]=f[i-1]+1;
else f[i]=1;
}
rmq.init(f,n);
for(int i = 1; i <= q; i++){
scanf("%d%d",&l,&r);
t=l;
while(t<=r&&a[t]==a[t-1]) t++;
printf("%d\n",max(rmq.query(t,r),t-l));
}
}
return 0;
}
二维RMQ
http://www.cnblogs.com/proverbs/archive/2012/10/05/2711985.html
LCA转RMQ //感觉和tarjan比没多大优势啊,说是在线不还是预处理
参考华农dalao的资料:http://www.cnblogs.com/scau20110726/archive/2013/05/26/3100812.html
https://wenku.baidu.com/view/8c4c0130f111f18583d05af9.html
http://blog.csdn.net/say_c_box/article/details/77838572
看不懂的约束RMQ
神犇的资料:http://www.cnblogs.com/jklongint/p/4777448.html?utm_source=tuicool
http://blog.sina.com.cn/s/blog_83e9c8da0100zbtp.html