P14727 Frog Jump

P14727 [ICPC 2022 Seoul R] Frog Jump

博客食用不知道会不会更佳

读题 & 思路

• Frog 在相连的区间（有重叠部分）内部移动没有花费，在不相连的区间之间才有花费，又看到输入区间的顺序，容易想到一边输入一边合并，$O(n)$。

• 模拟 Frog 在区间上跳，但是求两个区间的距离的时间复杂度为 $O(n)$，总时间复杂度 $O(nk)$，超时。
  因为要多次求合并后区间之间的距离的区间和（两个区间之间的空隙的和），容易想到前缀和，$O(k)$。

总时间复杂度 $O(n+k)$。

记得开 long long。

代码

具体实现看注释。

import java.io.*;
import java.util.*;
public class Main{
    //IO 优化
    static BufferedReader br=new BufferedReader(new InputStreamReader(System.in));
    static StringTokenizer st;
    static String next() throws IOException{
        while(st==null||!st.hasMoreElements()) st=new StringTokenizer(br.readLine());
        return st.nextToken();
    }
    static int nextInt() throws IOException{
        return Integer.parseInt(next());
    }
    static PrintWriter out=new PrintWriter(new BufferedWriter(new OutputStreamWriter(System.out)));
    //
    static long[] l=new long[214514];//合并后区间左右端点
    static long[] r=new long[214514];
    static int[] f=new int[214514];//原来的区间合并后区间编号
    static long[] s=new long[214514];//合并后区间 1 到 i 的距离
    public static void main(String[] args) throws IOException{
        long n=nextInt(),k=nextInt();
        int cnt=1;

        l[cnt]=nextInt();r[cnt]=nextInt();//一边读一边合并
        f[1]=cnt;
        for(int i=2;i<=n;i++){
            int a=nextInt(),b=nextInt();
            if(a>r[cnt]||b<l[cnt]){//如果不重合，记录新区间
                cnt++;
                l[cnt]=a;r[cnt]=b;
            }
            else{//如果重合，合并
                l[cnt]=Math.min(l[cnt],a);
                r[cnt]=Math.max(r[cnt],b);
            }
            f[i]=cnt;
            s[cnt]=s[cnt-1]+l[cnt]-r[cnt-1];//1到i的距离 = 1到i-1的距离 + i-1到i的距离
        }
        long ans=0;int p=1;
        for(int i=1;i<=k;i++){
            int x=nextInt();
            ans+=Math.abs(s[f[x]]-s[f[p]]);//累加距离
            p=x;
        }
        out.println(ans);
        out.flush();
    }
}

蒟蒻的第一篇题解,求过。${\tiny {\color{White}\text{WQX Frog}}}$