倍增/ST表/离散化–NOIP 2012 提高组 开车旅行

0x01 写在之前

题目链接:https://www.luogu.org/problemnew/show/P1081

前置技能: ST表 双向链表 倍增 离散化

一看省选/NOI-又是NOIP的题目,我们就大概可以知道这又是一个代码难度较高的高级暴力
▄︻┻┳═一…… ☆<(= ̄□ ̄=!)>

我们将会有以下几种方法优化暴力

  • 转化问题
  • 倍增 / 二分/ 数论优化 反正我是不会
  • 数据结构

那么,先看题目吧

0x02 题目

经过简单的分析题目,我们可以知道,看起来需要预处理了,毕竟看起来并没小于等于$O(m\log(n))$的在线算法

离线的话,倍增和ST表是$O(\log(n))$的

哪我们需要预处理什么呢

  • 我们需要知道在每个点时小A小B分别会前往哪里,已经在$2^j$后到达哪里
  • 以及到达每一步需要的步数

不太好做?

这个时候就应该祭上离散化,在排序并离散化后我们可以快速的通过双向链表快速的求出小A小B将会前往何处及前往的距离

剩下的东西就是ST表的东西了

0x03 代码

#include <cstdio>
#include <algorithm>
const int N=110000;
inline int Aabs(int a){return a>0?a:0-a;}
struct ci{
    int l,r,id,now,hei;
}c[N];
int n,m,pre,nxt,now,ans,p;
int nid[N],next_a[N],next_b[N],sta[N][25],stb[N][25],f[N][25];
long long x,dis_a,dis_b;
double Min=2147483647;
// helper functions start
// cmp(ci a,ci b)
// sort helper functions
// return bool
bool cmp(ci a,ci b){
    return a.hei<b.hei;
}
// fir()
// find tht nearst
// return bool
inline bool fir(){
    if(pre==0) return true;
    if(nxt==0) return false;
    return c[nxt].hei-c[now].hei<c[now].hei-c[pre].hei;
}
// sec(int x,int y)
// find second nearst in a and b
// x > now y < now
// return int
// - the second nearst's id
inline int sec(int x,int y){
    if(x==0) return c[y].id;
    if(y==0) return c[x].id;
    if(c[x].hei-c[now].hei<c[now].hei-c[y].hei) return c[x].id;
    else return c[y].id;
}
// get_dis(long long x,int p)
// Get the dis_a ans dis_b
// - x the Max distance
// - p start
// return void
inline void get_dis(long long x,int p){
    dis_a=dis_b=0;
    for(int j=20;j>=0;j--){
        if(f[p][j]&&(long long)dis_a+dis_b+sta[p][j]+stb[p][j]<=x){
            dis_a+=sta[p][j];
            dis_b+=stb[p][j];
            p=f[p][j];
        }
    }
    if(next_a[p]&&dis_a+dis_b+sta[p][0]<=x) dis_a+=sta[p][0];
}
// helper funtions end
// readin()
// readin
inline void readin(){
    scanf("%d",&n);
    for(int i=1;i<=n;i++){
        scanf("%d",&c[i].hei);
        c[i].id=i;
    }
}
// init()
// find pre and nxt / Discretization
inline void init(){
    std::sort(c+1,c+n+1,cmp);
    for(int i=1;i<=n;i++){
        nid[c[i].id]=i;
        c[i].l=i-1;
        c[i].r=i+1;
    }
    c[1].l=c[n].r=0;
    for(int i=1;i<=n;i++){
        now=nid[i];pre=c[now].l;nxt=c[now].r;
        if(fir()) next_b[i]=c[nxt].id,next_a[i]=sec(c[nxt].r,pre);
        else next_b[i]=c[pre].id,next_a[i]=sec(nxt,c[pre].l);
        if(pre) c[pre].r=nxt;
        if(nxt) c[nxt].l=pre;
    }
}
// make_st()
// make st table
inline void make_st(){
    for(int i=1;i<=n;i++){
        f[i][0]=next_b[next_a[i]];
        sta[i][0]=Aabs(c[nid[i]].hei-c[nid[next_a[i]]].hei);
        stb[i][0]=Aabs(c[nid[next_a[i]]].hei-c[nid[f[i][0]]].hei);
    }
    for(int j=1;j<=20;j++){
        for(int i=1;i<=n;i++){
            f[i][j]=f[f[i][j-1]][j-1];
            sta[i][j]=sta[i][j-1]+sta[f[i][j-1]][j-1];
            stb[i][j]=stb[i][j-1]+stb[f[i][j-1]][j-1];
        }
    }
}
// Ans_all()
// find Max of dis_a / dis_b
inline void Ans_all(){
    scanf("%lld",&x);
    for(int i=1;i<=n;i++){
        get_dis(x,i);
        if(Min>(1.0*dis_a/dis_b)){
            Min=1.0*dis_a/dis_b;
            ans=i;
        }
    }
    printf("%d\n",ans);
}
// Ans()
// get ans of all ask
inline void Ans(){
    scanf("%d",&m);
    while(m--){
        scanf("%d%lld",&p,&x);
        get_dis(x,p);
        printf("%lld %lld\n",dis_a,dis_b);
    }
}
int main(){
    readin();
    init();
    make_st();
    Ans_all();
    Ans();
}
]]>

科学解决 RMQ 问题 — 线段树/(ST/稀疏表)/分块

RBQRMQ

区间最值问题
大概就是那种给你一串数字,然后问你在区间[l,r]内,求最小值或最大值 一般,我们的操作,就是暴力枚举 然后你就光荣的TLE/MLE 然后让我们来说说区间问题的三种解法—线段树/ST表与分块

线段树


