E - Change of Assigned Interval Editorial /

Time Limit: 2 sec / Memory Limit: 1024 MiB

配点 : 433 点

問題文

高橋君と青木君は N 個の仕事を番号 1 から N で管理しています。

i 番目の仕事には、担当者を表す記号 S_i と作業コスト P_i が記録されています。S_i が T のとき担当者は高橋君、A のとき担当者は青木君です。

ここで、担当の 反転 とは、T を A に、A を T に変更することを指します。

Q 個の問い合わせが与えられます。

j 番目の問い合わせでは、次の操作を高々 1 回行うことができます。操作を行わないことも許されます。

操作： L_j \leq l \leq r \leq R_j を満たす整数の組 (l, r) を 1 つ選び、l 番目から r 番目までのすべての仕事について担当を反転する。

操作後（または操作を行わなかった場合）における、L_j 番目から R_j 番目までの仕事のうち青木君（A）が担当する仕事の作業コストの合計を考えます。操作の仕方を最適に選んだとき、この合計の最小値を求めてください。

各問い合わせは独立です。ある問い合わせでの操作は、元の担当・コストの情報や他の問い合わせには影響しません。

制約

  • 1 \leq N \leq 10^5
  • 1 \leq Q \leq 10^5
  • S_i は T または 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
  • 1 行目には、仕事の個数を表す N と、問い合わせの個数を表す Q が、スペース区切りで与えられる。
  • 続く N 行では、各仕事の情報が与えられる。
  • このうち i 行目には、i 番目の仕事の担当者を表す S_i と、その仕事の作業コストを表す P_i が、スペース区切りで与えられる。
  • S_i は T または A である。
  • 続く Q 行では、問い合わせの情報が与えられる。
  • このうち j 行目には、j 番目の問い合わせで対象となる範囲の左端 L_j と右端 R_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

Score : 433 pts

Problem Statement

Takahashi and Aoki manage N tasks numbered from 1 to N.

For the i-th task, a symbol S_i representing the person in charge and a work cost P_i are recorded. When S_i is T, the person in charge is Takahashi; when it is A, the person in charge is Aoki.

Here, flipping the assignment means changing T to A and A to T.

Q queries are given.

For the j-th query, you may perform the following operation at most once. It is also permitted to not perform the operation.

Operation: Choose a pair of integers (l, r) satisfying L_j \leq l \leq r \leq R_j, and flip the assignment of all tasks from the l-th to the r-th.

Consider the total work cost of tasks assigned to Aoki (A) among the tasks from the L_j-th to the R_j-th after the operation (or if no operation is performed). Find the minimum value of this total when the operation is chosen optimally.

Each query is independent. An operation in one query does not affect the original assignment/cost information or other queries.

Constraints

  • 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 are integers

Input

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
  • The first line contains N, the number of tasks, and Q, the number of queries, separated by a space.
  • The following N lines give the information of each task.
  • The i-th of these lines contains S_i, representing the person in charge of the i-th task, and P_i, representing the work cost of that task, separated by a space.
  • S_i is T or A.
  • The following Q lines give the information of the queries.
  • The j-th of these lines contains the left endpoint L_j and right endpoint R_j of the range for the j-th query, separated by a space.

Output

Print Q lines.

On the j-th line, print the answer to the j-th query as an integer.

Sample Input 1

5 4
A 3
T 5
A 2
T 4
A 6
1 5
2 4
3 3
4 5

Sample Output 1

5
0
0
0

Sample Input 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

Sample Output 2

0
0
0
0
0

Sample Input 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

Sample Output 3

29
8
10
5
0
1
10
0

Sample Input 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

Sample Output 4

4680
790
3540
2670
2020
0
340
4680
1470
1810
90
440
0
0
3230

Sample Input 5

1 1
A 1000000000
1 1

Sample Output 5

0