#P18461. Ursa Minor

Ursa Minor

Ursa Minor

World Rebuilder 原题像素画

像素画作者:Ambition、Sulfox 和 Charles。

耳廓狐 Sulfox 高高兴兴地度过了他的 20 岁生日,因为他收到了一件特别的礼物:一款名为 World Rebuilder 的像素游戏。他在游戏中扮演一位星际探险家,向着小熊座中最亮的恒星——北极星 Polaris 前进,并改造沿途的星球。

一个游戏关卡由目标序列 a1,a2,…,ana_1,a_2,\ldots,a_n 和工具序列 b1,b2,…,bmb_1,b_2,\ldots,b_m 决定。在关卡开始时,Sulfox 所降落星球的赤道上环形排列着 nn 块大陆,所有大陆的初始海拔都是 00。

“批量编辑(Batch Edit)”工具可以同时修改多块大陆的海拔。每次使用工具时,Sulfox 先从工具序列中选择一个数 kk,再选择一个任意实数 xx,随后选取环上恰好 kk 块连续大陆,将每块被选大陆的海拔都加上 xx。环的末尾与开头相邻;xx 可以为负数或非整数,中间海拔也没有非负限制。

当存在一个起始大陆和一个行进方向,使从那里出发沿该方向依次看到的 nn 块大陆的海拔恰为 a1,a2,…,ana_1,a_2,\ldots,a_n 时,这一关便通关了。每次操作都可以重新选择工具序列中的数、实数 xx 和连续大陆的位置,工具可以使用任意多次。

使用批量编辑工具调整海拔;被选中的大陆高亮显示

遗憾的是,游戏的关卡设计师十分懒惰。他只是从全局目标序列 A1,A2,…,ANA_1,A_2,\ldots,A_N 和全局工具序列 B1,B2,…,BMB_1,B_2,\ldots,B_M 中各选取一个连续子序列,便生成了一关。他甚至没有检查关卡能否通关,以至于 Sulfox 卡在了一些被标为“简单”的关卡上!

幸好,电子游戏总会通过多次版本更新修复错误(也可能引入新错误,谁知道呢)。现在给定初始版本的全局目标序列和全局工具序列,你需要依次处理以下两类事件:

  • 游戏更新:在新版本中,将 ApA_p 的值修改为 vv。
  • 关卡询问:在最新版本中,判断目标序列为 Al,Al+1,…,ArA_l,A_{l+1},\ldots,A_r、工具序列为 Bs,Bs+1,…,BtB_s,B_{s+1},\ldots,B_t 的关卡能否通关。

每次询问所描述的关卡都从所有海拔为 00 的初始状态开始;它不继承此前询问中的操作。全局工具序列不会被修改。

输入格式

第一行包含三个整数 N,M,QN,M,Q(1≤N,M,Q≤2×1051\le N,M,Q\le 2\times10^5),分别表示全局目标序列的长度、全局工具序列的长度和事件数。

第二行包含 NN 个整数 A1,A2,…,ANA_1,A_2,\ldots,A_N(0≤Ai≤1090\le A_i\le10^9),表示初始版本的全局目标序列。

第三行包含 MM 个整数 B1,B2,…,BMB_1,B_2,\ldots,B_M(1≤Bi≤N1\le B_i\le N),表示全局工具序列。

接下来 QQ 行,每行描述一个事件,格式为以下两种之一:

  • U p v:将 ApA_p 赋值为 vv,其中 1≤p≤N1\le p\le N,0≤v≤1090\le v\le10^9。
  • Q l r s t:询问目标序列为 Al,…,ArA_l,\ldots,A_r、工具序列为 Bs,…,BtB_s,\ldots,B_t 的关卡能否通关。其中 1≤l≤r≤N1\le l\le r\le N,1≤s≤t≤M1\le s\le t\le M,并保证本次选中的每个工具长度 Bs,…,BtB_s,\ldots,B_t 都不超过 r−l+1r-l+1。

上述所有下标从 11 开始,所有区间均包含两个端点。未选中的工具长度可以大于当前关卡长度。输入只有一组全局序列,没有多组数据或额外的总规模限制。工具长度可重复出现。

输出格式

对于每个 Q 事件,输出一行:能通关时输出 Yes,否则输出 No,注意大小写。U 事件没有输出;若全部事件都是更新,则没有输出行。

原样例

6 4 5
1 1 4 5 1 4
3 3 2 4
Q 1 5 1 2
Q 2 5 3 4
U 5 2
Q 1 6 1 2
Q 2 5 3 4
Yes
No
No
Yes