{"problem":{"name":"「TERRA-OI R1」别得意，小子","description":{"content":"现给定一个有 $n$ 段的分段函数，每一段可能是一个一次函数或者一个二次函数，并有 $q$ 次询问，每次询问 $x=k$ 时 $y$ 的取值或是 $y=k$ 与函数有多少个交点。 ","description_type":"Markdown"},"platform":"Luogu","limit":{"time_limit":2000,"memory_limit":131072},"difficulty":{"LuoguStyle":"P4"},"is_remote":true,"is_sync":true,"sync_url":null,"sign":"LGP8929"},"statements":[{"statement_type":"Markdown","content":"现给定一个有 $n$ 段的分段函数，每一段可能是一个一次函数或者一个二次函数，并有 $q$ 次询问，每次询问 $x=k$ 时 $y$ 的取值或是 $y=k$ 与函数有多少个交点。\n\n## Input\n\n第一行两个用空格分隔的整数 $n,q$，表示函数段数与询问次数。\n\n从第 $2$ 行到 $n+1$ 行，先给出 $l_i$ $r_i$，表示这个分段函数对应的取值范围为 $(l_i,r_i]$（保证 $l_1=0$，$\\forall i\\in [1,n-1],r_i=l_{i+1}$）。然后读入有以下两种情况：\n\n- $1$ $k$ $b$，表示这个区间内是 $y=kx+b$ 的一个一次函数（保证 $k\\ne 0$）。\n- $2$ $a$ $b$ $c$，表示这个区间内是 $y=ax^2+bx+c$ 的二次函数（保证 $a\\ne 0$）。\n\n从第 $n+2$ 行到第 $n+q+1$ 行，每行两个用空格分隔的整数 $op,k$：\n\n- 若 $op=1$ ，表示求出当 $x=k$ 时 $y$ 的值（保证 $k\\in (0,r_n]$）。\n- 若 $op=2$ ，表示求出直线 $y=k$ 在 $(0,r_n]$ 范围内与整个分段函数有几个交点。\n\n## Output\n\n一共 $q$ 行，每行一个整数表示对于每个询问的答案。\n\n[samples]\n\n## Background\n\n战至中途，蓝紫色天空瞬间变为黑压压一片，噬神者身上一些紫色外壳开始脱落，化为更小的蟒蛇，这些小家伙从出现开始便不要命的向你冲过来，刚清理掉这些小家伙，迷雾中忽然涌现出一张血盆大口，噬神者正向你冲击而来......\n\n## Note\n\n#### 【样例解释 #1】\n\n三段函数分别为 $y=x+2$，$y=x^2-2x+1$，$y=x$。\n\n对于当 $x=4$ 时套入第二段函数可以得到结果为 $9$。\n\n而直线 $y=5$ 只与第一段与第二段函数相交，并且各只有一个交点，所以结果为 $2$。\n\n显而易见，第三个询问对应的直线不与函数相交。\n\n第四个询问虽然与第一段函数交于 $x=0$ 的位置，但 $0$ 不在该函数区间内，故舍去。\n\n------------\n\n#### 【数据范围】\n\n**本题采用捆绑测试。**\n\n| Subtask | Score | $n,q\\le$ | limit |\n| :----------: | :----------: | :----------: | :----------: |\n| $1$ | $10$ | $100$ | 无 |\n| $2$ | $15$ | $10^3$ | $r_n\\le 5\\times 10^3$ |\n| $3$ | $20$ | $2\\times 10^5$ | 不存在询问 $2$ |\n| $4$ | $25$ | $2\\times 10^5$ | 不存在二次函数 |\n| $5$ | $30$ | $2\\times 10^5$ | 无 |\n\n对于 $100\\%$ 的数据，$1\\le n,q\\le 2\\times 10^5$，$0\\le l_i,r_i\\le10^9$，$\\forall i\\in [1,n],r_i>l_i$ 。\n\n所有的函数系数均在 **$64$ 位有符号整型变量**存储范围内，并且运算结果与每个函数式中任何一项的最大值与最小值不会超过 **$64$ 位有符号整型变量**存储范围。所有询问参数均在 **$32$ 位有符号整型变量**范围内。\n\n（即 $-4\\times 10^{18}\\le k,a,b,c\\le 4\\times 10^{18}$，$-10^9\\le x\\le 10^9$）\n\n------------\n#### 【提示】\n\n采用浮点数据时建议使用 long double，避免产生精度问题。\n\nupd：添加一组 hack 数据，未通过会显示为“Unaccepted 100pts”。","is_translate":false,"language":"English"}],"meta":{"iden":"LGP8929","tags":["数学","二分","O2优化","差分"],"sample_group":[["3 4\n0 3 1 1 2\n3 6 2 1 -2 1\n6 10 1 1 0\n1 4\n2 5\n2 114514\n2 2","9\n2\n0\n0"],["6 8\n0 4 2 1 -4 0 \n4 6 1 2 -10 \n6 11 1 1 -19 \n11 19 2 -1 -30 559 \n19 29 1 1 -58 \n29 38 1 1 -68 \n1 11\n2 4\n2 -1\n1 21\n2 -5\n2 2\n1 34\n2 1\n","-8\n1\n4\n-37\n1\n2\n-34\n2\n"]],"created_at":"2026-03-03 11:09:25"}}