P13293 [GCJ 2013 #1C] The Great Wall

你正在研究中国长城的历史。长城是中国人为防御来自北方的军事入侵而修建的。为了简化问题，我们假设长城从东边的正无穷一直延伸到西边的负无穷。由于需要覆盖的距离太长，长城并不是一次性建成的。本题假设修建者采用了一种“被动应对”的策略：每当某段边境被成功攻破，长城就会在该段加高到足以抵御相同强度攻击的高度。 中国北部边境经常遭到游牧部落的进攻。为简化问题，我们假设每个部落在某个区间内以强度 $S$ 发起攻击。要抵御这次攻击，长城在该区间上必须处处高度不低于 $S$。只要有哪怕一小段低于 $S$，攻击就会在那里突破并成功。注意，即使攻击成功，也不会损坏长城。每次攻击结束后，所有被攻击且高度低于 $S$ 的长城段都会被加高到 $S$——也就是说，长城会以最小的方式加固到足以抵御本次攻击的高度。需要注意的是，如果在同一天有多次攻击，这些攻击都在当天结束后统一加固，且加固到能同时抵御所有当天攻击的最低高度。 由于游牧部落是游牧的，他们不一定只进攻一次。实际上，他们会不断东移或西移，并定期进攻长城。为简化问题，假设他们以恒定速度移动，并以恒定时间间隔发起攻击；此外，假设同一部落每次进攻的强度变化也是恒定的（可能因消耗而减弱，也可能因经验而增强）。 假设最初（公元前 250 年）长城尚未修建（即任意位置高度为 0），并给出所有游牧部落的完整攻击描述，请你求出有多少次攻击是成功的。

输入的第一行为测试用例数 $T$。接下来有 $T$ 个测试用例。每个测试用例第一行为一个整数 $N$，表示进攻长城的部落数。接下来的 $N$ 行，每行描述一个部落，包含八个整数 $d_i$、$n_i$、$w_i$、$e_i$、$s_i$、$\text{delta\_d}_i$、$\text{delta\_p}_i$ 和 $\text{delta\_s}_i$，含义如下： - $d_i$ —— 该部落首次攻击的日期（以公元前250年1月1日为第0天） - $n_i$ —— 该部落的攻击次数 - $w_i$、$e_i$ —— 首次攻击时进攻区间的最西端和最东端 - $s_i$ —— 首次攻击的强度 - $\text{delta\_d}_i$ —— 该部落每次攻击之间的天数 - $\text{delta\_p}_i$ —— 该部落每次攻击后向东（正数）或向西（负数）移动的距离 - $\text{delta\_s}_i$ —— 该部落每次攻击后强度的变化量

对于每个测试用例，输出一行 "Case #x: y"，其中 $x$ 为测试用例编号（从1开始），$y$ 为成功的攻击次数。

**样例说明** 在第一个样例中，第一个部落攻击三次：第0天攻击 $[0,2]$，强度为 $10$，第2天攻击 $[3,5]$，强度为 $8$，第4天攻击 $[6,8]$，强度为 $6$；这三次都成功。然后第二个部落攻击三次，每次强度为 $8$——第10天攻击 $[2,3]$（例如在 $2.5$ 处，长城高度仍为 $0$，所以成功），第17天攻击 $[4,5]$（失败，因为 $[3,5]$ 区间长城已经加高到 $8$），第24天攻击 $[6,7]$（成功，因为那里长城高度只有 $6$）。 在第二个样例中，有三个部落，攻击交错进行。顺序如下： - 第0天，部落2攻击 $[0,1]$，高度 $7$，成功。 - 第1天，部落1攻击 $[0,5]$，高度 $10$，部落2攻击 $[2,3]$，高度 $9$。由于是同一天，这两次都成功（加固是在所有攻击结束后才进行的）。 - 第2天，部落2攻击 $[4,5]$，高度 $11$，成功（那里的长城高度原本为 $10$）。 - 第3天，部落1攻击 $[8,13]$，高度 $10$，成功。同时部落3攻击 $[0,5]$，高度 $1$，失败（该区间长城已有高度 $10$ 和 $11$）。 - 第4天，部落3攻击 $[4,9]$，高度 $1$，成功（$[5,8]$ 区间没有长城）。 - 第5天，部落3攻击 $[8,13]$，高度 $1$，失败（该区间长城高度为 $10$）。 **限制条件** - $1 \leq T \leq 20$ - $0 \leq d_i$ - $1 \leq \text{delta\_d}_i \leq 676060$ - $d_i + (n_i - 1) \times \text{delta\_d}_i \leq 676060$ - $1 \leq s_i \leq 10^6$ - $-10^5 \leq \text{delta\_s}_i \leq 10^5$ - $s_i + (n_i - 1) \times \text{delta\_s}_i \geq 1$ **小数据集（9 分，测试集 1 - 可见）** - $1 \leq N \leq 10$ - $1 \leq n_i \leq 10$ - $-100 \leq w_i < e_i \leq 100$ - $-10 \leq \text{delta\_p}_i \leq 10$ **大数据集（28 分，测试集 2 - 隐藏）** - $1 \leq N \leq 1000$ - $1 \leq n_i \leq 1000$ - $-10^6 \leq w_i < e_i \leq 10^6$ - $-10^5 \leq \text{delta\_p}_i \leq 10^5$ 翻译由 ChatGPT-4.1 完成。