题解

大力相应 teacher 要求。

正难则反，考虑求不合法的三元组的数量。

对于一个不合法的三元组，可以发现条件等价于三元组中有一个点出度为 2。记 \(m\) 次操作后每个点出度为 \(d_i\)，答案就是 \(\dbinom{n}{3}-\sum\limits_{i=1}^n\dbinom{d_i}{2}\)。

那么怎么统计？回忆 \(\mathcal{O}(nm)\) 的做法，数组 \(a_{i,j}\) 表示 \(i,j\) 间边的方向。假设当次修改影响的区间是 \([l,r]\)，那么这个修改就是 \(\forall i,j\in[l,r]\)，\(a_{i,j}\gets a_{i,j}\oplus 1\)。显然可以对 \(j\) 这一维差分。

更进一步的，我们可以对操作应用差分的思想。更具体的，我们枚举 \(i\)，用线段树维护 \(a\) 数组，每个修改 \([l,r]\) 就是在 \(i\) 为 \(l\) 或 \(r+1\) 的时候区间异或一下。时间复杂度 \(\mathcal{O}(n\log n)\)。