Train Maintenance

题面翻译

题目描述：

有 $n$ 种列车，第 $i$ 种列车每工作 $x_i$ 天就要维护 $y_i$ 天。

接下来的 $m$ 天中，每天有一个操作，分为加入一列车和删除一列车。在车刚加入的那一天，它刚维修完，即加进来的那天可以正常工作。

每一天的操作完成后，你都要回答，当前有多上车在维修？

输入格式

第一行两个整数 $n,m$。

接下来 $n$ 行，第 $i+1$ 行每行两个整数 $x_i,y_i$。

接下来 $m$ 行，每行两个正整数 $op,k$，描述当天的操作：

若 $op=1$，表示加入一列 $k$ 种类的车，保证当前没有 $k$ 种类的车；

若 $op=2$，表示删除一辆 $k$ 种类的车，保证当前有且仅有一列 $k$ 种类的车。

输出格式

$m$ 行，表示每组询问的答案。

数据范围：

$1\le n,m\le 2\times 10^5$。

$1\le x_i,y_i\le 10^9$。

$op=1$ 或 $op=2$。

$1\le k\le n$。

题目描述

Kawasiro Nitori is excellent in engineering. Thus she has been appointed to help maintain trains.

There are $n$ models of trains, and Nitori's department will only have at most one train of each model at any moment. In the beginning, there are no trains, at each of the following $m$ days, one train will be added, or one train will be removed. When a train of model $i$ is added at day $t$ , it works for $x_i$ days (day $t$ inclusive), then it is in maintenance for $y_i$ days, then in work for $x_i$ days again, and so on until it is removed.

In order to make management easier, Nitori wants you to help her calculate how many trains are in maintenance in each day.

On a day a train is removed, it is not counted as in maintenance.

输入格式

The first line contains two integers $n$ , $m$ ( $1 \le n,m \le 2 \cdot 10^5$ ).

The $i$ -th of the next $n$ lines contains two integers $x_i,y_i$ ( $1 \le x_i,y_i \le 10^9$ ).

Each of the next $m$ lines contains two integers $op$ , $k$ ( $1 \le k \le n$ , $op = 1$ or $op = 2$ ). If $op=1$ , it means this day's a train of model $k$ is added, otherwise the train of model $k$ is removed. It is guaranteed that when a train of model $x$ is added, there is no train of the same model in the department, and when a train of model $x$ is removed, there is such a train in the department.

输出格式

Print $m$ lines, The $i$ -th of these lines contains one integers, denoting the number of trains in maintenance in the $i$ -th day.

样例 #1

样例输入 #1

3 4
10 15
12 10
1 1
1 3
1 1
2 1
2 3

样例输出 #1

0
1
0
0

样例 #2

样例输入 #2

5 4
1 1
10000000 100000000
998244353 1
2 1
1 2
1 5
2 5
1 5
1 1

样例输出 #2

0
0
0
1

提示

Consider the first example:

The first day: Nitori adds a train of model $3$ . Only a train of model $3$ is running and no train is in maintenance.

The second day: Nitori adds a train of model $1$ . A train of model $1$ is running and a train of model $3$ is in maintenance.

The third day: Nitori removes a train of model $1$ . The situation is the same as the first day.

The fourth day: Nitori removes a train of model $3$ . There are no trains at all.