Hamming Triples

题意翻译

有 $m$ 个长度为 $n$ 的01字符串，编号为 $1$ 到 $m$，每个字符串中的位都按升序或降序排列。 用 $H(a,b)$ 表示汉明距离，即两个相同长度的字符串对应位不同的位置的个数。计算所有由三个编号不同的串 $a,b,c$ 组成的三元组中，$H(a,b)+H(b,c)+H(c,a)$ 最大的三元组有多少个。 输入时将每个串用两个整数 $s_i\in[0,1]$ 和 $f_i\in[0,n]$ 来表示，意为串的前 $f_i$ 个位为 $s_i$，后 $n-f_i$ 个位为 $1-s_i$。

题目描述

Little Chris is having a nightmare. Even in dreams all he thinks about is math. Chris dreams about $ m $ binary strings of length $ n $ , indexed with numbers from 1 to $ m $ . The most horrifying part is that the bits of each string are ordered in either ascending or descending order. For example, Chris could be dreaming about the following 4 strings of length 5: The Hamming distance $ H(a,b) $ between two strings $ a $ and $ b $ of length $ n $ is the number of positions at which the corresponding symbols are different. Сhris thinks that each three strings with different indices constitute a single triple. Chris's delusion is that he will wake up only if he counts the number of such string triples $ a $ , $ b $ , $ c $ that the sum $ H(a,b)+H(b,c)+H(c,a) $ is maximal among all the string triples constructed from the dreamed strings. Help Chris wake up from this nightmare!

输入输出格式

输入格式

The first line of input contains two space-separated integers $ n $ and $ m $ ( $ 1<=n<=10^{9} $ ; $ 3<=m<=10^{5} $ ), the length and the number of strings. The next $ m $ lines contain the description of the strings. The $ i $ -th line contains two space-separated integers $ s_{i} $ and $ f_{i} $ ( $ 0<=s_{i}<=1 $ ; $ 1<=f_{i}<=n $ ), the description of the string with index $ i $ ; that means that the first $ f_{i} $ bits of the $ i $ -th string are equal to $ s_{i} $ , and the remaining $ n-f_{i} $ bits are equal to $ 1-s_{i} $ . There can be multiple equal strings in Chris's dream.

输出格式

Output a single integer, the number of such string triples among the given that the sum of the Hamming distances between the strings of the triple is maximal.

输入输出样例

输入样例 #1

5 4
0 3
0 5
1 4
1 5

输出样例 #1

3

输入样例 #2

10 4
1 5
0 5
0 5
1 5

输出样例 #2

4

题意翻译

有 $m$ 个长度为 $n$ 的01字符串，编号为 $1$ 到 $m$，每个字符串中的位都按升序或降序排列。 用 $H(a,b)$ 表示汉明距离，即两个相同长度的字符串对应位不同的位置的个数。计算所有由三个编号不同的串 $a,b,c$ 组成的三元组中，$H(a,b)+H(b,c)+H(c,a)$ 最大的三元组有多少个。 输入时将每个串用两个整数 $s_i\in[0,1]$ 和 $f_i\in[0,n]$ 来表示，意为串的前 $f_i$ 个位为 $s_i$，后 $n-f_i$ 个位为 $1-s_i$。