裸Sparse Table
c++
#include <iostream>
#include <string.h>
#include <stdio.h>
#include <vector>
#include <algorithm>
using namespace std;
int d[200005][20];
void RMQ_init(vector<int>& A){
int n=A.size();
for(int i=0;i<n;i++) d[i][0]=A[i];
for(int j=1;(1<<j)<=n;j++)
for(int i=0;i+(1<<j)-1<n;i++)
d[i][j]=max(d[i][j-1],d[i+(1<<(j-1))][j-1]);
}
int RMQ(int L,int R){
int k=0;
while((1<<(k+1))<=R-L+1) k++;
return max(d[L][k],d[R-(1<<k)+1][k]);
}
int main(){
int n,m;
vector<int> A;
scanf("%d",&n);
int t;
for(int i=0;i<n;i++){
scanf("%d",&t);
A.push_back(t);
}
RMQ_init(A);
scanf("%d",&m);
int L,R;
for(int i=0;i<m;i++){
scanf("%d %d",&L,&R);
printf("%d\n",RMQ(L-1,R-1));
}
return 0;
}


裸的RMQ ST算法
#include <cstdio>
#include <cstring>
#include <algorithm>

template <class T>
class SparseTable
{
protected:
T **__table;
int size,layer;
int log2(int x)
{
int t=x;
int res=0;
for(int i=16;i;i>>=1) {
if(t>>i) {
res+=i;
t>>=i;
}
}
return res;
}

public:
SparseTable():__table(0),__size(0) {}
SparseTable(T __arr,int __l,int __r)
{
size=(r-__l)+1;
layer=log2(size);
__table=new T[__layer];
table[0]=new T[size];
for(int j=__l;j<=__r;j++) table[0][j-__l]=arr[j];
for(int i=1;i<=__layer;i++) {
int subSize=__size+1-(1<<i);
__table[i]=new T[subSize];
for(int j=0;j<subSize;j++) {
int k=j+(1<<(i-1));
table[i][j]=table[i-1][j]<__table[i-1][k]?
table[i-1][j]:table[i-1][k];
}
}
}
SparseTable(T __arr, int __l, int __r,bool (__cmp)(T __x,T __y))
{
size=(r-__l)+1;
layer=log2(size);
table=new T*[layer];
table[0]=new T[size];
for(int j=__l;j<=__r;j++) table[0][j-__l]=arr[j];
for(int i=1;i<=__layer;i++) {
int subSize=__size+1-(1<<i);
__table[i]=new T[subSize];
for(int j=0;j<subSize;j++) {
int k=j+(1<<(i-1));
table[i][j]=cmp(table[i-1][j],table[i-1][k])?
table[i-1][j]:table[i-1][k];
}
}
}
virtual ~SparseTable()
{
for(int i=0;i<__layer;i++) delete[] __table[i];
delete[] __table;
}
T ask(int __l,int r)
{
int layerIdx=log2(r-__l+1);
int j=__r-(1<<layerIdx)+1;
return table[layerIdx][__l]<table[layerIdx][j]?
table[layerIdx][__l]:table[layerIdx][j];
}
T ask(int __l, int __r,bool (*cmp)(T __x,T y))
{
int layerIdx=log2(r-__l+1);
int j=__r-(1<<layerIdx)+1;
return cmp(table[layerIdx][__l],table[layerIdx][j])?
table[layerIdx][__l]:table[layerIdx][j];
}
};

bool cmp(int a,int b)
{
return a>b;
}

int main()
{
//freopen("p1174t1in.txt","r",stdin);
int N;scanf("%d",&N);
int *temp=new int[N];
for(int i=0;i<N;i++) scanf("%d",&temp[i]);
SparseTable<int> ST(temp,0,N-1,cmp);
delete[] temp;
int Q;scanf("%d",&Q);
for(int i=0;i<Q;i++) {
int l,r;scanf("%d%d",&l,&r);
printf("%d\n",ST.ask(l-1,r-1,cmp));
}
return 0;
}

