NOIp 模拟赛考了，遂记之。

容易发现 $\nexists(A,B,C)$ 使 $\forall S$ 满足 $\lvert S \rvert>3$，因为 $(A,B,C)$ 中只有 $3$ 个元素，多了就放不进去了。

考虑分 $3$ 中情况讨论。

对于第 $1$ 中情况，$\lvert S \rvert=1$。

因为 $a,b,c$ 都是排列所以一定不存在重复的 $(A,B,C)$，自然答案就是 $n$。

对于第 $2$ 种情况，$\lvert S \rvert=2$。

考虑使用容斥，显然总方案为 $n\choose 2$，考虑怎么计算不合法的方案。

在这个情况下，不合法的方案显然就是 $(A,B,C)$ 全部来自一个位置。

换而言之，不合法的数量就是 $\sum\limits_{i=1}^n\sum\limits_{j=i+1}^n [(a_i<a_j)\wedge (b_i< b_j)\wedge (c_i<c_j)]$。

发现是三维偏序，直接用 CDQ 分治就可以求解。

对于第 $3$ 种情况，$\lvert S\rvert=3$。

继续使用容斥，显然总方案为 $n\choose 3$，还是考虑怎么计算不合法方案。

不合法的方案就是一个位置取超过 $2$ 个三元组中的元素，考虑分别考虑 $AB,AC,BC$。

确定了对象之后直接二位偏序处理，但是需要把多减的三个元素选都是一个位置的情况加回来。

Submission #58377417 - Snuke's Birthday Contest