Luogu7470

题意：给出 个二元组 。

给出参数 ，若一个二元组满足 ，则称为好的。

每次询问给出 ，询问 区间 中有多少个二元组是好的。

允许离线。 ，时限 。

---

考虑如何解决静态问题（先给出全部数据，然后再询问），然后套用线段树即可解决原问题。

考虑 的情况，将所有 插入一棵字典树，在 的意义下查询 的数的个数，容易求解。

再考虑 的情况，让每个数据主动向询问贡献。

（限制中的 均为对称的二元运算，因此，修改和询问地位的不同之处只在于贡献方向，转置后就是相同的）

即，将所有 插入字典树，在 的意义下，将所有 的对应询问均加一。

这样，对于询问 ，前者会统计到所有 的贡献，后者则统计到所有 的贡献。

---

考虑 约束同时存在的问题。

将数据 按照 排序，利用逐次插入维护 的集合，在其中查询 的贡献。

然后需要补上 的集合中 的贡献。

这可以将询问 按照 排序，利用逐次插入维护 的集合，并在其中对 的所有询问打上加一标记。

处理静态子问题的时空复杂度均为 。

回到原问题，由于允许离线，可以 dfs 线段树并处理，这样就能做到时间 ，空间 。