# 140 条题解

• @ 2019-10-01 11:20:17

segmentTreeO(nlogn)预处理+O(logn)查询,实测速度高于ST表。
~~(某神仙:线段树是最容易手滑的数据结构)~~

``````#include <iostream>

using namespace std;

const int maxn=210000,inf=0x3f3f3f3f;
int a[maxn];
struct stree{
int val[maxn<<2];
void build(int p, int lp, int rp) {
if(lp==rp) { val[p]=a[lp]; return; }
int mid=(lp+rp)>>1;
build(p<<1,lp,mid);
build(p<<1|1,mid+1,rp);
val[p]=max(val[p<<1],val[p<<1|1]);
}
int query(int p, int lp, int rp, int l, int r) {
if(l<=lp&&rp<=r) return val[p];
int mid=(lp+rp)>>1,ans=-inf;
if(l<=mid) ans=query(p<<1,lp,mid,l,r);
if(r>mid) ans=max(ans,query(p<<1|1,mid+1,rp,l,r));
return ans;
}
}t;

int main() {
ios::sync_with_stdio(false);
int n,m,l,r;
cin>>n;
for(int i=1; i<=n; i++) cin>>a[i];
t.build(1,1,n);
cin>>m;
while(m--) {
cin>>l>>r;
cout<<t.query(1,1,n,l,r)<<endl;
}
return 0;
}
``````

ST表解法 O(nlogn)预处理+O(1)查询,实测速度慢于segmentTree：
~~(为什么窝感觉ST表比segmentTree更容易手滑的亚子)~~

``````#include <cstdio>
#include <iostream>
#include <cmath>

using namespace std;

const int maxn=200010,maxt=30;
int f[maxn][maxt],a[maxn],n;
inline void prework() {
int t=log(n)/log(2);
for(int i=1; i<=n; i++) f[i][0]=a[i];
for(int l=1; l<=t; l++)
for(int i=1; i+(1<<l)<=n+1; i++)
f[i][l]=max(f[i][l-1],f[i+(1<<(l-1))][l-1]);
}

inline int qry(int l, int r) {
int le=log(r-l+1)/log(2);
return max(f[l][le],f[r-(1<<le)+1][le]);
}

int main() {
int m,l,r;
scanf("%d", &n);
for(int i=1; i<=n; i++) scanf("%d",a+i);
prework();
scanf("%d",&m);
while(m--) {
scanf("%d %d", &l, &r);
printf("%d\n", qry(l,r));
}
return 0;
}

``````
• @ 2017-10-31 14:40:58

为什么桶分RMQ比st还快

``````#include<cstdio>
using namespace std;
#define max(a,b) a>b?a:b
int num=0;char c=getchar();int f=1;
while(c<'0'||c>'9') {if(c=='-')f=-1;c=getchar();}
while(c>='0'&&c<='9') {num=num*10+c-'0';c=getchar();}
return num*f;
}
const int INF=1000000000;
const int MAX=1e6;
int b[MAX+10];
int a[MAX+10];
void inin(void);
int query(int,int);
void update(int x,int v);
int k;
int n,m;
void solve(void);

void solve(void);

int main(void){
solve();
return 0;
}
}
void solve(void){
inin();
//  for(int i=1;i<n;i++){
//      printf("\$t[%d]:=%d \$\n",i,t[i]);
//  }
}
//
void inin(void){
k=0;
while((k+1)*(k+1)<=n) k++;
int c=1;
int d=n/k;
for(int i=0;i<d;i++){
//  printf("* l:=%d r:=%d *\n",i*k+1,i*k+k);
for(int j=1;j<=k;j++){
b[i]=max(b[i],a[i*k+j]);
}
}c=d*k+1;
for(;c<=n;c++) b[d]=max(b[d+1],a[c]);
}
int query(int l,int r){
int d=(l/k);
int ql=d+1;
int qr=(r/k);
int i=l;
int _max=-INF;
while(i<=ql*k&&i<=r){_max=max(_max,a[i]);i++;}
while(i<=qr*k&&i<=r){_max=max(_max,b[i/k]);i+=k;}
while(i<=r){_max=max(_max,a[i]);i++;}
return _max;
}
void update(int x,int v){
a[x]=v;b[x/k]=(b[x/k],a[x]);
}
``````

一开始蜜汁超时的线段树

``````#include<cstdio>

using namespace std;
#define max(a,b) a>b?a:b
//Sgt
const int MAX=5e5;
int num=0;char c=getchar();int f=1;
while(c<'0'||c>'9'){if(c=='-')f=-1;c=getchar();}
while(c>='0'&&c<='9'){num=num*10+c-'0';c=getchar();}
return f*num;
}
int INF=1000000000;
int n;int m;
int ql,qr;
//
int a[MAX+10];
int t[MAX+10];

