2023-01-04：有三个题库 A、B、C，每个题库均有 n 道题目，且题目都是从 1 到 n 进行编号 每个题目都有一个难度值 题库 A 中第 i 个题目的难度为 ai 题库 B 中第 i 个题目的难度为 bi 题库 C 中第 i 个题目

use rand::Rng;use std::iter::repeat;fn main() {    let mut a = vec![71, 29, 13, 74, 90, 8, 30, 25];    let mut b = vec![72, 1, 50, 98, 86, 86, 52, 57];    let mut c = vec![11, 24, 61, 70, 11, 90, 13, 30];    let ans = ways2(&mut a, &mut b, &mut c);    println!("ans = {}", ans);    let nn: i32 = 100;    let vv: i32 = 100;    let test_time: i32 = 5000;    println!("测试开始");    for i in 0..test_time {        let n = rand::thread_rng().gen_range(0, nn) + 1;        let mut a = random_array(n, vv);        let mut b = random_array(n, vv);        let mut c = random_array(n, vv);        let ans1 = ways1(&mut a, &mut b, &mut c);        let ans2 = ways2(&mut a, &mut b, &mut c);        if ans1 != ans2 {            println!("出错了!{}", i);            println!("ans1 = {}", ans1);            println!("ans2 = {}", ans2);            break;        }    }    println!("测试结束");}
// 暴力方法// 时间复杂度O(N^3)// 为了验证fn ways1(a: &mut Vec<i32>, b: &mut Vec<i32>, c: &mut Vec<i32>) -> i32 {    let n = a.len() as i32;    a.sort();    b.sort();    c.sort();    let mut ans = 0;    for i in 0..n {        let mut j = 0;        while j < n && b[j as usize] <= a[i as usize] * 2 {            if b[j as usize] > a[i as usize] {                let mut k = 0;                while k < n && c[k as usize] <= b[j as usize] * 2 {                    if c[k as usize] > b[j as usize] {                        ans += 1;                    }                    k += 1;                }            }            j += 1;        }    }    return ans;}
// 正式方法// 时间复杂度O(N * logN)fn ways2(a: &mut Vec<i32>, b: &mut Vec<i32>, c: &mut Vec<i32>) -> i32 {    let n = a.len() as i32;    a.sort();    b.sort();    c.sort();    // B里面的记录    let mut help: Vec<i32> = repeat(0).take(n as usize).collect();    let mut i = 0;    let mut l = -1;    let mut r = 0;    while i < n {        while l + 1 < n && c[(l + 1) as usize] <= b[i as usize] {            l += 1;        }        while r < n && c[r as usize] <= b[i as usize] * 2 {            r += 1;        }        help[i as usize] = get_max(r - l - 1, 0);        i += 1;    }    for i in 1..n {        help[i as usize] += help[(i - 1) as usize];    }    let mut ans = 0;    let mut i = 0;    let mut l = -1;    let mut r = 0;    while i < n {        while l + 1 < n && b[(l + 1) as usize] <= a[i as usize] {            l += 1;        }        while r < n && b[r as usize] <= a[i as usize] * 2 {            r += 1;        }        if r - l - 1 > 0 {            ans += sum(&mut help, l + 1, r - 1);        }        i += 1;    }    return ans;}
fn sum(help: &mut Vec<i32>, l: i32, r: i32) -> i32 {    return if l == 0 {        help[r as usize]    } else {        help[r as usize] - help[(l - 1) as usize]    };}
fn get_max<T: Clone + Copy + std::cmp::PartialOrd>(a: T, b: T) -> T {    if a > b {        a    } else {        b    }}
// 为了测试fn random_array(n: i32, v: i32) -> Vec<i32> {    let mut arr: Vec<i32> = vec![];    for _i in 0..n {        arr.push(rand::thread_rng().gen_range(0, v));    }    return arr;}

// SPDX-License-Identifier: MITpragma solidity ^0.8.17;
contract Hello{    function main() public pure returns (int32){        int32[] memory a = new int32[](8);    a[0] = 71;    a[1] = 29;    a[2] = 13;    a[3] = 74;    a[4] = 90;    a[5] = 8;    a[6] = 30;    a[7] = 25;    int32[]  memory b = new int32[](8);    b[0] = 72;    b[1] = 1;    b[2] = 50;    b[3] = 98;    b[4] = 86;    b[5] = 86;    b[6] = 52;    b[7] = 57;    int32[]  memory c = new int32[](8);    c[0] = 11;    c[1] = 24;    c[2] = 61;    c[3] = 70;    c[4] = 11;    c[5] = 90;    c[6] = 13;    c[7] = 30;    int32 ans = ways2(a,b,c);        return ans;    }
  // 正式方法  // 时间复杂度O(N * logN)  function ways2(int32[] memory a, int32[] memory b, int32[] memory c) public pure returns (int32){    int32 n = int32(int(a.length));    sort(a);    sort(b);    sort(c);    // B里面的记录    int32[] memory help  = new int32[](uint(uint32(n)));    int32 l = -1;    int32 r = 0;    for (int32 i = 0; i < n; i++) {      while (l + 1 < n && c[uint(uint32(l + 1))] <= b[uint(uint32(i))]) {        l++;      }      while (r < n && c[uint(uint32(r))] <= b[uint(uint32(i))] * 2) {        r++;      }      help[uint(uint32(i))] = getMax(r - l - 1, 0);    }    for (int32 i = 1; i < n; i++) {      help[uint(uint32(i))] += help[uint(uint32(i - 1))];    }    int32 ans = 0;    l = -1;    r = 0;    for (int32 i = 0; i < n; i++) {      while (l + 1 < n && b[uint(uint32(l + 1))] <= a[uint(uint32(i))]) {        l++;      }      while (r < n && b[uint(uint32(r))] <= a[uint(uint32(i))] * 2) {        r++;      }      if (r - l - 1 > 0) {        ans += sum(help, l + 1, r - 1);      }    }    return ans;  }
  function sum(int32[] memory help, int32 l, int32 r) public pure returns (int32){    return l == 0 ? help[uint(uint32(r))] : help[uint(uint32(r))] - help[uint(uint32(l - 1))];  }
    function getMax(int32 a,int32 b) public pure returns (int32){        if(a>b){            return a;        }else{            return b;        }    }
  function sort(int32[] memory arr)public pure{    int32 temp = 0;    for(int32 i = 1; i <= int32(int(arr.length)) - 1; i++) {      for(int32 j = i; j > 0; j--) {        if(arr[uint(uint32(j - 1))] > arr[uint(uint32(j))]) {          temp = arr[uint(uint32(j))];          arr[uint(uint32(j))] = arr[uint(uint32(j - 1))];          arr[uint(uint32(j - 1))] = temp;         }else {          //不满足条件结束循环即可          break;        }      }    }  }}