← 返回题目列表

AtCoder · awc0087_e

E. 更改指定间隔

中文机器翻译题面 查看原题

分数: 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 T or A
  • 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 T or A.
  • 以下 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