int _query(int o,int l,int r){
int ls=o<<1;int rs=ls+1;
int _max=-INF;
if(ql<=l&&r<=qr){_max=max(_max,t[o]);}
else{
int mid=l+r>>1;
if(ql<=mid){_max=max(_query(ls,l,mid),_max);}
if(qr> mid){_max=max(_query(rs,mid+1,r),_max);}
}
//  printf("\$ ql=%d qr=%d o=%d l=%d r=%d _max=%d &\n",ql,qr,o,l,r,_max);
return _max;

}
inline int query(int l,int r){
ql=l;qr=r;
return _query(1,1,n);
}
void inin(int o,int l,int r){
//  printf("& o:=%d l:=%d r:=%d &\n",o,l,r);
int ls=o<<1;int rs=ls+1;int mid=l+r>>1;
if(l==r){t[o]=a[l];}
else{
inin(ls,l,mid);
inin(rs,mid+1,r);
t[o]=max(t[ls],t[rs]);
}

}
void solve(void);

int main(void){
solve();
return 0;
}
}
void solve(void){
inin(1,1,n);
//  for(int i=1;i<n;i++){
//      printf("\$t[%d]:=%d \$\n",i,t[i]);
//  }
}

``````

感觉应该是错的ST

``````#include<cstdio>

using namespace std;
#define max(a,b) a>b?a:b
//st
const int MAX=5e5;
int num=0;char c=getchar();int f=1;
while(c<'0'||c>'9'){if(c=='-')f=-1;c=getchar();}
while(c>='0'&&c<='9'){num=num*10+c-'0';c=getchar();}
return f*num;
}
int dp[MAX+10][30];
int a[MAX+10];
int n,m;
void inin(void);
int query(int l,int r);
void solve(void);

int main(void){
solve();
return 0;
}
void inin(void){
for(int i=1;i<=n;i++)dp[i][0]=a[i];
for(int j=1;(1<<j)<=n;j++) for(int i=1;i<=n;i++)
dp[i][j]=max(dp[i][j-1],dp[i+(1<<(j-1))][j-1]);
}
int query(int l,int r){
int k=0;
while(l+(1<<(k+1))<=r)k++;
return max(dp[l][k],dp[r+1-(1<<k)][k]);
}
void solve(void){
inin();
for(int i=1;i<=m;i++)
}
}
``````
• @ 2016-05-14 11:47:30
``````__________________________________________________
记录信息
评测状态    Accepted
题目  P1514 天才的记忆
递交时间    2016-05-14 11:46:18
代码语言    C++
消耗时间    2793 ms
消耗内存    2068 KiB
评测时间    2016-05-14 11:46:22
评测结果
编译成功

测试数据 #0: Accepted, time = 0 ms, mem = 2060 KiB, score = 10
测试数据 #1: Accepted, time = 15 ms, mem = 2060 KiB, score = 10
测试数据 #2: Accepted, time = 0 ms, mem = 2060 KiB, score = 10
测试数据 #3: Accepted, time = 46 ms, mem = 2068 KiB, score = 10
测试数据 #4: Accepted, time = 156 ms, mem = 2064 KiB, score = 10
测试数据 #5: Accepted, time = 312 ms, mem = 2064 KiB, score = 10
测试数据 #6: Accepted, time = 390 ms, mem = 2068 KiB, score = 10
测试数据 #7: Accepted, time = 390 ms, mem = 2068 KiB, score = 10
测试数据 #8: Accepted, time = 609 ms, mem = 2068 KiB, score = 10
测试数据 #9: Accepted, time = 875 ms, mem = 2064 KiB, score = 10
Accepted, time = 2793 ms, mem = 2068 KiB, score = 100
代码
#include <cstdio>
int main() {
int c[200001],d[200001],m,n,a,b;
scanf("%d",&n);
for (int i = 1;i <= n;i++)
scanf("%d",&c[i]);
scanf("%d",&m);
for (int i = 1;i <= m;i++) {
scanf("%d%d",&a,&b);
d[i] = c[a];
for (int j = a;j <= b;j++)
if (c[j] > d[i]) d[i] = c[j];
}
for (int i = 1;i <= m;i++)
printf("%d\n",d[i]);
return 0;
}
__________________________________________________
记录信息
评测状态    Accepted
题目  P1514 天才的记忆
递交时间    2016-07-04 13:22:40
代码语言    C++
消耗时间    622 ms
消耗内存    2072 KiB
评测时间    2016-07-04 13:22:42
评测结果
编译成功

