/ Vijos / 题库 / 天才的记忆 /

题解

140 条题解

  • 2
    @ 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;
}
  • 2
    @ 2017-10-31 14:40:58

    为什么桶分RMQ比st还快

    #include<cstdio>
using namespace std;
#define max(a,b) a>b?a:b
inline int readInt(void){
    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 read(void);
void solve(void);

void read(void);
void solve(void);

int main(void){
    read();
    solve();
    return 0;
}
void read(void){
    n=readInt();
    for(int i=1;i<=n;i++){a[i]=readInt();}
}
void solve(void){
    inin();
//  for(int i=1;i<n;i++){
//      printf("$t[%d]:=%d $\n",i,t[i]);
//  }
    m=readInt();int x,y;
    for(int i=1;i<=m;i++){x=readInt();y=readInt();printf("%d\n",query(x,y));}
}
//
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;
inline int readInt(void){
    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 read(void);
void solve(void);

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

    感觉应该是错的ST

    #include<cstdio>

using namespace std;
#define max(a,b) a>b?a:b
//st
const int MAX=5e5;
inline int readInt(void){
    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 read(void);
void solve(void);

int main(void){
    read();
    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();
    m=readInt();int x,y;
    for(int i=1;i<=m;i++)
    {x=readInt();y=readInt();printf("%d\n",query(x,y));}
}
void read(void){
    n=readInt();
    for(int i=1;i<=n;i++){a[i]=readInt();}
}
  • 2
    @ 2016-05-14 11:47:30 
    __________________________________________________
记录信息
评测状态    Accepted
题目  P1514 天才的记忆
递交时间    2016-05-14 11:46:18
代码语言    C++
评测机 ShadowShore
消耗时间    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++
评测机 ShadowShore
消耗时间    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++
评测机 ShadowShore
消耗时间    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;
}
  • 1
    @ 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]);
    }
    inline int read(){
    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(){
    n=read();
    for(int i=1;i<=n;i++){
    a[i]=read();
    }
    init();
    q=read();
    while(q--){
    int tl,tr;
    tl=read();tr=read();
    write(RMQ(tl,tr));
    putchar('\n');
    }
    return 0;
    }
    //比楼下的各位写线段树的快一些，因为o（1）查询
    //比写稀疏表的也快是因为我加了读入优化输出优化23333

  • 1
    @ 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;
inline char gc(){if(A==B){B=(A=ss)+fread(ss,1,1<<17,stdin);if(A==B)return EOF;}return*A++;}
template<class T>inline void read(T&x){
    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){
    if(l==r){read(tr[rt]);return;}
    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");
    read(n);
    Build(1,1,n);
    read(m);
    while(m--){
        int x,y;
        read(x);read(y);
        printf("%d\n",getmax(1,1,n,x,y));
    }
return 0;
}

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

  • 1
    @ 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));
        }
    }
}
  • 0
    @ 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];

    inline int read(){
    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(){
    n=read();
    for(int i=1;i<=n;++i) f[i][0]=read();
    m=read();
    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--){
    l=read(),r=read();
    int s=logn[r-l+1],x=r-(1<<s)+1;
    printf("%d\n",max(f[l][s],f[x][s]));
    }return 0;
    }

  • 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;
}
  • 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;
}
  • 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;
}
  • 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;
}
  • 0
    @ 2018-02-10 19:07:59

    。

  • 0
    @ 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));
    }
    }
    ```

  • 0
    @ 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;
}
  • 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;
    }

  • 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;
}
  • 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;
}
  • 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);
    }
    }

  • 0
    @ 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;
    }

  • 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
分类
其他 | RMQ 点击显示
标签
(无)
递交数
4976
已通过
1195
通过率
24%
被复制
3
上传者
  1. 关于
  2. 联系我们
  3. 隐私
  4. 服务条款
  5. 版权申诉
  6. Language
  1. © 2005 - 2023 Vijos.org
  2. uibuild-2f1065f
  3. 沪ICP备14040537号-1