#include <cstdio>
#include <algorithm>
using namespace std;
const int N=200010,inf=2099999999;
int v[N],T[N*4],n,a,b,m;
void up(int x){T[x]=max(T[x<<1|1],T[x<<1]);}
void build(int l,int r,int x){
if(l>=r){T[x]=v[l];return;}
int mid=l+r>>1;
build(l,mid,x<<1);build(mid+1,r,x<<1|1);
up(x);
}
int ask(int l,int r,int L,int R,int x){
int ret=-inf;
if(l<=L && R<=r)return T[x];
int mid=L+R>>1;
if(mid<r) ret=max(ret,ask(l,r,mid+1,R,x<<1|1));
if(l<=mid) ret=max(ret,ask(l,r,L,mid,x<<1));
return ret;
}
int main(){
scanf("%d",&n);
for(int i=1;i<=n;i++) scanf("%d",&v[i]);
build(1,n,1);
scanf("%d",&m);
for(int i=1;i<=m;i++) {
scanf("%d%d",&a,&b);
printf("%d\n",ask(a,b,1,n,1));
}
return 0;
}
线段树裸题

program a01;
var
i,j,k,l,n,m,g,h:longint;
a:array[0..200000,0..50]of longint;

function max(x,y:longint):longint;
begin
if x>y then exit(x) else exit(y);
end;

function ask(x,y:longint):longint;
var
k:longint;
begin
k:=trunc(ln(y-x+1)/ln(2));
ask:=max(a[x,k],a[y-1 shl (k)+1,k]);
end;

begin
readln(n);
for i:=1 to n do read(a[i,0]); readln;
readln(m);
k:=trunc(ln(n)/ln(2));
for j:=1 to k do
for i:=1 to n-(1 shl j)+1 do
a[i,j]:=max(a[i,j-1],a[i+1 shl (j-1),j-1]);
for i:=1 to m do
begin
readln(k,l);
if k>l then begin g:=k; k:=l; l:=g; end;
writeln(ask(k,l));
end;
end.

ST算法模板，也可以用线段树做

#include <stdio.h>
#include <math.h>

int dpMax[300000][20];

int Max(int a, int b);
void ST(int size);
int rangeMax(int left, int right);

int main(){
int num, query, i, left, right;
scanf("%d", &num);
for(i=0; i<num; i++)
scanf("%d", &dpMax[i][0]);
ST(num);
scanf("%d", &query);
while(query--){
scanf("%d %d", &left, &right);
printf("%d\n", rangeMax(left-1, right-1));
}
return 0;
}
int Max(int a, int b){
return a>b ? a:b;
}
void ST(int size){
int i, k;
for(i=1; i<=log(size)/log(2); i++){
for(k=0; k<size; k++){
if(k+(1<<i)-1<size)
dpMax[k][i] = Max(dpMax[k][i-1], dpMax[k+(1<<(i-1))][i-1]);
else
break;
}
}
}
int rangeMax(int left, int right){
int m = (int)(log(right-left+1)/log(2));
return Max(dpMax[left][m], dpMax[right-(1<<m)+1][m]);
}

#include<iostream>
#include<cstdio>
using namespace std;
struct tree{
int l,r,maxx;
};
tree node[4002000];
int n,m,a[2002000];
inline void update(int i)
{
node[i].maxx=max(node[i<<1].maxx,node[(i<<1)|1].maxx);
}
inline void build(int i,int l,int r)
{
node[i].l=l;node[i].r=r;
if(l==r){
node[i].maxx=a[l];
return;
}
int mid=(l+r)/2;
build(i<<1,l,mid);
build((i<<1)|1,mid+1,r);
update(i);
}
inline int Max(int i,int l,int r)
{
if(node[i].l==l&&node[i].r==r)
return node[i].maxx;
int mid=(node[i].l+node[i].r)/2;
if(r<=mid) return Max(i<<1,l,r);
else if(l>mid) return Max((i<<1)|1,l,r);
else return max(Max(i<<1,l,mid),Max((i<<1)|1,mid+1,r));
}
int main()
{
scanf("%d",&n);
for(int i=1;i<=n;i++)
scanf("%d",&a[i]);
build(1,1,n);
scanf("%d",&m);
for(int i=1;i<=m;i++){
int a,b;
scanf("%d%d",&a,&b);
printf("%d\n",Max(1,a,b));
}

}

