HDU - 5443 The Water Problem(ST表)

Posted on | In ,

思路

ST表模板

ST表

ST表是rmq的一种实现方式。初始化复杂度O(nlogn)，查询O(1),不支持修改，不能实现区间和(与st表查询方式有关，但我仔细想了想，感觉似乎修改下查询应该能在logn时间里得到区间和)。

初始化

ST表的初始化用到了倍增的思路。我们令ST[i][j]维护的是从i开始的，长度为2^j的区间，即[i,i+2^j-1]。那么显然有st[i][j]=function(min,max,|,…自选)(st[i][j-1],st[i+2^(j-1)][j-1])。因为st表维护区间的长度都是2的倍数，所以能做到区间合并时不重不漏。

查询

查询时我们取k=(int)log2(n)。然后求max(st[x][k],st[y-powerOfTwo[k]+1][k])即可。这样的区间实际上是有重叠的，所以这也是为什么我之前说的st表不能处理区间和问题。但是因为在rmq中没有这样的问题，所以我们大可放心使用。

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
#include <bits/stdc++.h>
#define ll long long
#define INF 0x7fffffff
#define inf 0x7fffffffffffffff
#define ms(a,val) memset((a),(val),(sizeof(a)))
#define sqr(x) ((x)*(x))
#define all(x) (x).begin(),(x).end()
using namespace std;
ll quickpow(ll a,ll b,ll MOD){ll ans=1;a%=MOD;while(b){if(b&1)ans=ans*a%MOD;a=a*a%MOD,b>>=1;}return ans;}
//head

//STtable and data needed
const int MAXN=1005;
const int LogMAXN=(int)(log(MAXN)/log(2))+5;
template <typename T>
struct STtable{
    //init O(nlogn),query O(1)
    //st[i][j] means it charges the interval of [i,i+2^j-1]
    T st[MAXN][LogMAXN];
    int powerOfTwo[LogMAXN],logOfTwo[MAXN];
    STtable(T A[],int n){
        powerOfTwo[0]=1;
        for(int i=1;i<LogMAXN;i++)powerOfTwo[i]=(powerOfTwo[i-1]<<1);
        logOfTwo[0]=-1;
        for(int i=1;i<MAXN;i++)logOfTwo[i]=((i)&(i-1))==0?logOfTwo[i-1]+1:logOfTwo[i-1];
        for(int i=0;i<n;i++)st[i][0]=A[i];
        //STtable initiation, you may change the function here
        for(int i=1;i<=logOfTwo[n];i++){
            for(int j=0;j+powerOfTwo[i]-1<n;j++){
                st[j][i]=max(st[j][i-1],st[j+powerOfTwo[i-1]][i-1]);
            }
        }
    }
    T rmq(int x,int y){
        int k=logOfTwo[y-x+1];
        return max(st[x][k],st[y-powerOfTwo[k]+1][k]);
    }
};
int a[1005];

int main() {
    int T;
    scanf("%d",&T);
    while(T--){
        int n,q,l,r;
        scanf("%d",&n);
        for(int i=0;i<n;i++)scanf("%d",&a[i]);
        STtable<int> st(a,n);
        scanf("%d",&q);
        for(int i=0;i<q;i++){
            scanf("%d%d",&l,&r);
            printf("%d\n",st.rmq(l-1,r-1));
        }
    }
    return 0;
}