UOJ Logo Universal Online Judge

UOJ

#93. 【集训队互测2015】上帝之手

统计

上帝之手操纵着四维空间。假设四维空间中上帝关心的部分共 $n$ 天,定义第 $i$ 天结束时一个三维世界的混乱度为 $x_i$。由于一些自然的原因,第 $i$ 天该世界的混乱度会增加 $d_i$,但为了世界的平衡,每天该世界都有一个混乱度的上限值 $l_i$,即实际上 $x_i = \min\{x_{i-1}+d_i , l_i\}$。

上帝想对该四维空间作一系列测试,于是希望你帮忙建立一个模型。具体有以下三种测试:

  1. 给定 $a, b$ 和 $k$,对于所有的 $c$ 满足 $a \leq c \leq b$,让世界以 $l_{c-1}$ 的初始混乱度从第 $c$ 天开始发展,把第 $b$ 天的混乱度 $x_b$ 写在一张纸上。你只需告诉上帝纸上第 $k$ 大的 $x_b$ 即可。保证 $1 \leq a \leq b \leq n$,且 $1 \leq k \leq b - a + 1$。
  2. 给定 $a, b$ 和 $x_0$,对于所有的 $c$ 满足 $a \leq c \leq b$,让世界以 $x_0$ 的初始混乱度从第 $c$ 天开始发展,把第 $b$ 天的混乱度 $x_b$ 写在一张纸上。你只需告诉上帝纸上最大的 $x_b$ 即可。(注意:$x_0$ 可能大于 $l_{c-1}$)。保证 $1 \leq a \leq b \leq n$。
  3. 给定 $a$ 和 $b$,对于所有的 $c$ 满足 $a \leq c \leq b$,让世界以 $l_{c-1}$ 的初始混乱度从第 $c$ 天开始发展,把第 $b$ 天的混乱度 $x_b$ 写在一张纸上。你只需告诉上帝纸上有多少种不同的 $x_b$ 即可。保证 $1 \leq a \leq b \leq n$。

当然,上帝还会修改某些位置的 $l_i$。你能成功帮助上帝完成测试吗?

输入格式

第一行包含两个正整数 $n$ 和 $m$,分别表示总天数和总操作(包含测试和修改)次数。

第二行为 $n$ 个非负整数 $d_1, \dots, d_n$。

第三行为 $n+1$ 个非负整数 $l_0, \dots, l_n$。含义见问题描述。

第四行起的 $m$ 行,每行第一个整数 $\mathrm{type}$ 表示操作种类。

若 $\mathrm{type}=0$,则后面跟有两个整数 $u$ 和 $x$,表示将 $l_u$ 改为 $x$。保证 $0 \leq u \leq n$。

若 $\mathrm{type}>0$,则 $\mathrm{type}$ 等于题目描述中对应的测试种类编号。$\mathrm{type} = 1$ 时后面跟有三个整数 $a, b$ 和 $k$;$\mathrm{type} = 2$ 时后面跟有三个整数 $a, b$ 和 $x_0$;$\mathrm{type} = 3$ 时后面跟有两个整数 $a$ 和 $b$。具体含义见问题描述。

输出格式

对于每个测试输出一行,包含一个整数表示测试结果。

样例一

input

3 5
2 1 3
2 6 7 5
1 1 2 2
3 1 3
0 3 15
3 1 3
2 1 3 2

output

5
1
2
8

限制与约定

对于前 10% 的数据,$n, m \leq 100$;

对于前 20% 的数据,$n, m \leq 5000$;

对于另 10% 的数据,$\mathrm{type} \leq 1$;

对于另 20% 的数据,$\mathrm{type} \leq 2$;

对于另 15% 的数据,$\mathrm{type} = 0~\text{或}~3$;

对于 100% 的数据,$n \leq 10^5$,$m \leq 2 \times 10^5$,$0 \leq d_i \leq 10^4$,$0 \leq l_i \leq 10^9$。第二类测试操作中 $0 \leq x_0 \leq 10^9$,修改操作中 $0 \leq x \leq 10^9$。

时间限制:$2\texttt{s}$

空间限制:$256\texttt{MB}$

来源

中国国家集训队互测2015 - By 陈思禹

下载

样例数据下载