n次80回回后两个点RE，火了开了个4002000的数组，AC了
#include<iostream>
#include<cstdio>
using namespace std;
struct tree{
int l,r,maxx;
};
tree node[4002000];
int n,m,a[2002000];
inline void update(int i)
{
node[i].maxx=max(node[i<<1].maxx,node[(i<<1)|1].maxx);
}
inline void build(int i,int l,int r)
{
node[i].l=l;node[i].r=r;
if(l==r){
node[i].maxx=a[l];
return;
}
int mid=(l+r)/2;
build(i<<1,l,mid);
build((i<<1)|1,mid+1,r);
update(i);
}
inline int Max(int i,int l,int r)
{
if(node[i].l==l&&node[i].r==r)
return node[i].maxx;
int mid=(node[i].l+node[i].r)/2;
if(r<=mid) return Max(i<<1,l,r);
else if(l>mid) return Max((i<<1)|1,l,r);
else return max(Max(i<<1,l,mid),Max((i<<1)|1,mid+1,r));
}
int main()
{
scanf("%d",&n);
for(int i=1;i<=n;i++)
scanf("%d",&a[i]);
build(1,1,n);
scanf("%d",&m);
for(int i=1;i<=m;i++){
int a,b;
scanf("%d%d",&a,&b);
printf("%d\n",Max(1,a,b));
}

}

#include<cstdio>
#include<algorithm>
#include<cstdlib>
using namespace std;
struct type{
int l,r;
int data;
};
int n,k,m=1,small;
int num[200010];
type tree[500100];
void maketree(int x,int s,int t){
int mid;
tree[x].l=s;
tree[x].r=t;
if (s!=t){
mid=(s+t)/2;
maketree(2*x,s,mid);
maketree(2*x+1,mid+1,t);
}
if (s==t){
if (s>n) tree[x].data=small-1;
else tree[x].data=num[s];
}
else tree[x].data=max(tree[2*x].data,tree[2*x+1].data);
}
int que(int x,int s,int t){
int l=tree[x].l,r=tree[x].r;
int mid=(l+r)/2;
int ans1,ans2=small-1;
if ((s==l)&&(t==mid)) return tree[2*x].data;
if ((s==mid+1)&&(t==r)) return tree[2*x+1].data;
if ((s==l)&&(t==r)) return tree[x].data;
if (t<=mid) ans1=que(2*x,s,t);
else{
if (s>=mid+1) ans1=que(2*x+1,s,t);
else{
ans1=que(2*x,s,mid);
ans2=que(2*x+1,mid+1,t);
}
}
return max(ans1,ans2);
}
int main(){
//freopen("p1.in","r",stdin);
scanf("%d",&n);
for (int i=1;i<=n;i++){
scanf("%d",&num[i]);
if (i==1) small=num[i];
small=min(small,num[i]);
}
while (m<n) m<<=1;
maketree(1,1,m);
scanf("%d",&m);
for (int i=0;i<m;i++){
int s,t;
scanf("%d%d",&s,&t);
printf("%d\n",que(1,s,t));
}
//fclose(stdin);
return 0;
}

裸rmq
代码奉上：
#include <iostream>
#include <cstdio>

using namespace std;

const int maxn=200005;
const int maxh=30;

int a[maxn];
int f[maxn][maxh];
int n,q;

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

int main()
{
cin>>n;
int i,j,k;
for(i=1;i<=n;i++)
{
scanf("%d",&a[i]);
f[i][0]=a[i];
}
for(i=1;(1<<i)<=n;i++)
{
for(j=1;j+(1<<i)-1<=n;j++)
{
f[j][i]=max(f[j][i-1],f[j+(1<<(i-1))][i-1]);
}
}
cin>>q;
int l,r;
while(q--)
{
scanf("%d %d",&l,&r);
int cnt=0;
while((1<<(cnt+1))<=r-l)
{
cnt++;
}
cout<<max(f[l][cnt],f[r-(1<<cnt)+1][cnt])<<endl;
}
return 0;
}

var
a,b:array[0..200000] of longint;
i,m,n,k1,k2,j:longint;
procedure sort(l,r: longint);
var
i,j,x,y: longint;
begin
i:=l;
j:=r;
x:=a[(l+r) div 2];
repeat
while a[i]>x do
inc(i);
while x>a[j] do
dec(j);
if not(i>j) then
begin
y:=a[i];
a[i]:=a[j];
a[j]:=y;
y:=b[i];
b[i]:=b[j];
b[j]:=y;
inc(i);
j:=j-1;
end;
until i>j;
if l<j then
sort(l,j);
if i<r then
sort(i,r);
end;

begin
readln(n);
for i:=1 to n do
begin
read(a[i]);
b[i]:=i;
end;
sort(1,n);
readln(m);
for i:=1 to m do
begin
readln(k1,k2);
for j:=1 to n do
if (b[j]>=k1) and (b[j]<=k2) then
break;
writeln(a[j]);
end;
end.

