分数: 433 分
问题陈述
高桥和青木管理 N 任务编号自 1 to N.
对于 i- 第一个任务,一个符号 S_i 代表负责人和工作费用
记录了 P_i 。当 S_i is T,负责人为高桥;当它是 A,负责人是青木。
在这里, 翻转 赋值意味着改变
给出了 T to A 和 A to T.
Q 查询。
对于 j第一条查询,您最多可以执行一次以下操作。也允许不执行该操作。
操作: 选择一对整数 (l, r) 满意 L_j \leq l \leq r \leq R_j,并翻转所有任务的分配 l-第 r-th。
考虑分配给 Aoki 的任务的总工作成本 (A)其中的任务 L_j-第 R_j- 操作后(或者如果未执行任何操作)。当操作被最佳选择时,找到该总数的最小值。
每个查询都是独立的。一个查询中的操作不会影响原始分配/成本信息或其他查询。
约束
- 1 \leq N \leq 10^5
- 1 \leq Q \leq 10^5
- S_i is
TorA - 1 \leq P_i \leq 10^9
- 1 \leq L_j \leq R_j \leq N
- N, Q, P_i, L_j, R_j 是整数
输入
N Q S_1 P_1 S_2 P_2 \vdots S_N P_N L_1 R_1 L_2 R_2 \vdots L_Q R_Q
- 第一行包含 N,任务数量,以及 Q,查询数量,以空格分隔。
- 以下 N 行给出每个任务的信息。
- 的 i- 这些行中包含 S_i,代表负责人 i第一个任务,以及 P_i,表示该任务的工作成本,以空格分隔。
- S_i is
TorA. - 以下 Q 行给出查询的信息。
- 的 j- 第这些行包含左端点 L_j 和右端点 R_j 的范围 j-第一个查询,以空格分隔。
输出
打印 Q 行。
关于 j第行,打印答案 j-第一个查询作为整数。
示例输入 1
5 4 A 3 T 5 A 2 T 4 A 6 1 5 2 4 3 3 4 5
示例输出 1
5 0 0 0
示例输入 2
6 5 T 7 T 1 T 4 A 10 A 2 T 8 1 3 4 6 1 6 2 5 5 5
示例输出 2
0 0 0 0 0
示例输入 3
12 8 A 8 T 3 T 12 A 5 A 20 T 7 A 1 T 15 T 6 A 9 T 4 A 11 1 12 1 6 4 10 7 12 2 2 5 9 3 11 8 10
示例输出 3
29 8 10 5 0 1 10 0
示例输入 4
25 15 T 100 A 250 T 30 A 400 A 50 T 600 T 70 A 800 T 90 A 1000 A 110 T 1200 T 130 A 1400 T 150 A 1600 T 170 T 1800 A 190 A 2000 T 210 A 2200 T 230 A 2400 T 250 1 25 1 10 6 20 11 25 3 17 8 8 14 19 2 24 5 15 16 23 7 13 20 25 1 1 12 12 9 21
示例输出 4
4680 790 3540 2670 2020 0 340 4680 1470 1810 90 440 0 0 3230
示例输入 5
1 1 A 1000000000 1 1
示例输出 5
0