Description
- Kimi 最近得到了一个玩具,玩具由环和弦两个部分组成。环上有 2*N 个端
- 点,而 N 条弦,每条连接其中的两个,既不重复也不遗漏。Kimi 对这些弦产生
- 了浓厚的兴趣,他想数一数,一共有多少对弦是相交的呢?
Input
- 输入文件的第一行包含一个整数 N。
- 接下来 N 行,每行包含两个整数 a、b(1≤a,b≤2*N),表示一条连接 a,b 的弦
Output
- 输出文件中近包含一个整数,表示相交弦的对
Sample Input
3 2
5 2
6 3Sample Output
1题解
- 两条弦相交只需要保证其中一条的一个点在另一条的两个端点之间
- 然后树状数组or线段树维护一下前n个数有多少个左or右端点就好
1 |
|