题目描述
有 n 枚硬币,依次编号为 1,…,n。第 i 枚硬币的正面权值为 Ai,反面权值为 Bi,初始时全部正面朝上。
依次执行 m 次操作。第 j 次操作给定 Lj,Rj,Tj,把编号在 [Lj,Rj] 内、当前朝上一面的权值不超过 Tj 的硬币翻面。
求所有操作完成后,硬币朝上一面的权值之和。
输入格式
第一行一个整数 n。第二行 n 个整数 A1,…,An。第三行 n 个整数 B1,…,Bn。
第四行一个整数 m。接下来 m 行,每行三个整数 Lj,Rj,Tj。
输出格式
输出一行一个整数,表示操作结束后的权值之和。
样例
5
1 2 3 4 5
5 4 3 2 1
3
1 3 4
3 4 3
1 5 2
21
原题另外将大样例置于独立文件 name/name.in 与 name/name.ans。
数据范围
- 20% 的数据满足 n,m≤2×103。
- 另外 50% 的数据满足每次操作都有 Lj=1,Rj=n。
- 所有数据满足 1≤n,m≤105,1≤Lj≤Rj≤n,1≤Ai,Bi,Tj≤109。
原 PDF 题面第 1 页 · 原 PDF 题面第 2 页