线段树什么的都是浮云！
直接n^2快排+枚举搞定。
当然有些投机取巧。。。
但是这个优化还是挺牛的

st即可

Block code

#include<cstdio>
#include<algorithm>
#define maxn 200001
#define maxm 200
#define REP(i,l,r) for (int i=l;i<=r;i++)

using namespace std;

int d[maxn][maxm],n,a[maxn],m;

void RMQ(){
REP(i,1,n) d[i][0]=a[i];
for (int j=1;(1<<j)<=n;j++)
for (int i=1;i+(1<<j)-1<=n;i++)
d[i][j]=max(d[i][j-1],d[i+(1<<(j-1))][j-1]);
return;
}

int Query(int l,int r){
int power;
for (power=0;(1<<(power+1))<r-l+1;power++) ;
//printf("power=%d\n",power);
return max(d[l][power],d[r-(1<<power)+1][power]);
}

namespace test{
void OutputArrD(){
REP(i,1,n)
for (int j=0;i+(1<<j)-1<=n;j++) {
printf("d[%d][%d]=%d\n",i,j,d[i][j]);
}
}
}

int main(){
scanf("%d",&n);
REP(i,1,n) scanf("%d",&a[i]);
RMQ();
//test::OutputArrD();
scanf("%d",&m);
while (m--){
int l,r;
scanf("%d%d",&l,&r);
printf("%d\n",Query(l,r));
}
return 0;
}

const
ch:array[0..18]of longint=(1,2,4,8,16,32,64,128,256,512,1024,2048,4096,8192,16384,32768,65536,131072,262144);
var
f:array[1..200000,0..18]of longint;
i,j,k,ans,m,n,l,r:longint;

function max(a,b:longint):longint;
begin if a>b then exit(a) else exit(b);end;

Begin
readln(n);
for i:=1 to n do read(f[i,0]);
for j:=1 to trunc(ln(n)/ln(2)) do
for i:=1 to n-ch[j]+1 do
f[i,j]:=max(f[i,j-1],f[i+ch[j-1],j-1]);
readln(m);
for j:=1 to m do
begin
readln(l,r);
k:=trunc(ln(r-l+1)/ln(2));
ans:=max(f[l,k],f[r-ch[k]+1,k]);
writeln(ans);
end;
End.

跪求9ms的代码= =……

线段树 比rmq 还快

为什么**RMQ**这木慢，呜呜呜~~~
还是过了，AC万岁>.<

编译成功
测试数据 #0: Accepted, time = 7 ms, mem = 17268 KiB, score = 10
测试数据 #1: Accepted, time = 0 ms, mem = 17264 KiB, score = 10
测试数据 #2: Accepted, time = 0 ms, mem = 17264 KiB, score = 10
测试数据 #3: Accepted, time = 15 ms, mem = 17272 KiB, score = 10
测试数据 #4: Accepted, time = 62 ms, mem = 17268 KiB, score = 10
测试数据 #5: Accepted, time = 62 ms, mem = 17268 KiB, score = 10
测试数据 #6: Accepted, time = 109 ms, mem = 17268 KiB, score = 10
测试数据 #7: Accepted, time = 140 ms, mem = 17264 KiB, score = 10
测试数据 #8: Accepted, time = 140 ms, mem = 17264 KiB, score = 10
测试数据 #9: Accepted, time = 156 ms, mem = 17264 KiB, score = 10
Accepted, time = 691 ms, mem = 17272 KiB, score = 100

没敢开math库，写的有点恶心，誒........

var t,x,y,i,j,m,n,p,q,l:longint;
f:array[0..200050,0..20] of longint;

function max(i,j:longint):longint;
begin
if i>j then exit(i) else exit(j);
end;

begin
readln(n);
for i:=1 to n do read(f[i,0]);
readln(m);
p:=1;
q:=0;
while p shl 1<=n do begin
p:=p shl 1;
inc(q);
end;
i:=0;
p:=1;
while i<=q do begin
inc(i);
t:=n-p shl 1+1;
for j:=1 to t do f[j,i]:=max(f[j,i-1],f[j+p,i-1]);
p:=p shl 1;
end;
for i:=1 to m do begin
readln(x,y);
l:=y-x+1;
p:=1;
q:=0;
while p*2<=l do begin
p:=p shl 1;
inc(q);
end;
writeln(max(f[x,q],f[x+l-p,q]));
end;
end.

一个裸的st就可以了。。。
编译成功

