寻找奇点

陈叔的芯片在终端上投射出一片密集的光点——G-30 矿区的守卫部署图。但这些光点不是单独给出的，而是用 $N$ 个等差序列压缩描述的：每个序列给出起始位置 $S$、结束位置 $E$、公差 $D$，代表守卫部署在 $S, S+D, S+2D, ..., E$ 这些位置上。

"这么多位置……"CC 盯着屏幕上滚动的数字，"咋个找那个奇点？"

"猜数字。"你说，"守卫只在整数位置上。我们要找一个位置 $x$，使得所有序列中包含 $x$ 的序列个数是奇数。"

"一个个数？"老周摇头，"数到明年。"

"不用一个个数。"你在终端上画了一条数轴，"假设我们要找的位置在左边一半还是右边一半。取中点，统计所有序列中小于等于中点的守卫总数。如果这个总数是奇数，说明奇点在左边；如果是偶数，说明奇点在右边。"

"就像猜数字。"CC 说，"大了还是小了，每次砍掉一半。"

"对。"

你开始写。对于每个等差序列，计算它在前半段范围内有多少个元素——用公式快速算出个数。把所有序列的结果加起来，判断奇偶性。

屏幕上，搜索范围像被刀切一样一次次减半——从大的一半开始，一刀一刀，直到范围缩小到单个数字。

"找到了。"你说，"位置 47。"

"又是 47。"CC 说。

Echo 没说话。但她的投影在"47"这个数字上停留了很久。

老周和陈叔对视了一眼。老周说："47 号井架。那里只有一个守卫——Zero 的防御最薄弱的地方。"

"那就是突破口。"CC 把数据刀握在手里，"走。"

题目描述

$N$ 个等差序列，每个序列给出 $S, E, D$，表示守卫部署在 $S, S+D, S+2D, ..., E$ 这些位置上。求一个位置 $x$，使得包含 $x$ 的序列个数为奇数。

输入格式

$N$。然后 $N$ 行，每行 $S, E, D$。

输出格式

位置 $x$。

输入样例

5
2 -1 3 -2 5

输出样例

3 -1
3 -1
3 -1
3 -1
3 -1

提示

• 二分搜索。取中点 $mid$，统计所有序列中小于等于 $mid$ 的元素总数。
• 若总数为奇数，奇点在左边；否则在右边。
• 等差序列在 $[L, R]$ 范围内的元素个数：$\max(0, \lfloor \frac{\min(E, R) - S}{D} \rfloor + 1)$。

综合防线

八道题，八道锁，全部解开。

走廊尽头的门向两侧滑开，露出后面真正的通道——通往G-20矿区的主干道。Echo站在门前，投影比之前任何时候都更明亮。

"下一层。"她说，"是数据结构。"

"又是数据结构？"CC问。

"对。"Echo说，"这次是树状数组和线段树——用来维护大范围数据的工具。"

[下一章：树状数组与线段树 —— G-20矿区]