Liveddd's Blog

愛にできることはまだあるかい

LOJ#2395. 「JOISC 2017 Day 2」火车旅行

发表于 分类于
本文字数： 2.3k 阅读时长 ≈ 5 分钟

很好的一道题。

考虑最优情况下的路径，满足 经过的点的值 呈现单峰。

于是我们考虑从 $u,v$ 开始双向奔赴，二者按照顺序经过的点的值是单调的。由于我们是不断尝试朝中间走，并且走的点权是单调的。这意味着我们不断尝试朝 对面的点 走一定是最优的。考虑倍增 $f_{i,j},g_{i,j}$ 表示分别向左向右跳 $2^j$ 步走到的最远的点。查询的时候不断尝试往中间跳就行了。时间复杂度 $\mathcal O((n+q)\log n)$。

其实我不太知道如何严谨证明这样的策略的正确性，纯靠手玩再讨论几种情况勉强理解。但就是感觉很对，还是太菜了。

Code
 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
#include<iostream>
#include<cstdio>
using namespace std;
const int N=1e5+10,K=17;
template<class T>
inline void read(T &x)
{
    x=0;int f=0;
    char ch=getchar();
    while(ch<'0'||ch>'9'){if(ch=='-')f=1;ch=getchar();}
    while(ch>='0'&&ch<='9')x=(x<<1)+(x<<3)+(ch^48),ch=getchar();
    if(f)x=~x+1;
}
template<class T,class ...T1>
inline void read(T &x,T1 &...x1)
{
    read(x),read(x1...);
}
int n,m,q;
int a[N];
int f[K+5][N],g[K+5][N];
int top,sta[N];

int main()
{
    // freopen("1.in","r",stdin);
    // freopen("1.out","w",stdout);
    read(n,m,q);
    for(int i=1;i<=n;i++)read(a[i]);
    
    for(int i=1;i<=n;i++)
    {
        while(top&&a[sta[top]]<a[i])top--;
        if(top)f[0][i]=sta[top];
        else f[0][i]=i;
        sta[++top]=i;
    }
    top=0;
    for(int i=n;i;i--)
    {
        while(top&&a[sta[top]]<a[i])top--;
        if(top)g[0][i]=sta[top];
        else g[0][i]=i;
        sta[++top]=i;
    }
    for(int t=1;t<=K;t++)
        for(int i=1;i<=n;i++)
        {
            f[t][i]=min(f[t-1][f[t-1][i]],f[t-1][g[t-1][i]]);
            g[t][i]=max(g[t-1][g[t-1][i]],g[t-1][f[t-1][i]]);
        }
    int u,v,ans;
    while(q--)
    {
        int x,y;
        read(x,y);
        if(x>y)swap(x,y);
        ans=0;
        u=v=x;
        for(int t=K;~t;t--)
        {
            int p=min(f[t][u],f[t][v]),q=max(g[t][u],g[t][v]);
            if(q<y)u=p,v=q,ans+=1<<t;
        }
        x=v,u=v=y;
        for(int t=K;~t;t--)
        {
            int p=min(f[t][u],f[t][v]),q=max(g[t][u],g[t][v]);
            if(p>x)u=p,v=q,ans+=1<<t;
        }
        printf("%d\n",ans);
    }
    return 0;
}