题目链接: P9933 [NFLSPC #6] 9.pop_book();
先考虑一个最基本的式子: \(x=v \times t\)，很显然的一点是，除了 Alek岁，每个人的运动路程函数写出来都是一条一次函数，斜率为速度 \(v\)，而截距暂时无法确定。
我们考虑下 Alek岁 的变化情况。很显然的是当两个人相遇，只有两种情况：
- Alek岁 追上别人，那么很显然这个人的速度一定比 Alek岁 小，根据题意，Alek不受任何影响。
- 如果是别人追上 Alek岁，那么很显然他 碎度一定大于 Alek岁，这样一来，Alek岁立马“变成那个人”，因为 \(v_{alek岁} < v_{other}\)，并且相遇，根据题意立马发生 \(v_{alek岁} \leftarrow v_{other}\)，所以如果有别人追上 Alek岁，那么可以变向地看做 Alek岁 瞬间变成那个人了。
考虑下如何解决环上路程问题。比较经典的断环为链。我们把长为 \(m\) 的操场断开拼成一段段的。那么 Alek岁 可以看做从 \(0\) 位置不断往右跑。
考虑下如何解决每个人的起点问题。显而易见的是，Alek岁 在 \(t\) 时段的位置是容易找到的。具体而言：对于 \(t\) 时段之前的已经开始跑的人，我们都能根据他们的出发点及其速度得到一条一次函数，而显而易见的是，在 \(t\) 时刻最高的点即为当前位置。
稍微证明下：
Alek岁 从0开始移动，当一个人从他“后面”启动时（如果在他前面就当做多追一圈从后面超过他），然后运动追上他，那么他会立马变成这个人。然后继续被别人追，显然这个过程 \(v\) 会越来越大，而且至多变化 \(n\) 次。Alek 岁在 \(t\) 时刻显然应当是还在起点没动（此时可能还没有人经过他），或者是其中一个人路程函数上的一个 \(t\) 时刻的点。容易知道，前面的语言转化为图像说明：
容易看出每个人的出发点是不同的，每个人的速度也是不同的。红色则为 Alek 的运动轨迹，途径三人，速度变化三次。很容易可以看出 \(t_i\) 时刻得到位置，则是对应的最高点。这个就是一堆线段中找 \(\max(k_i \times x +b_i)\)，典型的李超线段树维护问题。
开始考虑如何求截距 \(b\)，很显然的是，当时间为出发时间的时候，我们如果能找到当前点应该在的位置即 \((t_{出发时间},x_{当前链上的位置})\) 即可知道这条直线的方程。很显而易见的是，除了 Alek岁，其他人都是互不影响的，所以我们只需要考虑其他人对 Alek岁 的影响即可。
对于某个时刻的 \(t_i\) 我们可以通过李超线段树查出当前 Alek岁 的位置，同时知道他在第几个 \(m\) 段上即
\[\text{所在段的起点}start=\frac{pos_{alek岁}}{m}\times m
\]
这样一来根据出发地点还有上述起点，可以推出这个人应该在操场上的位置。假如这个人在此时 Alek岁 后面，那么不用管了，让他去追 Alek岁，追上就能改变。否则需要人为的移动到让他追 Alek岁：
很显然的是，按照环形跑道，我们该追那两个绿色部分的路程追到 Alek岁，但显然因为我们断环成链了，只会往右跑，必须保证这个人在 Alek岁 的后面去追到他才行。所以如图所示，我们只需要把当前位置往前平移一段长 \(m\) 就行。
算法思路
由于李超线段树维护线段不优，维护线段的原因是因为，这个一次函数需要在出发时刻 \(t_i\) 之后才奏效。为了避免维护线段，我们直接离线操作，对查询扫描线，到达指定查询时间的十时候才进行更新即可。这样一来就可以当做直线插入了，不会查询前面的时间导致出现问题。时间值域过大，不想离散化，动态开点即可。对于每插入一个人，查询出发时间时 Alek岁 的位置，根据这个位置获得自己在位移数轴上的正确位置以后算出截距并插入直线。
\[y=v_i \times (t-t_i)+pos_{正确位置} \rightarrow y=v_i \times t+(pos_{正确位置}-v_i \times t_i)
\]
很显然 \(k=v_i\)，\(b=pos_{正确位置}-v_i \times t_i\)
Rust 参考代码
#![allow(unused_variables)]
#![allow(clippy::large_stack_arrays)]
#![allow(unused_macros)]
#![allow(unused_mut)]
#![allow(dead_code)]
#![allow(unused_imports)]
#![allow(non_upper_case_globals)]
use std::cell::{Ref, RefCell};
use std::cmp::max;
use std::ffi::c_ushort;
use std::fs::read_to_string;
use std::io::{BufRead, Write};
use std::mem::swap;
use std::net::UdpSocket;
use std::ops::{Add, AddAssign};
//----------------------------递归闭包---------------------------
struct Func<'a, A, F>(&'a dyn Fn(Func<'a, A, F>, A) -> F);
impl<'a, A, F> Clone for Func<'a, A, F> {
fn clone(&self) -> Self {
Self(self.0)
}
}
impl<'a, A, F> Copy for Func<'a, A, F> {}
impl<'a, A, F> Func<'a, A, F> {
fn call(&self, f: Func<'a, A, F>, x: A) -> F {
(self.0)(f, x)
}
}
fn y<A, R>(g: impl Fn(&dyn Fn(A) -> R, A) -> R) -> impl Fn(A) -> R {
move |x| (|f: Func<A, R>, x| f.call(f, x))(Func(&|f, x| g(&|x| f.call(f, x), x)), x)
}
//Y组合子使用示例:(多参采用元组传参)
// let dfs = | f: & dyn Fn((usize, i32,bool)) -> bool, (i,sum,s): (usize,i32,bool) | -> bool{
// if i == n {
// return sum == 0 & & s;
// }
// return f((i + 1, sum + a[i], true)) | | f((i + 1, sum, s)) | |
// f((i + 1, sum - a[i], true));
// };
//----------------------------递归闭包---------------------------
//----------------------------常用函数----------------------------
#[inline]
fn prefix_array<T>(a: &Vec<T>, start: T) -> Vec<T>
where
T: Add<Output = T> + Copy + AddAssign,
{
(0..=a.len())
.scan(start, |x, y| {
if y == 0 {
Some(start)
} else {
*x += a[y - 1];
Some(*x)
}
})
.collect::<Vec<T>>()
}
#[inline]
fn suffix_array<T>(a: &Vec<T>, end: T) -> Vec<T>
where
T: Add<Output = T> + Copy + AddAssign,
{
let mut tmp = (0..=a.len())
.rev()
.scan(end, |x, y| {
if y == a.len() {
Some(end)
} else {
*x += a[y];
Some(*x)
}
})
.collect::<Vec<T>>();
tmp.reverse();
tmp
}
//----------------------------常用函数----------------------------
macro_rules! __inner_io_prelude {
($scanner:ident, $out:ident, $dol:tt) =>
{
use crate::io::in_out;
use crate::io::Scanner;
use std::io::Write;
let ($scanner, mut $out) = in_out();
let mut $scanner = Scanner::new($scanner);
macro_rules! __inner_input {(mut $a:ident : $type:tt) => {let mut $a: $type = $scanner.next();};($a:ident : $type:tt) => {let $a: $type = $scanner.next();};}
macro_rules! input {($dol ($dol($idents: ident)+ : $type: tt),*) => {$dol (__inner_input!{$dol ($idents)+: $type})*};}
macro_rules! put {($dol ($dol format:tt)*) => { let _ = write!($out, $dol ($dol format)*);};}
macro_rules! puts {($dol ($dol format:tt)*) => { let _ = writeln!($out, $dol ($dol format)*);};}
macro_rules! read_string_u8 {() => {$scanner.next::<String>().into_bytes()};}
macro_rules! print_all {($A:expr) => {{for &v in &$A {let _ = write!($out, "{} ", v);}puts!();}};}
macro_rules! read_usize {($n:expr) => {(0..$n).map(|_|$scanner.next::<usize>()).collect::<Vec<usize>>()};}
macro_rules! read_i32 {($n:expr) => {(0..$n).map(|_|$scanner.next::<i32>()).collect::<Vec<i32>>()};}
macro_rules! read_i64 {($n:expr) => {(0..$n).map(|_|$scanner.next::<i64>()).collect::<Vec<i64>>()};}
macro_rules! read_i128 {($n:expr) => {(0..$n).map(|_|$scanner.next::<i128>()).collect::<Vec<i128>>()};}
macro_rules! read_tow_array_usize {($n:expr,$m:expr) => {(0..$n).map(|_| read_usize!($m)).collect::<Vec<Vec<usize>>>()};}
macro_rules! read_tow_array_i32 {($n:expr,$m:expr) => {(0..$n).map(|_| read_i32!($m)).collect::<Vec<Vec<i32>>>()};}
macro_rules! read_tow_array_i64 {($n:expr,$m:expr) => {(0..$n).map(|_| read_i64!($m)).collect::<Vec<Vec<i64>>>()};}
macro_rules! read_tow_array_i128 {($n:expr,$m:expr) => {(0..$n).map(|_| read_i128!($m)).collect::<Vec<Vec<i128>>>()};}
macro_rules! count_bit {($n:expr) => {{let (mut ans, mut k) = (0_usize, $n);while k > 0 {ans += 1;k &= k - 1;}ans}};}
};
}
macro_rules! io_prelude {
($scanner:ident, $out:ident) => { __inner_io_prelude!($scanner, $out, $); };
}
// --------------------------- tools -----------------------------------
mod io {
use std::fs::File;
use std::io::{stdin, stdout, BufRead, BufReader, BufWriter, Write};
#[cfg(windows)]
pub fn in_out() -> (impl BufRead, impl Write) {
use std::os::windows::prelude::{AsRawHandle, FromRawHandle};
unsafe {
let stdin = File::from_raw_handle(stdin().as_raw_handle());
let stdout = File::from_raw_handle(stdout().as_raw_handle());
(BufReader::new(stdin), BufWriter::new(stdout))
}
}
#[cfg(unix)]
pub fn in_out() -> (impl BufRead, impl Write) {
use std::os::unix::prelude::{AsRawFd, FromRawFd};
unsafe {
let stdin = File::from_raw_fd(stdin().as_raw_fd());
let stdout = File::from_raw_fd(stdout().as_raw_fd());
(BufReader::new(stdin), BufWriter::new(stdout))
}
}
pub struct Scanner<R> {
reader: R,
buf_str: Vec<u8>,
buf_iter: std::str::SplitAsciiWhitespace<'static>,
}
impl<R: BufRead> Scanner<R> {
pub fn new(reader: R) -> Self {
Self {
reader,
buf_str: Vec::new(),
buf_iter: "".split_ascii_whitespace(),
}
}
pub fn next<T: std::str::FromStr>(&mut self) -> T {
loop {
if let Some(token) = self.buf_iter.next() {
return token.parse().ok().expect("Failed parse");
}
unsafe {
self.buf_str.set_len(0);
}
self.reader
.read_until(b'\n', &mut self.buf_str)
.expect("Failed read");
self.buf_iter = unsafe {
let slice = std::str::from_utf8_unchecked(&self.buf_str);
std::mem::transmute(slice.split_ascii_whitespace())
}
}
}
}
}
mod random {
use std::time::SystemTime;
const NN: usize = 312;
const MM: usize = 156;
const MATRIX_A: u64 = 0xB5026F5AA96619E9;
const UM: u64 = 0xFFFFFFFF80000000;
const LM: u64 = 0x7FFFFFFF;
const F: u64 = 6364136223846793005;
const MAG01: [u64; 2] = [0, MATRIX_A];
pub struct Random {
mt: [u64; NN],
index: usize,
}
impl Random {
pub fn new(seed: u64) -> Self {
let mut res = Self {
mt: [0u64; NN],
index: NN,
};
res.mt[0] = seed;
for i in 1..NN {
res.mt[i] = F
.wrapping_mul(res.mt[i - 1] ^ (res.mt[i - 1] >> 62))
.wrapping_add(i as u64);
}
res
}
pub fn gen(&mut self) -> u64 {
if self.index == NN {
for i in 0..(NN - MM) {
let x = (self.mt[i] & UM) | (self.mt[i + 1] & LM);
self.mt[i] = self.mt[i + MM] ^ (x >> 1) ^ MAG01[(x & 1) as usize];
}
for i in (NN - MM)..(NN - 1) {
let x = (self.mt[i] & UM) | (self.mt[i + 1] & LM);
self.mt[i] = self.mt[i + MM - NN] ^ (x >> 1) ^ MAG01[(x & 1) as usize];
}
let x = (self.mt[NN - 1] & UM) | (self.mt[0] & LM);
self.mt[NN - 1] = self.mt[MM - 1] ^ (x >> 1) ^ MAG01[(x & 1) as usize];
self.index = 0;
}
let mut x = self.mt[self.index];
self.index += 1;
x ^= (x >> 29) & 0x5555555555555555;
x ^= (x << 17) & 0x71D67FFFEDA60000;
x ^= (x << 37) & 0xFFF7EEE000000000;
x ^= x >> 43;
x
}
pub fn next(&mut self, n: u64) -> u64 {
self.gen() % n
}
pub fn next_bounds(&mut self, f: u64, t: u64) -> u64 {
f + self.next(t - f + 1)
}
}
static mut RAND: Option<Random> = None;
pub fn random() -> &'static mut Random {
unsafe {
if RAND.is_none() {
RAND = Some(Random::new(
(SystemTime::UNIX_EPOCH.elapsed().unwrap().as_nanos() & 0xFFFFFFFFFFFFFFFF)
as u64,
));
}
RAND.as_mut().unwrap()
}
}
pub trait Shuffle {
fn shuffle(&mut self);
}
impl<T> Shuffle for &mut [T] {
fn shuffle(&mut self) {
let len = self.len();
for i in 0..len {
let at = (random().gen() % ((i + 1) as u64)) as usize;
self.swap(i, at);
}
}
}
}
//----------------------------Test------------------------------常用板子书写区
//----------------------------Test------------------------------常用板子书写区
//-----------------------------main-------------------------------------主逻辑书写区
const N: usize = 550010;
static mut K: [i64; 550010] = [0; N];
static mut B: [i64; 550010] = [0; N];
static mut VAL: [usize; 17600320] = [0usize; N << 5];
static mut LEFT: [usize; 17600320] = [0usize; N << 5];
static mut RIGHT: [usize; 17600320] = [0usize; N << 5];
static mut cnt: usize = 0;
pub unsafe fn get_y(curr: usize, x: i64) -> i64 {
K[curr] * x + B[curr]
}
pub unsafe fn add(curr: &mut usize, l: i64, r: i64, mut id: usize) {
if *curr == 0 {
cnt += 1;
*curr = cnt;
}
if VAL[*curr] == 0 {
VAL[*curr] = id;
return;
}
let mid = (l + r) >> 1;
if get_y(VAL[*curr], mid) < get_y(id, mid) {
swap(&mut VAL[*curr], &mut id);
}
if l == r {
return;
}
if get_y(VAL[*curr], l) < get_y(id, l) {
add(&mut LEFT[*curr], l, mid, id);
}
if get_y(VAL[*curr], r) < get_y(id, r) {
add(&mut RIGHT[*curr], mid + 1, r, id);
}
}
pub unsafe fn query(curr: usize, l: usize, r: usize, x: i64) -> i64 {
if curr == 0 {
return 0;
}
let mid: usize = (l + r) >> 1;
get_y(VAL[curr], x).max(if x <= mid as i64 {
query(LEFT[curr], l, mid, x)
} else {
query(RIGHT[curr], mid + 1, r, x)
})
}
static mut n: usize = 0;
static mut root: usize = 0;
static mut tMax: usize = 0;
static mut segCnt: usize = 0;
pub unsafe fn clear() {
for i in 1..=n {
K[i] = 0;
B[i] = 0;
}
for i in 1..=n << 2 {
LEFT[i] = 0;
RIGHT[i] = 0;
VAL[i] = 0;
}
cnt = 0;
root = 0;
segCnt = 0;
}
#[inline]
pub unsafe fn solve() {
io_prelude!(scanner, out);
//-----------------------------------------------------------------
for _ in 0..scanner.next::<usize>() {
n = scanner.next();
input! {m:usize,q:usize}
let mut qu = vec![];
for i in 0..n {
qu.push((
scanner.next::<i64>(),
scanner.next::<i64>(),
scanner.next::<i64>(),
));
}
let mut curr = 0;
let t_query = read_i64!(q);
tMax = t_query[q - 1] as usize + 1;
for &v in &t_query {
while curr < n && qu[curr].2 <= v {
let (pos, v, ti) = qu[curr];
let curr_pos = query(root, 1, tMax, ti);
let mut nxt_pos = pos + (curr_pos as usize / m * m) as i64;
if nxt_pos > curr_pos {
nxt_pos -= m as i64;
}
segCnt += 1;
K[segCnt] = v;
B[segCnt] = nxt_pos - v * ti;
add(&mut root, 1, tMax as i64, segCnt);
curr += 1;
}
puts!("{}", query(root, 1, tMax, v));
}
clear();
}
}
//-----------------------------main-------------------------------------主逻辑书写区
fn main() {
unsafe {
solve();
}
}
C++ 参考代码
#include <bits/stdc++.h>
//#pragma GCC optimize("Ofast,unroll-loops")
#define isPbdsFile
#ifdef isPbdsFile
#include <bits/extc++.h>
#else
#include <ext/pb_ds/priority_queue.hpp>
#include <ext/pb_ds/hash_policy.hpp>
#include <ext/pb_ds/tree_policy.hpp>
#include <ext/pb_ds/trie_policy.hpp>
#include <ext/pb_ds/tag_and_trait.hpp>
#include <ext/pb_ds/hash_policy.hpp>
#include <ext/pb_ds/list_update_policy.hpp>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/exception.hpp>
#include <ext/rope>
#endif
using namespace std;
using namespace __gnu_cxx;
using namespace __gnu_pbds;
typedef long long ll;
typedef long double ld;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
typedef tuple<int, int, int> tii;
typedef tuple<ll, ll, ll> tll;
typedef unsigned int ui;
typedef unsigned long long ull;
typedef __int128 i128;
#define hash1 unordered_map
#define hash2 gp_hash_table
#define hash3 cc_hash_table
#define stdHeap std::priority_queue
#define pbdsHeap __gnu_pbds::priority_queue
#define sortArr(a, n) sort(a+1,a+n+1)
#define all(v) v.begin(),v.end()
#define yes cout<<"YES"
#define no cout<<"NO"
#define Spider ios_base::sync_with_stdio(false);cin.tie(nullptr);cout.tie(nullptr);
#define MyFile freopen("..\\input.txt", "r", stdin),freopen("..\\output.txt", "w", stdout);
#define forn(i, a, b) for(int i = a; i <= b; i++)
#define forv(i, a, b) for(int i=a;i>=b;i--)
#define ls(x) (x<<1)
#define rs(x) (x<<1|1)
#define endl '\n'
//用于Miller-Rabin
[[maybe_unused]] static int Prime_Number[13] = {0, 2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37};
template <typename T>
int disc(T* a, int n)
{
return unique(a + 1, a + n + 1) - (a + 1);
}
template <typename T>
T lowBit(T x)
{
return x & -x;
}
template <typename T>
T Rand(T l, T r)
{
static mt19937 Rand(time(nullptr));
uniform_int_distribution<T> dis(l, r);
return dis(Rand);
}
template <typename T1, typename T2>
T1 modt(T1 a, T2 b)
{
return (a % b + b) % b;
}
template <typename T1, typename T2, typename T3>
T1 qPow(T1 a, T2 b, T3 c)
{
a %= c;
T1 ans = 1;
for (; b; b >>= 1, (a *= a) %= c)if (b & 1)(ans *= a) %= c;
return modt(ans, c);
}
template <typename T>
void read(T& x)
{
x = 0;
T sign = 1;
char ch = getchar();
while (!isdigit(ch))
{
if (ch == '-')sign = -1;
ch = getchar();
}
while (isdigit(ch))
{
x = (x << 3) + (x << 1) + (ch ^ 48);
ch = getchar();
}
x *= sign;
}
template <typename T, typename... U>
void read(T& x, U&... y)
{
read(x);
read(y...);
}
template <typename T>
void write(T x)
{
if (x == ' ' or x == endl)return;
if (x < 0)x = -x, putchar('-');
if (x > 9)write(x / 10);
putchar(x % 10 ^ 48);
}
template <typename C, typename T, typename... U>
void write(C c, T x, U... y)
{
write(x), putchar(c);
write(c, y...);
}
template <typename T11, typename T22, typename T33>
struct T3
{
T11 one;
T22 tow;
T33 three;
bool operator<(const T3 other) const
{
if (one == other.one)
{
if (tow == other.tow)return three < other.three;
return tow < other.tow;
}
return one < other.one;
}
T3() { one = tow = three = 0; }
T3(T11 one, T22 tow, T33 three) : one(one), tow(tow), three(three)
{
}
};
template <typename T1, typename T2>
void uMax(T1& x, T2 y)
{
if (x < y)x = y;
}
template <typename T1, typename T2>
void uMin(T1& x, T2 y)
{
if (x > y)x = y;
}
constexpr int N = 5e5 + 10;
struct Seg
{
int k;
ll b;
Seg() = default;
Seg(const int k, const ll b)
: k(k),
b(b)
{
}
ll getY(const ll x) const
{
return k * x + b;
}
} seg[N];
int cnt;
struct Node
{
int left, right;
int id;
} node[N << 5];
int id;
#define idx(x) node[x].id
#define lll node[curr].left
#define rrr node[curr].right
inline void add(int& curr, const int l, const int r, int val)
{
if (!curr)curr = ++cnt;
if (!idx(curr))
{
idx(curr) = val;
return;
}
const int mid = l + r >> 1;
if (seg[val].getY(mid) > seg[idx(curr)].getY(mid))swap(val,idx(curr));
if (l == r)return;
if (seg[val].getY(l) > seg[idx(curr)].getY(l))add(lll, l, mid, val);
if (seg[val].getY(r) > seg[idx(curr)].getY(r))add(rrr, mid + 1, r, val);
}
inline ll query(const int curr, const int l, const int r, const int pos)
{
if (!curr)return 0;
ll ans = seg[idx(curr)].getY(pos);
if (const int mid = l + r >> 1; pos <= mid)uMax(ans, query(lll, l, mid, pos));
else uMax(ans, query(rrr, mid + 1, r, pos));
return ans;
}
int n, m, q;
int root;
//注意多测清空
inline void clear()
{
forn(i, 1, n)seg[i].k = seg[i].b = 0;
forn(curr, 1, cnt)
lll = rrr = idx(curr) = 0;
cnt = id = 0;
root = 0;
}
T3<int, int, int> p[N]; //离线记录
int qu[N << 1];
int tMax = 1;
inline void solve()
{
cin >> n >> m >> q;
forn(i, 1, n)cin >> p[i].one >> p[i].tow >> p[i].three;
int curr = 1;
forn(i, 1, q)cin >> qu[i];
tMax = qu[q] + 1;
forn(i, 1, q)
{
int t = qu[i];
while (curr <= n and p[curr].three <= t)
{
auto [pos, v, ti] = p[curr];
ll currPos = query(root, 1, tMax, ti); //当前Alek位置
ll nxtPos = pos + currPos / m * m; //这个需要插入的人所在的位置
if (nxtPos > currPos)nxtPos -= m; //如果在Alek前面就让他多追一圈
int k = v;
ll b = nxtPos - ll(v) * ti;
seg[++id] = Seg(k, b);
add(root, 1, tMax, id);
curr++;
}
cout << query(root, 1, tMax, t) << endl;
}
clear();
}
signed int main()
{
Spider
//------------------------------------------------------
int test = 1;
// read(test);
cin >> test;
forn(i, 1, test)solve();
// while (cin >> n, n)solve();
// while (cin >> test)solve();
}
\[\text{最终单个Test的复杂度为} O(n\log{T_{max}})
\]