c++# 「GMOI R2-T4」电子木鱼## 题目背景运营电子资本招聘赛博佛祖积累虚拟功德。功德无量随喜赞叹。## 题目描述给你 $n$表示一共有 $n$ 位赛博佛祖编号依次为 $1 sim n$。第 $i1 leq i leq n$ 位赛博佛祖可以对应为一个二元组 $langle S_i d_i rangle$其中 $S$ 在任意时刻均为 $1 2 3 dots m$ 的一个子集可以为空而 $

分析：

一道很有意思的题目，考虑这样一个问题，如果所有的 $S_i$ 都是不同的，该怎么做？

我们可以考虑暴力模拟，按照题目的定义模拟一遍即可，但是这道题目最重要的地方在于如何优化。

我们考虑一个问题，如果当前某一个 $S_i$ 为空集，那么必然存在一个 $d_i \in {1,\dots,m}$，使得 $d_i\in S_j$，那么我们可以把 $d_i$ 从 $S_j$ 中移除，这样在下一个时刻，$S_j$ 就有可能成为空集了，这样我们就可以先枚举 $d_i$，再枚举 $i$，然后把 $d_i$ 从 $S_j$ 中移除，这样就不用重新枚举整个 $S$ 了，复杂度就变成了 $\mathcal{O}(nm\log m)$。

然后我们考虑 $S_i$ 不同的情况，我们发现如果 $S_i$ 不同，那么 $d_i$ 也不可能相等，所以我们可以将 $S_i$ 排序，然后通过排序后的位置来判断是否为相等的 $S$。注意到因为 $S$ 是二元组而不是单个数组，所以不能直接排序，我们可以将 $S$ 看成二进制数，然后排序即可。

然后我们再考虑询问怎么做，我们可以考虑将询问离线下来，按照 $r$ 排序，然后从小到大依次加入 $[l,r]$ 中的佛祖，因为 $r$ 越来越大，所以每次加入的佛祖对后面的操作都不会有影响，这样我们就可以做到 $\mathcal{O}(n^2+m2^m\log m)$ 的时间复杂度。

代码：