测试数据 #0: Accepted, time = 0 ms, mem = 2072 KiB, score = 10
测试数据 #1: Accepted, time = 0 ms, mem = 2072 KiB, score = 10
测试数据 #2: Accepted, time = 0 ms, mem = 2072 KiB, score = 10
测试数据 #3: Accepted, time = 15 ms, mem = 2068 KiB, score = 10
测试数据 #4: Accepted, time = 31 ms, mem = 2072 KiB, score = 10
测试数据 #5: Accepted, time = 78 ms, mem = 2068 KiB, score = 10
测试数据 #6: Accepted, time = 93 ms, mem = 2068 KiB, score = 10
测试数据 #7: Accepted, time = 78 ms, mem = 2068 KiB, score = 10
测试数据 #8: Accepted, time = 140 ms, mem = 2072 KiB, score = 10
测试数据 #9: Accepted, time = 187 ms, mem = 2072 KiB, score = 10
Accepted, time = 622 ms, mem = 2072 KiB, score = 100
代码
#include <algorithm>
#include <cstdio>
using std :: sort;
int n,m;
struct T {int a,num;}s[200001];
inline bool cmp(T x,T y) {return x.a > y.a;}
int main() {
scanf("%d",&n);
for (int i = 1;i <= n;i++) {
scanf("%d",&s[i].a);
s[i].num = i;
}
sort(s+1,s+n+1,cmp);
scanf("%d",&m);
for (int i = 1,l,r,j;i <= m;i++) {
scanf("%d%d",&l,&r);
for (j = 1;j <= n;j++)
if (s[j].num <= r && s[j].num >= l) break;
printf("%d\n",s[j].a);
}
return 0;
}
__________________________________________________
记录信息
评测状态    Accepted
题目  P1514 天才的记忆
递交时间    2016-07-24 10:04:10
代码语言    C++
消耗时间    700 ms
消耗内存    9948 KiB
评测时间    2016-07-24 10:04:12
评测结果
编译成功

测试数据 #0: Accepted, time = 0 ms, mem = 9948 KiB, score = 10
测试数据 #1: Accepted, time = 15 ms, mem = 9944 KiB, score = 10
测试数据 #2: Accepted, time = 0 ms, mem = 9944 KiB, score = 10
测试数据 #3: Accepted, time = 15 ms, mem = 9948 KiB, score = 10
测试数据 #4: Accepted, time = 31 ms, mem = 9944 KiB, score = 10
测试数据 #5: Accepted, time = 78 ms, mem = 9944 KiB, score = 10
测试数据 #6: Accepted, time = 109 ms, mem = 9948 KiB, score = 10
测试数据 #7: Accepted, time = 125 ms, mem = 9948 KiB, score = 10
测试数据 #8: Accepted, time = 156 ms, mem = 9948 KiB, score = 10
测试数据 #9: Accepted, time = 171 ms, mem = 9944 KiB, score = 10
Accepted, time = 700 ms, mem = 9948 KiB, score = 100
代码
#include <bits/stdc++.h>
using std :: max;
const int INF = 999999999;
long maxV= -INF;
struct Node {
long L,R,maxV;
long Mid() { return (L+R)/2; }
};
Node tree[800010];
void BuildTree(long root,long L,long R) {
tree[root].L = L;
tree[root].R = R;
tree[root].maxV = -INF;
if (L != R) {
BuildTree(2*root+1,L,(L+R)/2);
BuildTree(2*root+2,(L+R)/2 + 1, R);
}
}
void Insert(long root,long i,long v) {
if (tree[root].L == tree[root].R) {
tree[root].maxV= v;
return;
}
tree[root].maxV= max(tree[root].maxV,v);
if (i <= tree[root].Mid()) Insert(2*root+1,i,v);
else Insert(2*root+2,i,v);
}
void Query(long root,long s,long e) {
if (tree[root].maxV <= maxV) return;
if (tree[root].L == s && tree[root].R == e) {
maxV= max(maxV,tree[root].maxV);
return;
}
if (e <= tree[root].Mid()) Query(2*root+1,s,e);
else if(s > tree[root].Mid()) Query(2*root+2,s,e);
else {
Query(2*root+1,s,tree[root].Mid());
Query(2*root+2,tree[root].Mid()+1,e);
}
}
int main() {
long n,m;
scanf("%ld",&n);
BuildTree(0,1,n);
for (long i = 1,x;i <= n;i++) {
scanf("%ld",&x);
Insert(0,i,x);
}
scanf("%ld",&m);
for (long i = 1;i <= m;i++) {
long s,e;
scanf("%ld%ld",&s,&e);
maxV= -INF;
Query(0,s,e);
printf("%ld\n",maxV);
}
return 0;
}
``````
• @ 2017-07-23 11:14:38

