题意概括

维护 $n$ 个频率（$1 \sim n$）的开关状态，两个开启的频率若不互质就会干扰。
支持切换单个频率开关，查询区间 $[l,r]$ 内是否存在一对开启的频率相互干扰。

核心思路

关键转化：
两个数不互质 ⇔ 它们有公共质因子。
因此，若区间内存在一个质数 $p$，使得 $p$ 的倍数有至少 两个不同的开启频率，则答案為 DA，否则為 NE。

算法步骤

1. 预处理

   • 筛出 $1 \sim n$ 的质数，并求出每个数的质因子集合。

2. 维护数据结构

   • 对每个质数 $p$，用 set 或线段树维护是 $p$ 的倍数且当前开启的频率集合。
   • 全局维护一个 set 记录所有当前开启的频率。

3. 查询处理

   • 对询问 $[l,r]$，枚举 $l \sim r$ 中某个开启的频率 $x$ 的一个质因子 $p$。
   • 在 $p$ 对应的开启频率集合中，查找是否存在另一个频率 $y \in [l,r]$ 且 $y \neq x$。
   • 若找到则输出 DA，否则 NE。

4. 优化

   • 只需检查每个开启频率的最小质因子即可覆盖所有情况。
   • 使用线段树维护每个质数 $p$ 对应的最小/第二大开启位置，可 $O(\log n)$ 查询。

复杂度

• 预处理 $O(n \log \log n)$
• 每次操作 $O(\log n)$ 或 $O(\log^2 n)$
• 可通过 $n \leq 10^6, q \leq 2\times 10^5$