{"problem":{"name":"[Ynoi Easy Round 2021] TEST_136","description":{"content":"给定 $n$ 个点 $(x_i,y_i,c_i)$，$i=1,2,\\dots,n$，共有 $m$ 次查询操作，每次查询给定 $A,B,C$，问满足 $Ax_i+By_i+C<0$，$Ax_j+By_j+C<0$，$c_i=c_j$ 的二元组 $(i,j)$ 的个数。","description_type":"Markdown"},"platform":"Luogu","limit":{"time_limit":8000,"memory_limit":524288},"difficulty":{"LuoguStyle":"P7"},"is_remote":true,"is_sync":true,"sync_url":null,"sign":"LGP8513"},"statements":[{"statement_type":"Markdown","content":"给定 $n$ 个点 $(x_i,y_i,c_i)$，$i=1,2,\\dots,n$，共有 $m$ 次查询操作，每次查询给定 $A,B,C$，问满足 $Ax_i+By_i+C<0$，$Ax_j+By_j+C<0$，$c_i=c_j$ 的二元组 $(i,j)$ 的个数。\n\n## Input\n\n第一行两个整数 $n\\ m$；\n\n接下来 $n$ 行，每行三个整数 $x_i\\ y_i\\ c_i$，$i=1,2,\\dots,n$；\n\n接下来 $m$ 行，每行三个整数 $A\\ B\\ C$。\n\n## Output\n\n共 $m$ 行，每行一个整数，表示答案。\n\n[samples]\n\n## Note\n\nIdea：nzhtl1477，Solution：ccz181078，Code：ccz181078，Data：ccz181078\n\n样例解释：\n\n第一个查询对应 $(2,2)(3,3)$；\n\n第二个查询对应 $(1,1)(2,2)(2,4)(3,3)(3,5)(4,2)(4,4)(5,3)(5,5)$。\n\n数据范围：\n\n对 $5\\%$ 的数据，$n,m\\le 10^3$；\n\n对另外 $10\\%$ 的数据，$c_i\\le 2$；\n\n对另外 $15\\%$ 的数据，$c_i\\le 100$；\n\n对另外 $15\\%$​ 的数据，$\\max(|x_i|,|y_i|)=10^6$​；\n\n对另外 $15\\%$ 的数据，$|A|=|B|=1$；\n\n对另外 $10\\%$ 的数据，$n\\le 20000,\\;m\\le 200000$；\n\n对于其余数据，无特殊约束。\n\n每部分数据构成子任务，无依赖关系。\n\n所有数据满足：\n\n$1\\le n\\le 50000$；\n\n$1\\le m\\le 500000$；\n\n$A^2+B^2>0$；\n\n$-10^9\\le x_i,y_i,A,B,C\\le 10^9$；\n\n$1\\le c_i\\le n$；\n\n所有数值为整数；\n\n当 $i\\ne j$ 时，$x_i\\ne x_j$ 或 $y_i\\ne y_j$。\n\n对于除了子任务 4 以外的数据，满足 $n$ 个点的 $x,y$ 坐标分别在某个预设的区间内均匀随机选取，并保证没有重复的点，且对于第 $i$ 个点，$c_i$ 和 $x_i,y_i$ 是分别独立地随机选取的，但 $c_i$ 的分布没有特殊限制。","is_translate":false,"language":"English"}],"meta":{"iden":"LGP8513","tags":["2021","O2优化","Ynoi"],"sample_group":[["5 2\n2 -1 1\n0 -3 5\n1 -3 2\n1 3 5\n3 2 2\n1 2 4\n1 -2 -9\n","2\n9\n"]],"created_at":"2026-03-03 11:09:25"}}