测试数据 #0: Accepted, time = 3 ms, mem = 49160 KiB, score = 10
测试数据 #1: Accepted, time = 3 ms, mem = 49160 KiB, score = 10
测试数据 #2: Accepted, time = 3 ms, mem = 49160 KiB, score = 10
测试数据 #3: Accepted, time = 36 ms, mem = 49160 KiB, score = 10
测试数据 #4: Accepted, time = 48 ms, mem = 49160 KiB, score = 10
测试数据 #5: Accepted, time = 63 ms, mem = 49160 KiB, score = 10
测试数据 #6: Accepted, time = 66 ms, mem = 49160 KiB, score = 10
测试数据 #7: Accepted, time = 71 ms, mem = 49160 KiB, score = 10
测试数据 #8: Accepted, time = 90 ms, mem = 49160 KiB, score = 10
测试数据 #9: Accepted, time = 90 ms, mem = 49160 KiB, score = 10
Accepted, time = 478 ms, mem = 49160 KiB, score = 100

st主要部分：
procedure st;
begin
k:=trunc(ln(n)/ln(2));
for j:=1 to k do
for i:=1 to n-1 shl j+1 do
begin
fmax[i,j]:=max(fmax[i,j-1],fmax[i+1 shl (j-1),j-1]);
end;
end;

快排+搜索

├ 测试数据 01：答案正确... (25ms, 3708KB)

├ 测试数据 02：答案正确... (75ms, 3708KB)

├ 测试数据 03：答案正确... (71ms, 3708KB)

├ 测试数据 04：答案正确... (114ms, 3708KB)

├ 测试数据 05：答案正确... (107ms, 3708KB)

├ 测试数据 06：答案正确... (130ms, 3708KB)

├ 测试数据 07：答案正确... (130ms, 3708KB)

├ 测试数据 08：答案正确... (110ms, 3708KB)

├ 测试数据 09：答案正确... (157ms, 3708KB)

├ 测试数据 10：答案正确... (239ms, 3708KB)

type

intt=record

data:int64;

num:longint;

end;

var

a:array[1..200000] of intt;

ii,jj,n,m,k1,k2:longint;

procedure sort(l,r:longint);

var

i,j,x:longint;

y:intt;

begin

i:=l;

j:=r;

x:=a[(l+r) div 2].data;

repeat

while a[i].dataj;

if l

编译通过...

├ 测试数据 01：答案正确... 0ms

├ 测试数据 02：答案正确... 0ms

├ 测试数据 03：答案正确... 0ms

├ 测试数据 04：答案正确... 0ms

├ 测试数据 05：答案正确... 9ms

├ 测试数据 06：答案正确... 0ms

├ 测试数据 07：答案正确... 0ms

├ 测试数据 08：答案正确... 56ms

├ 测试数据 09：答案正确... 134ms

├ 测试数据 10：答案正确... 87ms

---|---|---|---|---|---|---|---|-

Accepted 有效得分：100 有效耗时：286ms

咋就秒不了

type

ele=record

l,r,v:int64;

end;

var

tree:array[0..800001]of ele;

n,m,k,i,j,a,b,c:longint;

function max(a,b:int64):int64;

begin if a>b then max:=a else max:=b;end;

function inq(l,r,p:longint):int64;

var

z:longint;

begin

if (l=tree[p].l)and(r=tree[p].r) then exit(tree[p].v);

z:=(tree[p].l+tree[p].r) shr 1;

if l>z then exit(inq(l,r,p shl 1+1));

if r

ST的复杂度是O(nlogn)

我还用了一种方法，是用一棵二叉树存储二分的结果，再用类似线段树插入删除的方式查询，不知是不是神牛说的线段树做法（其实那棵树不算线段树吧，都不用插入删除），复杂度是O(mlogn)

这里m小的可怜，所以ST在这里无用武之地了。。

用指针和动态内存方式写了棵树，结果时间比ST还悲剧T-T

编译通过...

├ 测试数据 01：答案正确... 0ms

├ 测试数据 02：答案正确... 0ms

├ 测试数据 03：答案正确... 0ms

├ 测试数据 04：答案正确... 0ms

├ 测试数据 05：答案正确... 0ms

├ 测试数据 06：答案正确... 0ms

├ 测试数据 07：答案正确... 0ms

├ 测试数据 08：答案正确... 0ms

├ 测试数据 09：答案正确... 0ms

├ 测试数据 10：答案正确... 0ms

快排竟然秒杀

...............................（无语中）