稀疏表动态分配封装模板求调

//the code is from chenjh
#include<cstdio>
#include<cassert>
#include<algorithm>
template<typename T>
struct SparseTable{
	public:
	SparseTable(int n=0,const T *a=nullptr):N(n){
		assert(n>=0);
		for(int i=0;i<30;i++){st1[i]=new T[n+1];st2[i]=new T[n+1];}
		lg=new unsigned int[n+1];
		lg[1]=0u;
		for(int i=1;i<=n;i++)lg[i]=lg[i>>1u]+1u,st1[0][i]=st2[0][i]=a[i];
		for(unsigned int k=1;k<=lg[n];k++)for(int i=1;i<=n;i++)
			st1[k][i]=(i+(1<<(k-1))<=n)?std::max(st1[k-1][i],st1[k-1][i+(1<<(k-1))]):st1[k-1][i],
			st2[k][i]=(i+(1<<(k-1))<=n)?std::min(st2[k-1][i],st2[k-1][i+(1<<(k-1))]):st2[k-1][i];
	}
	~SparseTable(){delete[] lg;for(int i=0;i<30;i++){delete[] st1[i];delete[] st2[i];}}
	/*
	int * GetLg()const{return lg;}
	T ** GetST1()const{return st1;}
	T ** GetST2()const{return st2;}
	SparseTable&operator = (const SparseTable& y){
		delete[] lg;for(int i=0;i<30;i++){delete[] st1[i];delete[] st2[i];}
		N=y.size();
		int*Lg=y.GetLg();
		lg=new int[N+1];memset(lg,Lg,sizeof Lg);
		for(int i=1;i<30;i++){st1[i]=new T[]}
	}
	*/
	inline int size()const{return N;}
	inline T QueryMax(const int l,const int r){
		assert(0<l && l<=r && r<=N);
		int k=lg[r-l+1];
		return std::max(st1[l][k],st1[r-(1<<k)+1][k]);
	}
	inline T QueryMin(const int l,const int r){
		assert(0<l && l<=r && r<=N);
		int k=lg[r-l+1];
		return std::min(st2[l][k],st2[r-(1<<k)+1][k]);
	}
	private:
	int N;
	unsigned int *lg;
	T *st1[30],*st2[30];
};
int n,m;
int a[100001];
int main(){
	scanf("%d%d",&n,&m);
	for(int i=1;i<=n;i++) scanf("%d",&a[i]);
	SparseTable<int> st(n,a);
	for(int x,y;m--;)scanf("%d%d",&x,&y),printf("%d\n",st.QueryMax(x,y));
	return 0;
}