配点: 7 点
問題文
在圆周上 N 个点,并按顺时针方向 1, 2, \ldots, N 编号。此外,M 条线段,线段 i 是点 L_i 和点 R_i 。
線分 s,t 在非端点处相交的情况下, 请问(s,t) (1 \leq s \lt t \leq M) 的组合数量。
制約
- 3\leq N\leq 300000
- 2\leq M\leq 300000
- 1\leq L_i < R_i\leq N
- (L_i, R_i) \neq (L_j, R_j) (1 \leq i \lt j \leq M)
小課題
- (1 点) N \leq 1000, M \leq 1000
- (2 点) N \leq 1000, M \leq 100000
- (4 点)无附加约束 打印第
入力
输入是按以下格式从标准输入给出的。
N M L_1 R_1 L_2 R_2 \vdots L_M R_M
出力
線分 s,t 在非端点处相交的情况下 请输出 (s,t) (1 \leq s \lt t \leq M) 的组合数量。
入力例 1
6 3 2 5 1 4 1 3
出力例 1
2
入力例 2
250 10 13 218 17 99 24 180 53 115 96 97 111 158 124 164 135 227 158 177 204 224
出力例 2
10
入力例 3
100 10 1 2 1 3 1 4 1 5 1 6 1 7 1 8 1 9 1 10 1 11
出力例 3
0
入力例 4
100 10 1 100 2 99 3 98 4 97 5 96 6 95 7 94 8 93 9 92 10 91
出力例 4
0
入力例 5
1000 40 12 43 23 59 32 118 44 751 68 136 70 168 85 328 88 809 92 981 95 540 98 772 98 903 125 896 173 737 199 325 212 369 227 587 230 374 287 442 306 926 314 858 316 371 318 493 337 506 384 887 387 493 394 457 404 652 414 527 422 920 441 730 445 620 468 602 482 676 568 857 587 966 653 757 710 928 764 927 778 916
出力例 5
229