T3 segment
题目描述
请注意本题特殊的时间限制。
你找到一款抽象游戏：MD-MC。
这款游戏的背景是 $m$ 维空间，有 $n$ 个信标处在空间中，第 $i$ 个信标第 $j$ 维的坐标为 $x_{i,j}$，初始耐久度为 $v_i$。
如果一个信标的耐久度变为负数，这个信标将立即损坏。
在游戏中，顺序发生了 $q$ 次天灾。
对于第 $i$ 次天灾：
- 其影响范围为一个超长方体，该超长方体的第 $j$ 维下界为 $l_{i,j}$，上界为 $r_{i,j}$ （包含）；
- 将所有处在影响范围内的信标的耐久度减少 $c_i$。
你想知道，在前 $i$ 次天灾发生后，还有多少信标没有损坏。
输入格式
第一行三个整数 $n,m,q$。
接下来 $n$ 行，第 $i+1$ 行有 $m+1$ 个整数，表示 $x_{i,1},x_{i,2},\dots,x_{i,m},v_i$。
接下来 $q$ 行，第 $i+n+1$ 行有 $2m+1$ 个整数，表示 $l_{i,1},r_{i,1},l_{i,2},r_{i,2},\dots,l_{i,m},r_{i,m},c_i$。
为减少本题代码难度，保证对于 $j\in[1,m]\cap\mathbb{N}$，$x_{1,j},x_{2,j},\dots,x_{n,j}$ 构成一个 $1\sim n$ 的排列。
输出格式
共 $q$ 行，第 $i$ 行一个整数，表示在前 $i$ 次天灾发生后，还有多少信标没有损坏。
样例
样例输入 #1
6 2 5
3 4 1
6 3 1
5 1 1
1 6 1
2 5 1
4 2 1
3 4 3 5 1
6 6 3 6 2
1 2 3 6 2
2 3 4 6 1
1 6 1 6 2样例输出 #1
6
5
3
2
0样例 $2$
见附件中的 ex_segment2.in 与 ex_segment2.ans。
样例 $3$
见附件中的 ex_segment3.in 与 ex_segment3.ans。
数据范围
对于所有数据，$1\leq n\leq 10^4$，$1\leq m\leq 5$，$1\leq q\leq 5\times 10^6$，$0\leq v_i\leq10^6$，$1\leq c_i\leq10^9$，$1\leq x_{i,j},l_j,r_j\leq n$。
保证对于 $j\in[1,m]\cap\mathbb{N}$，$x_{1,j},x_{2,j},\dots,x_{n,j}$ 构成一个 $1\sim n$ 的排列。
| 测试点编号 | $n=$ | $m=$ | $q=$ | $v_i\leq$ | 分值 | 时限 |
|---|---|---|---|---|---|---|
| $1$ | $10^3$ | $5$ | $2\times10^5$ | $10^6$ | $10$ | $6s$ |
| $2$ | $10^4$ | $1$ | $5\times10^5$ | $10^6$ | $20$ | $6s$ |
| $3$ | $10^4$ | $5$ | $5\times10^5$ | $0$ | $30$ | $6s$ |
| $4$ | $10^4$ | $5$ | $5\times10^5$ | $10^6$ | $20$ | $6s$ |
| $5$ | $10^4$ | $5$ | $5\times10^6$ | $10^6$ | $20$ | $30s$ |
为防止选手在读入上造成大量的时间开销，本题下发了 fastio.cpp 文件。
同时，为防止出题人丑陋的 fastio 污染到选手的眼睛，建议使用 fastio 时将其中的 FASTIO 命名空间折叠。