# 状态 耗时 内存占用

#1 Accepted 3ms 324.0KiB
#2 Accepted 4ms 904.0KiB
#3 Accepted 6ms 2.867MiB
#4 Accepted 10ms 5.93MiB
#5 Accepted 17ms 6.41MiB
#6 Accepted 27ms 13.531MiB
#7 Accepted 37ms 17.672MiB
#8 Accepted 36ms 17.691MiB
#9 Accepted 68ms 23.977MiB
#10 Accepted 62ms 23.887MiB
//st表又名稀疏表，黑科技啊！
#include<iostream>
#include<cstdio>
#include<cmath>
using namespace std;
#define size 200001
int a[size],n,q,st[size][30];
void init(){
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)<=n+1;i++){
st[i][j]=max(st[i][j-1],st[i+(1<<(j-1))][j-1]);
}
}
}
inline int RMQ(int x,int y){
int k=log(y-x+1)/log(2.0);
return max(st[x][k],st[y-(1<<k)+1][k]);
}
int data=0,w=1;char ch=0;
while(ch!='-'&&(ch<'0'||ch>'9')) ch=getchar();
if(ch=='-') w=-1,ch=getchar();
while(ch>='0'&&ch<='9') data=data*10+ch-'0',ch=getchar();
return data*w;
}
inline void write(int x){
if(x<0) putchar('-'),x=-x;
if(x>9) write(x/10);
putchar(x%10+'0');
}
int main(){
for(int i=1;i<=n;i++){
}
init();
while(q--){
int tl,tr;
write(RMQ(tl,tr));
putchar('\n');
}
return 0;
}
//比楼下的各位写线段树的快一些，因为o（1）查询
//比写稀疏表的也快是因为我加了读入优化输出优化23333

• @ 2017-03-12 08:51:31
``````#include<cstdio>
#define re register int
#define File(s) freopen(s".in","r",stdin),freopen(s".out","w",stdout)
#define Debug(x) std::cerr<<#x<<"="<<x<<"\n"
typedef long long ll;
char ss[1<<17],*A=ss,*B=ss;
static char c;x=0;int y=1;
while(c=gc(),c!='-'&&(c<'0'||'9'<c));
if(c=='-')y=-1;else x=c-'0';
while(c=gc(),'0'<=c&&c<='9')x=x*10+c-'0';
x*=y;
}
//---------------------------True Code----------------------------
const int N=2e5;
int n,m,tr[4*N];
inline int max(int a,int b){return a>b?a:b;}
void Build(int rt,int l,int r){
int m=(l+r)>>1;
Build(rt<<1,l,m);Build(rt<<1|1,m+1,r);
tr[rt]=max(tr[rt<<1],tr[rt<<1|1]);
}
int getmax(int rt,int l,int r,int a,int b){
if(a<=l&&r<=b)return tr[rt];
int m=(l+r)>>1;
if(b<=m)return getmax(rt<<1,l,m,a,b);
else if(a>m)return getmax(rt<<1|1,m+1,r,a,b);
else return max(getmax(rt<<1,l,m,a,b),getmax(rt<<1|1,m+1,r,a,b));
}
int main(){
File("talentm");
Build(1,1,n);
while(m--){
int x,y;
printf("%d\n",getmax(1,1,n,x,y));
}
return 0;
}
``````

最骚的是负数了，读入优化打炸了

• @ 2017-01-13 19:58:21

RMQ

``````#include <cmath>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <iomanip>
#include <iostream>
#include <algorithm>
#include <vector>
#include <deque>
#include <set>
#include <limits>
#include <string>
#include <sstream>
using namespace std;

const int oo_min=0xcfcfcfcf,oo_max=0x3f3f3f3f;

int n,m;
int a[262144+1];
int rmq[262144+1][18+1];

void pr_rmq_max_1()
{
for (int i=1;i<=n;i++)
rmq[i][0]=a[i];
for (int i=1;i<=log2(n);i++)
for (int j=1;j<=n;j++)
rmq[j][i]=max(rmq[j][i-1],((j+(1<<(i-1))<=n)?rmq[j+(1<<(i-1))][i-1]:oo_min));
}

int rmq_max_1(int l,int r)
{
int temp=int(log2(r-l+1));
return max(rmq[l][temp],rmq[r-(1<<temp)+1][temp]);
}

