题解

思路

把不等式 $x_u<x_v$ 看作有向边 $u\to v$。若图有环，即使全部使用存在量词也无法让严格不等式同时成立。

在有向无环图中，变量 $x_i$ 能使用全称量词，当且仅当它与所有更早出现的变量都不可达。否则对手可以给 $x_i$ 一个破坏已有大小关系的实数。不可达时，任意取值都不会与过去产生约束，因而可以安全使用全称量词。

做法

先拓扑排序检测有向环。

令 ancestor[i] 为能够到达 $i$ 的顶点及 $i$ 自身中的最小编号。按拓扑序沿边转移即可求出。类似地，按逆拓扑序求 descendant[i]，表示从 $i$ 可达的顶点及自身中的最小编号。

当 min(ancestor[i], descendant[i]) == i 时，不存在编号小于 $i$ 且与它可达的顶点，令第 $i$ 个量词为 A；否则令其为 E。所有可用 A 的位置彼此独立，因此全部选择即可得到唯一的最大方案。

小范围可以枚举所有量词串并用传递闭包验证；中等范围直接计算整张图的传递闭包。

复杂度

满分算法时间复杂度为 $O(n+m)$，空间复杂度为 $O(n+m)$。