#P5266. 取名字

    ID: 4304 传统题 3000ms 128MiB 尝试: 8 已通过: 4 难度: 8 上传者: 标签>CF2400提高+/省选-离线查询添加/删除事件普通线段树树状数组局部离散化线段树上二分奇偶性分析

取名字

题目描述

有 nn 枚硬币,依次编号为 1,…,n1,\ldots,n。第 ii 枚硬币的正面权值为 AiA_i,反面权值为 BiB_i,初始时全部正面朝上。

依次执行 mm 次操作。第 jj 次操作给定 Lj,Rj,TjL_j,R_j,T_j,把编号在 [Lj,Rj][L_j,R_j] 内、当前朝上一面的权值不超过 TjT_j 的硬币翻面。

求所有操作完成后,硬币朝上一面的权值之和。

输入格式

第一行一个整数 nn。第二行 nn 个整数 A1,…,AnA_1,\ldots,A_n。第三行 nn 个整数 B1,…,BnB_1,\ldots,B_n。

第四行一个整数 mm。接下来 mm 行,每行三个整数 Lj,Rj,TjL_j,R_j,T_j。

输出格式

输出一行一个整数,表示操作结束后的权值之和。

样例

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%20\% 的数据满足 n,m≤2×103n,m\le 2\times10^3。
  • 另外 50%50\% 的数据满足每次操作都有 Lj=1,Rj=nL_j=1,R_j=n。
  • 所有数据满足 1≤n,m≤1051\le n,m\le10^5,1≤Lj≤Rj≤n1\le L_j\le R_j\le n,1≤Ai,Bi,Tj≤1091\le A_i,B_i,T_j\le10^9。

原 PDF 题面第 1 页 · 原 PDF 题面第 2 页