给定长度为 $N$ 的序列，求满足 $i < j < k$ 且 $a[i] < a[j] < a[k]$ 的三元组个数。$N \le 10^5$，$a_i \le 10^9$。通过枚举中间位置 $j$，利用权值树状数组分别统计左右两侧的可行元素个数，$O(N \log N)$ 解决。

1. 题目数据 (Problem Metadata) 题目类型：传统题 题目链接：Problem - 670C - Codeforces 时间限制：2 秒 内存限制：256 MB 2. 题意简述 (Problem Summary) 给定 $n...

提供离散化的数组与 vector 两种代码模板，包含排序去重、lower_bound 查询映射关系，适用于值域压缩场景。

离散化是排序算法对于线性降维的一个重要应用。通常情况下，如果一组数值域很大，但是只考虑他们的大小关系，则可以通过离散化的方式将值域降维到不重复元素个数（和数组长度同数量级）。 比如：$[1,20,300,4234,51234,64321,114514...

NOI 2015 约束满足问题，利用并查集维护相等关系的传递性，离散化压缩变量编号后判定不等约束是否冲突，时间复杂度 O(n α(n))。