← 返回题目列表

AtCoder · typical90_q

017. 交叉段(★7)

中文机器翻译题面 查看原题

配点: 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. (1 点) N \leq 1000, M \leq 1000
  2. (2 点) N \leq 1000, M \leq 100000
  3. (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