第一行有一个正整数n(3<=n<=100000)，代表小A拟定的路线数量
第二行有n个正整数，第i个代表第i条路线的起始日期
第三行有n个正整数，第i个代表第i条路线的终止日期
输入保证起始日期小于终止日期
日期最小是1，最大不超过1000000000
小A打算选三个路线进行旅游，比如 A -> B -> C
要求A的结束日期要小于B的开始日期，B的结束日期要小于C的开始日期。
输出一个非负整数，代表线路的方案数量。
例子
输入
6
4 1 3 2 1 2
4 1 3 3 2 2
输出
6
解释
[1,1] -> [2,2] -> [3,3]
[1,1] -> [2,2] -> [4,4]
[1,1] -> [2,3] -> [4,4]
[1,2] -> [3,3] -> [4,4]
[1,1] -> [3,3] -> [4,4]
[2,2] -> [3,3] -> [4,4]
方法一: 暴力算法
步骤:
1.找出所有路线的最晚结束日期，记为max。
2.对于所有路线按照起始日期进行排序。
3.使用一个三维数组dp[i][j][k]，其中ii表示当前考虑到第ii条路线，jj表示还需要选择jj条路线，kk表示前一条路线的结束日期。
4.递归计算每个状态的方案数。对于当前情况，分为两种可能：
不选当前路线，即dp[i][j][k] = dp[i+1][j][k]。
选择当前路线，即dp[i][j][k] = dp[i][j][k]=dp[i+1][j−1][roads[i][1]]，其中roads[i][1]roads[i][1]表示当前路线的结束日期。
5.记忆化搜索，避免重复计算。
6.最终，dp[0][3][0]dp[0][3][0]就是所求的答案。
方法二：线段树算法
步骤：
1.将所有路线按照起始日期排序。
2.构建一个数组sortedsorted，其中包含所有路线的起始日期和结束日期，并将其排序。可以使用一个线段树维护sortedsorted数组的前缀和。
3.使用三个线段树分别统计当前路径长度为1、2、3时的方案数。具体地，在遍历每个路线时，先查询出所有结束日期小于该路线起始日期的路线组合数量，然后将该路线加入到线段树中，并更新线段树的值。
4.最终，三个线段树的总和就是符合条件的路线组合数量。
对比
方法一的时间复杂度为O(n^3)。由于需要递归计算每个状态的方案数，因此当路线数量较多时，时间复杂度会非常高。
方法二的时间复杂度为O(nlogn)。由于使用了线段树优化，可以大大降低时间复杂度。
因此，方法二比方法一更加高效。
rust代码
use std::time::Instant;
fn num1(roads: &mut Vec<Vec<i32>>) -> i32 {
let n = roads.len();
let mut max = 0;
for i in 0..n {
max = std::cmp::max(max, roads[i][1]);
}
//let mut sorted_roads = roads.clone();
roads.sort_by(|a, b| a[0].cmp(&b[0]));
let mut dp = vec![vec![vec![-1; (max + 1) as usize]; 4]; n];
for a in 0..n {
for b in 0..4 {
for c in 0..=max {
dp[a][b][c as usize] = -1;
}
}
}
process1(&roads, 0, 3, 0, &mut dp)
}
fn process1(
roads: &Vec<Vec<i32>>,
i: usize,
rest: i32,
end: i32,
dp: &mut Vec<Vec<Vec<i32>>>,
) -> i32 {
if rest == 0 {
return 1;
}
if i == roads.len() {
return 0;
}
if dp[i][rest as usize][end as usize] != -1 {
return dp[i][rest as usize][end as usize];
}
let p1 = process1(roads, i + 1, rest, end, dp);
let p2 = if roads[i][0] > end {
process1(roads, i + 1, rest - 1, roads[i][1], dp)
} else {
0
};
let ans = p1 + p2;
dp[i][rest as usize][end as usize] = ans;
ans
}
fn num2(roads: &mut Vec<Vec<i32>>) -> i32 {
let n = roads.len();
let mut sorted = vec![0; n << 1];
for i in 0..n {
sorted[i << 1] = roads[i][0];
sorted[i << 1 | 1] = roads[i][1];
}
sorted.sort_unstable(); // 使用 sort_unstable() 函数排序
roads.sort_unstable_by(|a, b| a[0].cmp(&b[0])); // 使用 sort_unstable_by() 函数排序
let mut it1 = IndexTree::new((n as i32) << 1);
let mut it2 = IndexTree::new((n as i32) << 1);
let mut it3 = IndexTree::new((n as i32) << 1);
for road in roads {
let l = rank(&sorted, road[0]);
let r = rank(&sorted, road[1]);
it1.add(r, 1);
it2.add(r, it1.sum(l - 1));
it3.add(r, it2.sum(l - 1));
}
it3.sum((n as i32) << 1)
}
fn rank(sorted: &Vec<i32>, num: i32) -> i32 {
let mut l = 0;
let mut r = sorted.len() as i32 - 1;
let mut m = 0;
let mut ans = 0;
while l <= r {
m = (l + r) / 2;
if sorted[m as usize] >= num {
ans = m;
r = m - 1;
} else {
l = m + 1;
}
}
ans + 1
}
struct IndexTree {
tree: Vec<i32>,
n: i32,
}
impl IndexTree {
fn new(size: i32) -> Self {
Self {
tree: vec![0; (size + 1) as usize],
n: size,
}
}
fn sum(&self, mut index: i32) -> i32 {
let mut ret = 0;
while index > 0 {
ret += self.tree[index as usize];
index -= (index & -index);
}
ret
}
fn add(&mut self, mut index: i32, d: i32) {
while index <= self.n {
self.tree[index as usize] += d;
index += (index & -index);
}
}
}
fn random_roads(n: usize, v: i32) -> Vec<Vec<i32>> {
let mut roads = vec![vec![0, 0]; n];
for i in 0..n {
let mut a = rand::random::<i32>() % v + 1;
if a <= 0 {
a += v;
}
let mut b = rand::random::<i32>() % v + 1;
if b <= 0 {
b += v;
}
let (start, mut end) = if a < b { (a, b) } else { (b, a) };
if start == end {
end += 1;
}
roads[i][0] = start;
roads[i][1] = end;
}
roads
}
fn main() {
const N: usize = 50;
const V: i32 = 50;
const TEST_TIME: usize = 5000;
println!("功能测试开始");
for i in 0..TEST_TIME {
let n = rand::random::<usize>() % N + 1;
let mut roads = random_roads(n, V);
let mut roads2 = roads.clone();
let roads3 = roads2.clone();
let ans1 = num1(&mut roads);
let ans2 = num2(&mut roads2);
if ans1 != ans2 {
println!("出错了！{}", i);
println!("出错了！ans1 = {}", ans1);
println!("出错了！ans2 = {}", ans2);
println!("roads3 = {:?}", roads3);
return;
}
}
println!("功能测试结束");
println!("性能测试开始");
let n = 5000;
let v = 1000000000;
let mut roads = random_roads(n, v);
println!("数组长度 : {}", n);
println!("数值范围 : {}", v);
let start = Instant::now();
num2(&mut roads);
let end = Instant::now();
println!("运行时间 : {} 毫秒", (end - start).as_millis());
println!("性能测试结束");
}执行结果