int main()
{
while (~scanf("%d",&n))
{
for (int i=1;i<=n;i++)
scanf("%d",&a[i]);
pr_rmq_max_1();
scanf("%d",&m);
for (int i=1;i<=m;i++)
{
int l,r;
scanf("%d%d",&l,&r);
printf("%d\n",rmq_max_1(l,r));
}
}
}
``````

Segment Tree

``````#include <cmath>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <iomanip>
#include <algorithm>
#include <vector>
#include <deque>
#include <limits>
#include <string>
#include <sstream>
using namespace std;

const int oo_min=0xcfcfcfcf,oo_max=0x3f3f3f3f;

struct segment_tree_1
{
int l,r,mid,x;
}st[2*262144+2];

int n,m;
int a[262144+1];

void build_segment_tree_1(int p,int l,int r)
{
st[p].l=l,st[p].r=r,st[p].mid=(l+r)/2;
if (l<r)
{
if (l<=st[p].mid)
build_segment_tree_1(p*2,l,st[p].mid);
if (st[p].mid+1<=r)
build_segment_tree_1(p*2+1,st[p].mid+1,r);
}
if (l==r)
st[p].x=a[l];
else
st[p].x=max(st[p*2].x,st[p*2+1].x);
}

int sum_1(int p,int l,int r)
{
if (st[p].l==l&&st[p].r==r)
return st[p].x;
else if (r<=st[p].mid)
return sum_1(p*2,l,r);
else if (l>=st[p].mid+1)
return sum_1(p*2+1,l,r);
else
return max(sum_1(p*2,l,st[p].mid),sum_1(p*2+1,st[p].mid+1,r));
}

int main()
{
while (~scanf("%d",&n))
{
for (int i=1;i<=n;i++)
scanf("%d",&a[i]);
build_segment_tree_1(1,1,n);
scanf("%d",&m);
for (int i=1;i<=m;i++)
{
int l,r;
scanf("%d%d",&l,&r);
printf("%d\n",sum_1(1,l,r));
}
}
}
``````
• @ 2022-05-02 19:48:10

#include<bits/stdc++.h>
using namespace std;
const int N=2e5+1;
int n,m,l,r,logn[N],f[N][30];

int x=0,f=1;char ch=getchar();
while(ch<'0'||ch>'9'){if (ch=='-') f=-1;ch=getchar();}
while(ch>='0'&&ch<='9'){x=x*10+ch-48;ch=getchar();}
return x*f;
}int main(){
for(int i=1;i<=20;++i)
for(int j=1;j+(1<<i)-1<=n;++j) f[j][i]=max(f[j][i-1],f[j+(1<<i-1)][i-1]);
for(int i=2;i<=n;++i) logn[i]=logn[i/2]+1;
while(m--){
int s=logn[r-l+1],x=r-(1<<s)+1;
printf("%d\n",max(f[l][s],f[x][s]));
}return 0;
}

• @ 2019-04-05 19:57:38

#1 Accepted 1ms 324.0 KiB
#2 Accepted 2ms 456.0 KiB
#3 Accepted 3ms 580.0 KiB
#4 Accepted 9ms 2.973 MiB
#5 Accepted 17ms 3.094 MiB
#6 Accepted 28ms 4.762 MiB
#7 Accepted 32ms 3.516 MiB
#8 Accepted 33ms 3.504 MiB
#9 Accepted 49ms 7.582 MiB
#10 Accepted 50ms 6.355 MiB

``````#include<cstdio>
#include<algorithm>
#define max std::max
const int maxn=2e5+10;
struct node{
int l,r,v;
}tree[maxn*4];
void build(int rt,int l,int r){
tree[rt].l=l;
tree[rt].r=r;
if (l==r){
scanf("%d",&tree[rt].v);
return;
}
int mid=(l+r)>>1;
build(rt<<1,l,mid);
build(rt<<1|1,mid+1,r);
tree[rt].v=max(tree[rt<<1].v,tree[rt<<1|1].v);
}
void update(int rt,int a,int b){
int l=tree[rt].l,r=tree[rt].r;
if (l==r){
tree[rt].v=b;
return;
}
int mid=(l+r)>>1;
if (mid>=a) update(rt<<1,a,b);
else update(rt<<1|1,a,b);
tree[rt].v=max(tree[rt<<1].v,tree[rt<<1|1].v);
}
int query(int rt,int a,int b){
int l=tree[rt].l,r=tree[rt].r;
if (l==a&&r==b)
return tree[rt].v;
int mid=(l+r)>>1;
if (mid>=b) return query(rt<<1,a,b);
else if(mid<a) return query(rt<<1|1,a,b);
else return max(query(rt<<1,a,mid),
query(rt<<1|1,mid+1,b));
}
int main(){
int n;
scanf("%d",&n);
build(1,1,n);
int m;
scanf("%d",&m);
while (m--){
int a,b;
scanf("%d%d",&a,&b);
printf("%d\n",query(1,a,b));
}
return 0;
}
``````
• @ 2019-04-05 12:54:58

