Skip to content

14210: 【原4210】travel

题目

题目描述

author: Chen Yuxuan 原OJ链接:https://acm.sjtu.edu.cn/OnlineJudge-old/problem/4210

Description

有 \(n\) 个城市, \(n - 1\) 条道路 (\(n > 1\)),第 \(i\) 个城市和第 \(i + 1\) 个城市通过第 \(i\) 条道路相连 ( \(1\leq i \lt n\) ),第 \(i\) 道路有两个属性 \(a_i , b_i \, (a_i \gt 0, b_i \geq 0)\)

轩轩是个货担郎,假设他在持有 \(x\) 枚金币时通过第 \(i\) 条道路,那么他的金币数量将变为 \( \lfloor x / a_i \rfloor + b_i\)

接下来轩轩要利用 \(m\) 天规划自己的行程,每天会发生以下两种事件中的一种:

  1. 轩轩得知第 \(k\) 条道路的属性值修改为 \(x, y\),即修改 \(a_k = x, b_k = y\)

  2. 轩轩询问你,假设他持有 \(w\) 枚金币,从第 \(s\) 个城市出发,到达第 \(t\) 个城市 (\(s < t\)),经过 \(s\)与 \(t\) 间的每条道路恰好一次 (即沿序通过道路 \(s, s + 1, s + 2,\cdots ,t - 1\)),那么当他到达 \(t\) 时,将持有多少枚金币呢?

Input Format

第一行一个整数 \(case_id\)

第二行两个整数 \(n\) 和 \(m\) ,表示城市的个数和规划行程的天数。

第三行 \(n-1\) 个整数,第 \(i\) 个整数表示第 \(i\) 条道路的属性 \(a_i\)

第四行 \(n-1\) 个整数,第 \(i\) 个整数表示第 \(i\) 条道路的属性 \(b_i\)

接下来 \(m\) 行,每行 \(4\) 个整数,格式为 1 k x y2 w s t,含义见问题描述。

case_id
n m
a_1 a_2 a_3 ... a_{n-1}
b_1 b_2 b_3 ... b_{n-1}
...
1 k_i x_i y_i
...
2 w_j s_j t_j
...

Output Format

对于每个询问,输出一行,一个整数,表示你的答案

Sample Input

-1
4 3
2 1 2
1 1 1
2 100 1 4
1 2 2 0
2 100 1 4

Sample Output

27
13

Limits

在真实的测试数据中:

  • \(case_id\in {0, 1, 2, 3, 4, 5, 6, 7, 8, 9}\)

  • \(1 \lt n \leq 10^5, 1 \leq m \leq 2*10^5, 1\leq a_i \leq 10^3, 0\leq b_i \leq10^3\)

  • \(1 \leq k_i \lt n, 1\leq x_i \leq 10^3, 0\leq y_i \leq 10^3\)

  • \(0 \leq w_i \leq 10^6 , 1 \leq s_i \lt t_i \leq n\)

| case | n | m | else | | ------ | ------ | ------ | ------ | | 0 | 100 | 200 | | | 1 | 1000 | 2000 | | | 2 | 10000 | 20000 | | | 3 | 10000 | 50000 | | | 4 | 10000 | \(10^5\) | | | 5 | \(10^5\) | \(210^5\) | \(a_i = x_i = 1\) | | 6 | \(10^5\) | \(210^5\) | \(a_i = x_i = 1\) | | 7 | \(10^5\) | \(210^5\) | \(b_i = y_i = 0\) | | 8 | \(10^5\) | \(210^5\) | \(b_i = y_i = 0\) | | 9 | \(10^5\) | \(2*10^5\) | |

Oops! 本题目还没有解答!

助教老师们编题的速度,已经超过了解题的速度!

OJ翻了一新,但本解答集还大多用的是2017-2019级,甚至更早的同学们贡献的答案。

如果你已经AC了,可以的话,请您参考添加页面,与大家一起分享你的题解!