「NnOI R2-T3」Horizon Blue

Luogu
IDLGP9571
Time500ms
Memory512MB
DifficultyP4
数学洛谷原创O2优化
小 C 喜欢在画板上画画。他进行了 $ n $ 次操作,每次操作有如下三种可能: - ```1 k b``` 代表小 C 绘制了一条解析式为 $ y=kx+b $ 的直线。 - ```2 k b``` 代表小 C 询问你直线 $ y=kx+b $ 与多少条被绘制的直线有**恰好**一个公共点。 - ```3 k b``` 代表小 C 擦除所有与直线 $ y=kx+b $ 有**至少**一个公共点的直线。 **注意:两条重合的直线有无数个交点。** **注意:询问时重合的直线应分别计算。** ## Input 第一行一个整数 $ n $。 接下来 $n$ 行,每行三个整数 $ 1/2/3,k,b $,代表一次操作。 ## Output 对每次 ```2 k b``` 操作,输出满足要求的直线数量。 [samples] ## Note **【样例 1 解释】** 第 1 次操作,绘制直线 $ y=x $。 第 2 次操作,绘制直线 $ y=-x $。 第 3 次操作,可以发现直线 $ y=2x+1 $ 与前两条线相交。 第 4 次操作,擦掉所有 $ y=x+3 $ 相交的线,直线 $ y=-x $ 被擦掉。 第 5 次操作,$ y=2x+1 $ 显然与 $ y=x $ 相交。 第 6 次操作,$ y=x+1 $ 与 $ y=x $ 斜率相等,是平行线,不相交。 **【数据范围】** 对于 $ 100\% $ 的数据,$ 1 \le n \le 10^5 $,$ 1 \le |k| \le 10^5 $,$ 0 \le |b| \le 10^5 $。 **提示:本题开启捆绑测试。** $$ \def\r{\cr\hline} \def\None{\text{None}} \def\arraystretch{1.5} \begin{array}{c|c|c} \textbf{Subtask} & \textbf{Sp. Constraints} & \textbf{Score}\r \textsf1& n \le 5000 & 27 \r \textsf2& \vert k\vert,\vert b\vert \le 50 & 21 \r \textsf3& 无第\ 3\ 类操作 & 13 \r \textsf4& 第\ i\ 次操作满足\ k=i & 14 \r \textsf5& 无特殊限制 & 25 \r \end{array} $$ 在赛后新添加的 hack 测试点将放入 subtask 6。 ### 题目来源 | 项目 | 人员 | |:-:|:-:| | idea | 船酱魔王 | | data | 船酱魔王 | | check | EstasTonne | | solution | 船酱魔王 |
Samples
Input #1
6
1 1 0
1 -1 0
2 2 1
3 1 3
2 2 1
2 1 1
Output #1
2
1
0
Input #2
10
1 1 0
1 1 0
2 1 1
2 1 0
2 2 5
3 1 0
2 2 5
1 2 3
1 3 4
2 3 5
Output #2
0
0
2
0
1
API Response (JSON)
{
  "problem": {
    "name": "「NnOI R2-T3」Horizon Blue",
    "description": {
      "content": "小 C 喜欢在画板上画画。他进行了 $ n $ 次操作,每次操作有如下三种可能: - ```1 k b``` 代表小 C 绘制了一条解析式为 $ y=kx+b $ 的直线。 - ```2 k b``` 代表小 C 询问你直线 $ y=kx+b $ 与多少条被绘制的直线有**恰好**一个公共点。 - ```3 k b``` 代表小 C 擦除所有与直线 $ y=kx+b $ 有**至少**一个公共点",
      "description_type": "Markdown"
    },
    "platform": "Luogu",
    "limit": {
      "time_limit": 500,
      "memory_limit": 524288
    },
    "difficulty": {
      "LuoguStyle": "P4"
    },
    "is_remote": true,
    "is_sync": true,
    "sync_url": null,
    "sign": "LGP9571"
  },
  "statements": [
    {
      "statement_type": "Markdown",
      "content": "小 C 喜欢在画板上画画。他进行了 $ n $ 次操作,每次操作有如下三种可能:\n\n- ```1 k b``` 代表小 C 绘制了一条解析式为 $ y=kx+b $ 的直线。\n- ```2 k b``` 代表小 C 询问你直线 $ y=kx+b $ 与多少条被绘制的直线有**恰好**一个公共点。\n- ```3 k b``` 代表小 C 擦除所有与直线 $ y=kx+b $ 有**至少**一个公共点...",
      "is_translate": false,
      "language": "English"
    }
  ]
}
Full JSON Raw Segments