貌似是ST裸题吧，不过其实到现在为止不知道为啥f数组可以开f[200200][19]这个19怎么肥死

``````#include <iostream>
#include <algorithm>
#include <cstdio>
using namespace std;
#define maxn 200200
int a[maxn],Log[maxn],f[maxn][20];
int n,m;
int main()
{
cin>>n;
for(int i=1;i<=n;i++) cin>>a[i];
Log[1]=0;
f[1][0]=a[1];
for(int i=2;i<=n;i++)
{
Log[i]=Log[i>>1]+1;
f[i][0]=a[i];
}
for(int j=1;(1<<j)<=n;j++)
for(int i=1;i+(1<<(j-1))<=n;i++)
f[i][j]=max(f[i][j-1],f[i+(1<<(j-1))][j-1]);
cin>>m;
for(int i=1;i<=m;i++)
{
int left,right;
cin>>left>>right;
int len=Log[right-left+1];
int ans=max(f[left][len],f[right-(1<<len)+1][len]);
cout<<ans<<endl;
}
return 0;
}

``````
• @ 2018-04-04 20:19:19

用st算法解决的，不知道为什么总是提醒我runningtime error，于是把dp中以2为步长改为以4为步长，压缩了一半的空间，总算通过了。运行时间应该没有多大的变化，依然是预处理O(nlgn),查询时间O(1)

``````#include<stdio.h>
#define NUM1 200001
#define NUM3 9
int FINDMAX(int a,int b)
{
if (a>=b) return a; else return b;
}
int main()
{
int number[NUM1];
int max[NUM1][NUM3];
int n,i,j,k;
scanf("%d",&n);
for (i=0;i<n;i++)
scanf("%d",&number[i]);
i=1;k=0;
while (i<=n)
{
if (i==1)
for (j=0;j<n;j++)
max[j][0]=number[j];
else
{
for (j=0;j<n;j++)
if (j+i-1<n)
{
max[j][k]=FINDMAX(max[j][k-1],max[j+i/4][k-1]);
max[j][k]=FINDMAX(max[j][k],max[j+i/2][k-1]);
max[j][k]=FINDMAX(max[j][k],max[j+i*3/4][k-1]);
}
else
break;
}
i=i*4;
k++;
}
int m,begin,end,length,ma;
scanf("%d",&m);
for (j=0;j<m;j++)
{
scanf("%d%d",&begin,&end);
begin=begin-1;end=end-1;
length=end-begin+1;
i=1;
for (k=0;i<=length;k=k)
{
k++;
i=i*4;
}
k--;i=i/4;
ma=max[begin][k];
if (begin+i*2-1<=end)
ma=FINDMAX(ma,max[begin+i][k]);
if (begin+i*3-1<=end)
ma=FINDMAX(ma,max[begin+2*i][k]);
ma=FINDMAX(ma,max[end-i+1][k]);
printf("%d\n",ma);
}
return 0;
}
``````
• @ 2018-04-04 20:17:30

用st算法解决的，不知道为什么总是提醒我runningtime error，于是把dp中以2为步长改为以4为步长，压缩了一半的空间，总算通过了。运行时间应该没有多大的变化，依然是预处理O(nlgn),查询时间O(1)

``````#include<stdio.h>
#define NUM1 200001
#define NUM3 9
int FINDMAX(int a,int b)
{
if (a>=b) return a; else return b;
}
int main()
{
int number[NUM1];
int max[NUM1][NUM3];
int n,i,j,k;
scanf("%d",&n);
for (i=0;i<n;i++)
scanf("%d",&number[i]);
i=1;k=0;
while (i<=n)
{
if (i==1)
for (j=0;j<n;j++)
max[j][0]=number[j];
else
{
for (j=0;j<n;j++)
if (j+i-1<n)
{
max[j][k]=FINDMAX(max[j][k-1],max[j+i/4][k-1]);
max[j][k]=FINDMAX(max[j][k],max[j+i/2][k-1]);
max[j][k]=FINDMAX(max[j][k],max[j+i*3/4][k-1]);
}
else
break;
}
i=i*4;
k++;
}
int m,begin,end,length,ma;
scanf("%d",&m);
for (j=0;j<m;j++)
{
scanf("%d%d",&begin,&end);
begin=begin-1;end=end-1;
length=end-begin+1;
i=1;
for (k=0;i<=length;k=k)
{
k++;
i=i*4;
}
k--;i=i/4;
ma=max[begin][k];
if (begin+i*2-1<=end)
ma=FINDMAX(ma,max[begin+i][k]);
if (begin+i*3-1<=end)
ma=FINDMAX(ma,max[begin+2*i][k]);
ma=FINDMAX(ma,max[end-i+1][k]);
printf("%d\n",ma);
}
return 0;
}
``````
• @ 2018-02-10 19:07:59

