[洛谷P3865]【模板】ST表

题目大意：区间静态最大值

题解：ST表，zkw线段树

ST表：

st[i][j]存[i,i+$j^{2}$-1]的最大值，查询时把区间分成两个长度相同的小区间（可重复）

#include<cstdio>

#include<cctype>

using namespace std;

const int maxn=100010;

int n,m,M;

int st[maxn][20],lg[maxn];

inline int max(int a,int b){return a>b?a:b;}

inline void read(int &x){

	char t=getchar();

	while (!isdigit(t))t=getchar();

	for (x=t^48,t=getchar();isdigit(t);t=getchar())x=x*10+(t^48);

}

int main(){

	read(n),read(m);

	lg[0]=-1;

    for (int i=1;i<=n;i++)lg[i]=lg[i>>1]+1;

    for (int i=1;i<=n;i++)read(st[i][0]);

    for (int i=1;i<=17;i++){

    	int tmp=1<<i-1;

    	for (int j=1;j+(tmp<<1)-1<=n;j++)st[j][i]=max(st[j][i-1],st[j+tmp][i-1]);

	}

    while (m--) {

    	int x,y,tmp;

        read(x),read(y);

        tmp=lg[y-x+1];

        printf("%d\n",max(st[x][tmp],st[y-(1<<tmp)+1][tmp]));

    }

    return 0;

}

ZKW线段树：

#include<cstdio>

#include<cctype>

using namespace std;

const int maxn=100010;

int n,m,M;

int ts[maxn<<2];

inline int max(int a,int b){return a>b?a:b;}

inline void read(int &x){

	char t=getchar();

	while (!isdigit(t))t=getchar();

	for (x=t^48,t=getchar();isdigit(t);t=getchar())x=x*10+(t^48);

}

int ask(int s,int t){

	int ans=-2147483647;

	for (s+=M-1,t+=M+1;s^t^1;s>>=1,t>>=1){

		if (~s&1)ans=max(ans,ts[s^1]);

		if (t&1)ans=max(ans,ts[t^1]);

	}

	return ans;

}

int main(){

	read(n),read(m);

	for (M=1;M<=n+1;M<<=1);

	for (int i=M+1;i<=M+n;i++)read(ts[i]);

	for (int i=M-1;i;i--)ts[i]=max(ts[i<<1],ts[i<<1|1]);

	while (m--){

		int x,y;

		read(x),read(y);

		printf("%d\n",ask(x,y));

	}

	return 0;

}