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