• @ 2018-02-10 19:07:36

ST表，查询O(1)
```cpp
#include<iostream>
#include<cstdio>
using namespace std;
#define For(i, l, r) for(int i = l; i <= r; ++i)
const int N = 200001;
const int K = 21;

int n, m, a[N], ST[K][N], Log[N];
int Find(int l, int r) {
int x = Log[r - l + 1];
return max(ST[x][l], ST[x][r - (1 << x) + 1]);
}
int main() {
int l, r;
scanf("%d", &n);
For(i, 1, n) scanf("%d", &a[i]);
For(i, 1, n) ST[0][i] = a[i];
For(i, 1, K)
for(int j = 1; j + (1 << i) - 1<= n; ++j)
ST[i][j] = max(ST[i - 1][j], ST[i - 1][j + (1 << (i - 1))]);
for(int i = 1; (1 << i) < N; ++i) Log[1 << i] = i;
For(i, 1, N) if(!Log[i]) Log[i] = Log[i - 1];
scanf("%d", &m);
For(i, 1, m) {
scanf("%d%d", &l, &r);
printf("%d\n", Find(l, r));
}
}
```

• @ 2017-12-19 15:32:54
``````#include <iostream>
using namespace std;

int N, Q;
int D[(1<<18)][18];
int A[(1<<18)];

void RMQ_INIT() {
for(int i=1; i<=N; i++) 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]);
}

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 L, R;
cin >> N;
for(int i=1; i<=N; i++) cin >> A[i];
RMQ_INIT();
cin >> Q;
for(int i=1; i<=Q; i++) {
cin >> L >> R;
cout << RMQ(L, R) << '\n';
}

return 0;
}
``````
• @ 2017-10-03 16:26:42

rmq
#include<iostream>
#include<algorithm>
#include<cstdio>
#define maxa 200000+10
using namespace std;
int a[maxa],d[maxa][20];
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,i,j;
scanf("%d",&n);
for(i=0;i<n;++i)
scanf("%d",&(a[i]));
for(i=0;i<n;++i)
d[i][0] = a[i];
for(j=1;(1<<j)<=n;++j)
for(i=0;i+(1<<j)-1<n;++i)
d[i][j] = max(d[i][j-1],d[i+(1<<(j-1))][j-1]);
int k;
scanf("%d",&k);
while(k--)
{
int L,R;
scanf("%d%d",&L,&R);
printf("%d\n",RMQ(L-1,R-1));
}
return 0;
}

• @ 2017-08-13 17:25:45
``````#include <cstdio>
#include <algorithm>
#include <math.h>
#include <iostream>
using namespace std;
#define hh 200203
int n=0,m=0,a[hh],dp[hh][26];
int lo;
inline int maxx(int a,int b){return a>b?a:b;}
int main()
{
scanf("%d",&n);
lo=(int)(log(n)/log(2))+1;
for(int i=1;i<=n;i++)
{
scanf("%d",&a[i]);
dp[i][0]=a[i];
}
for(int j=1;j<=lo;j++)
{
for(int z=1;z<=n;z++)
{
if(z+(int)pow(2,j-1)<hh)
dp[z][j]=maxx(dp[z][j-1],dp[z+(int)pow(2,j-1)][j-1]);
}
}
scanf("%d",&m);int x,y;
for(int h=1;h<=m;h++)
{
scanf("%d%d",&x,&y);
int mx=(int)(log(y-x+1)/log(2));
printf("%d\n",maxx(dp[x][mx],dp[y-(int)pow(2,mx)+1][mx]));
}
return 0;
}
``````
• @ 2017-07-16 23:52:21

线段树模板

``````#include <cstdio>
#include <cstring>
#include <algorithm>

using namespace std;

const int maxN = 2e5 + 5;
const int maxM = 1e4 + 5;
const int neg_inf = 1 << 31;

int val[maxN];
int seg_max[maxN << 2];
int n, m;

void input_val()
{
scanf("%d", &n);
for(int i = 1; i <= n; i++)
scanf("%d", val + i);
}