预处理: O( n*log(n) )
查询: O( log(n) )
单点更新: 支持,不破坏查询复杂度
写的爽,调的更爽
线段树是一种数据结构 首先我们需要了解一种东西,哈弗曼树 显然,对于一颗二叉树,如果一个节点号为n那么它的左节点是2n,右节点是2n+1 然后我们就可以愉快的存树了 然后什么是线段树呢? 吃的 它是能够维护一定区间的树 他的根节点是[L,R](最左和最右)的最优值 然后左节点是[L,(L+R)/2]的最优值 右节点是[(L+R)/2+1,R]的最优值 往后以此类推 直到l==r为止 简单代码如下:
这个代码对应[https://www.luogu.org/problemnew/show/P4644]这道题
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
int n,m,e;
struct whi{
    int left,rig,cost;
}a[11000];
int f[110000];
int tree[11000000];
bool cmp(whi a,whi b){
    return a.rig<b.rig;
}
// 创建
void build(int p,int l,int r){// p 当前下标 l 左端点 r 右端点
    if(l==r) {tree[p]=f[l];return ;}
    build(p<<1,l,(l+r)>>1);
    build(p<<1|1,((l+r)>>1)+1,r);
    tree[p]=min(tree[p<<1],tree[p<<1|1]);
}
// 更新单点
void update(int p,int l,int r,int now,int val){// p 当前下表 l 当前左端点 r 当前右端点 now 当前点的边界 val 更新的值
    if(l==r&&l==now){tree[p]=val;return ;}
    if(now<=((l+r)>>1)) update(p<<1,l,(l+r)>>1,now,val);
    else update(p<<1|1,((l+r)>>1)+1,r,now,val);
    tree[p]=min(tree[p<<1],tree[p<<1|1]);
}
// 求区间最值
int query(int p,int l,int r,int ll,int rr){//p 当前下表  l 当前左端点 r 当前右端点 ll 需求左端点 rr 需求右端点
    if(ll<=l&&rr>=r){return tree[p];}
    int ans=0x7fffffff,mid=(l+r)>>1;
    if(ll<=mid) ans=min(ans,query(p<<1,l,mid,ll,rr));
    if(rr>mid) ans=min(ans,query(p<<1|1,mid+1,r,ll,rr));
    return ans;
}
int main(){
    memset(f,0x3f,sizeof(f));
    scanf("%d%d%d",&n,&m,&e);
    m++;e++;
    for(int i=1;i<=n;i++){
        scanf("%d%d%d",&a[i].left,&a[i].rig,&a[i].cost);
        a[i].left++;a[i].rig++;
    }
    sort(a+1,a+n+1,cmp);
    /*for(int i=1;i<=n;i++){
        printf("%d %d %d\n",a[i].left,a[i].rig,a[i].cost);
    }*/
    f[m-1]=0;
    build(1,m-1,e);
    for(int i=1;i<=n;i++){
        if(a[i].rig<m) continue;
        if(a[i].left<=m) f[a[i].rig]=min(f[a[i].rig],a[i].cost);
        else f[a[i].rig]=min(f[a[i].rig],query(1,m-1,e,a[i].left-1,a[i].rig)+a[i].cost);
        update(1,m-1,e,a[i].rig,f[a[i].rig]);
    }
    if(f[e]>=1061109567) printf("-1");
    else printf("%d",f[e]);
}
当然这个并不是线段树的完整用法wq 更详细的用法,请看下篇题解

ST/稀疏表

> 速度虽快,更新却难
预处理: O( n*log(n) )
查询: O( 1 )
单点更新: 支持,需重新预处理
ST/稀疏表(以下统称)ST表,是一种基于倍增思想的玄学算法 比如说我们用f[i][j]储存从 i 位置开始的 2^j个数中的最大值 那么转移的时候我们可以把当前区间拆成两个区间并分别取最大值 查询先计算出 log2(区间长度) 然后对于左端点和右端点分别进行查询,这样可以保证一定可以覆盖查询的区间 然后你就会发现一堆log和换底公式出现于你的程序中 感性理解吧~ 但是不难理解
对应例题:[https://www.luogu.org/problemnew/show/P3865]
#include <cstdio>
#include <cmath>
#include <cstring>
#include <algorithm>
using namespace std;
int n,m,l,r;
int a[110000];
int f[110000][110];
int st_query(int l,int r){
    int k=log(r-l+1)/log(2);
    return max(f[l][k],f[r-(1<<k)+1][k]);
}
int main(){
    scanf("%d%d",&n,&m);
    for(int i=1;i<=n;i++){
        scanf("%d",&a[i]);
        f[i][0]=a[i];
    }
    int t=log(n)/log(2)+1;
    for(int j=1;j<t;j++){
        for(int i=1;i<=n-(1<<j)+1;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",&l,&r);
        printf("%d\n",st_query(l,r));
    }
}
看起来是不是相当简单qwq 但是要千万注意log时该加1时不该加时不加1

分块


高端的模拟
预处理: O(n)
查询: O(sqrt(n))
更新: O(sqrt(n))
先说说什么是分块算法吧 分块,顾名思义,就是将一个数列分成几块单独处理,比如讲[1,5]分成三块就是[1,2] [3,4] [5]这三个 那么我们查找[1,3]的最小值,只需要查找第一个与第二个块的最小值 经过一些证明,我们可以知道,在分成sqrt(n)块的情况下最优 所以就有了复杂度中的一堆sqrt(n) 那么代码我相信大家心里都有数了 那么和线段树一样,代码下篇题解讲,毕竟都是一道题目嘛wq

End


这几种解法,只是一种板子,而真正的RMQ算法,可能会结合多种东西,或者被多种东西所结合,所以说活学活用是最重要的,无论如何,刷题是最重要的 “Happy Coding Life” ]]>