//[left, right]
int _build_aux(int id, int left, int right)
{
if(left == right)
return seg_max[id] = val[left];
int mid = (left + right) >> 1;
return seg_max[id] = max(_build_aux(id << 1, left, mid),
_build_aux(id << 1 | 1, mid + 1, right));
}

void build()
{
_build_aux(1, 1, n);
}

int ql, qr; // query range
int _query_aux(int id, int left, int right)
{
if(ql <= left && qr >= right)
return seg_max[id];
else if(qr < left || ql > right)
return neg_inf;
int mid = (left + right) >> 1;
return max(_query_aux(id << 1, left, mid),
_query_aux(id << 1 | 1, mid + 1, right));
}

int query(int _ql, int _qr)
{
ql = _ql;
qr = _qr;
return _query_aux(1, 1, n);
}

int main()
{
input_val();
build();

scanf("%d", &m);
int u, v;
for(int i = 0; i < m; i++)
{
scanf("%d%d", &u, &v);
printf("%d\n", query(u, v));
}

return 0;
}
``````
• @ 2016-11-16 07:27:29

#include<bits/stdc++.h>
using namespace std;
const int MAXN=200005;
int n,m,x,y,a[MAXN];
int f[MAXN][20];
void query(int l,int r)
{
int k=log2(r-l+1);
printf("%d\n",max(f[l][k],f[r-(1<<k)+1][k]));
}
int main()
{
scanf("%d",&n);
for(int i=1;i<=n;i++)scanf("%d",&a[i]);
scanf("%d",&m);
for(int i=1;i<=n;i++)f[i][0]=a[i];
for(int j=1;j<=20;j++){
for(int i=1;i+(1<<j)-1<=n;i++){
f[i][j]=max(f[i][j-1],f[i+(1<<(j-1))][j-1]);
}
}
for(int i=1;i<=m;i++){
scanf("%d%d",&x,&y);
query(x,y);
}
}

• @ 2016-08-27 15:58:38

用RMQ哦！！！
#include<cstdio>
#include<cmath>
#include<algorithm>
using namespace std;
int n,m,x,y,k;
int ans,f[200001][21];
int main()
{
scanf("%d",&n);
for(int i=1;i<=n;i++)
{
scanf("%d",&f[i][0]);
}
for(int j=1;j<=20;j++)
{
for(int i=1;i<=n;i++)
{
if(i+(1<<j)-1<=n)
f[i][j]=max(f[i][j-1],f[i+(1<<(j-1))][j-1]);
}
}
scanf("%d",&m);
for(int i=1;i<=m;i++)
{
scanf("%d%d",&x,&y);
k=log(y-x+1)/log(2);
ans=max(f[x][k],f[y-(1<<k)+1][k]);
printf("%d\n",ans);
}
return 0;
}

• @ 2016-08-15 00:45:31
``````#include<cstdio>
#include<cstring>
#include<cmath>
#include<sstream>
#include<algorithm>
#include<vector>

#define maxN 200010

typedef long long QAQ;
struct Tree{int l,r;QAQ mintr,maxtr;};

Tree tr[maxN<<2];
int arr[maxN];

QAQ Max(QAQ a ,QAQ b){return a>b?a:b;}

void Push_up (int i){
tr[i].maxtr = Max ( tr[i<<1].maxtr , tr[i<<1|1].maxtr);
}

void Build_Tree (int x , int y , int i){
tr[i].l = x ; tr[i].r = y ;
if( x==y )tr[i].maxtr = tr[i].mintr = arr[x] ;
else {
QAQ mid = (tr[i].l + tr[i].r ) >> 1 ;
Build_Tree ( x , mid , i<<1 );
Build_Tree ( mid+1 , y ,i<<1|1);
Push_up ( i );
}
}

QAQ Query_Max ( int q ,int w ,int i ){
if(q<=tr[i].l && w>=tr[i].r )return tr[i].maxtr ;
else {
QAQ mid = (tr[i].l + tr[i].r )>>1;
if(q>mid){
return Query_Max ( q , w , i<<1|1);
}
else if(w<=mid){
return Query_Max ( q , w , i<<1);
}
else {
return Max( Query_Max ( q , w , i<<1) ,Query_Max ( q , w , i<<1|1));
}
}
}

int main(){
int N,M,l,r;
scanf("%d",&N);
for ( int i=1 ; i<=N ; ++i )scanf("%d",&arr[i]);
Build_Tree( 1 , N , 1 );
scanf("%d",&M);
while(M--){
scanf("%d%d",&l,&r);
printf("%I64d\n",Query_Max( l , r , 1));
}
return 0;
}
``````

线段树

ID
1514

6

(无)

4989

1196

24%

2