当前位置：首页 > news >正文

打卡信奥刷题（3286）用C++实现信奥题 P8929 「TERRA-OI R1」别得意，小子

news 2026/5/21 19:12:11

P8929 「TERRA-OI R1」别得意，小子

题目背景

战至中途，蓝紫色天空瞬间变为黑压压一片，噬神者身上一些紫色外壳开始脱落，化为更小的蟒蛇，这些小家伙从出现开始便不要命的向你冲过来，刚清理掉这些小家伙，迷雾中忽然涌现出一张血盆大口，噬神者正向你冲击而来…

题目描述

现给定一个有nnn段的分段函数，每一段可能是一个一次函数或者一个二次函数，并有qqq次询问，每次询问x=kx=kx=k时yyy的取值或是y=ky=ky=k与函数有多少个交点。

输入格式

第一行两个用空格分隔的整数n,qn,qn,q，表示函数段数与询问次数。

从第222行到n+1n+1n+1行，先给出lil_ilirir_iri，表示这个分段函数对应的取值范围为(li,ri](l_i,r_i](li,ri]（保证l1=0l_1=0l1=0，∀i∈[1,n−1],ri=li+1\forall i\in [1,n-1],r_i=l_{i+1}∀i∈[1,n−1],ri=li+1）。然后读入有以下两种情况：

111kkkbbb，表示这个区间内是y=kx+by=kx+by=kx+b的一个一次函数（保证k≠0k\ne 0k=0）。
222aaabbbccc，表示这个区间内是y=ax2+bx+cy=ax^2+bx+cy=ax2+bx+c的二次函数（保证a≠0a\ne 0a=0）。

从第n+2n+2n+2行到第n+q+1n+q+1n+q+1行，每行两个用空格分隔的整数op,kop,kop,k：

若op=1op=1op=1，表示求出当x=kx=kx=k时yyy的值（保证k∈(0,rn]k\in (0,r_n]k∈(0,rn]）。
若op=2op=2op=2，表示求出直线y=ky=ky=k在(0,rn](0,r_n](0,rn]范围内与整个分段函数有几个交点。

输出格式

一共qqq行，每行一个整数表示对于每个询问的答案。

输入输出样例 #1

输入 #1

3 4 0 3 1 1 2 3 6 2 1 -2 1 6 10 1 1 0 1 4 2 5 2 114514 2 2

输出 #1

9 2 0 0

输入输出样例 #2

输入 #2

6 8 0 4 2 1 -4 0 4 6 1 2 -10 6 11 1 1 -19 11 19 2 -1 -30 559 19 29 1 1 -58 29 38 1 1 -68 1 11 2 4 2 -1 1 21 2 -5 2 2 1 34 2 1

输出 #2

-8 1 4 -37 1 2 -34 2

说明/提示

【样例解释 #1】

三段函数分别为y=x+2y=x+2y=x+2，y=x2−2x+1y=x^2-2x+1y=x2−2x+1，y=xy=xy=x。

对于当x=4x=4x=4时套入第二段函数可以得到结果为999。

而直线y=5y=5y=5只与第一段与第二段函数相交，并且各只有一个交点，所以结果为222。

显而易见，第三个询问对应的直线不与函数相交。

第四个询问虽然与第一段函数交于x=0x=0x=0的位置，但000不在该函数区间内，故舍去。

【数据范围】

本题采用捆绑测试。

Subtask	Score	n,q≤n,q\len,q≤	limit
111	101010	100100100	无
222	151515	10310^3103	rn≤5×103r_n\le 5\times 10^3rn≤5×103
333	202020	2×1052\times 10^52×105	不存在询问222
444	252525	2×1052\times 10^52×105	不存在二次函数
555	303030	2×1052\times 10^52×105	无

对于100%100\%100%的数据，1≤n,q≤2×1051\le n,q\le 2\times 10^51≤n,q≤2×105，0≤li,ri≤1090\le l_i,r_i\le10^90≤li,ri≤109，∀i∈[1,n],ri>li\forall i\in [1,n],r_i>l_i∀i∈[1,n],ri>li。

所有的函数系数均在646464位有符号整型变量存储范围内，并且运算结果与每个函数式中任何一项的最大值与最小值不会超过646464位有符号整型变量存储范围。所有询问参数均在323232位有符号整型变量范围内。

（即−4×1018≤k,a,b,c≤4×1018-4\times 10^{18}\le k,a,b,c\le 4\times 10^{18}−4×1018≤k,a,b,c≤4×1018，−109≤x≤109-10^9\le x\le 10^9−109≤x≤109）

【提示】

采用浮点数据时建议使用 long double，避免产生精度问题。

upd：添加一组 hack 数据，未通过会显示为“Unaccepted 100pts”。

C++实现

#include<cstdio>#include<cmath>#include<algorithm>template<typenameT>voidrd(T&x){x=0;intf=1;charc=getchar();while(c<'0'||c>'9'){if(c=='-')f=-1;c=getchar();}while(c>='0'&&c<='9'){x=x*10+c-48;c=getchar();}x*=f;}template<typenameT>Trd(){T x;rd(x);returnx;}template<typenameT,typename...T2>voidrd(T&x,T2&...y){rd(x),rd(y...);}typedeflongdoubledb;typedeflonglongll;llrd(){returnrd<ll>();}constll N=2e5+10;ll n,q;ll l[N],r[N],a[N],b[N],c[N];ll cnt;structD{ll y,d;operatorll(){returny;}}diff[N<<2];template<typenameT>Tcalc(ll i,T x){returna[i]*x*x+b[i]*x+c[i];}voidadd(ll i,db l,db r){db x=calc(i,l),y=calc(i,r);if(x<y)diff[++cnt]={floor(x)+1,1},diff[++cnt]={floor(y)+1,-1};elsediff[++cnt]={ceil(y),1},diff[++cnt]={ceil(x),-1};}intmain(){rd(n,q);for(ll i=1;i<=n;++i){rd(l[i],r[i]);if(rd()==2)rd(a[i]);elsea[i]=0;rd(b[i],c[i]);db z=-b[i]/(2.l*a[i]);if(l[i]<z&&z<=r[i])add(i,l[i],z),add(i,z,r[i]);elseadd(i,l[i],r[i]);}std::sort(diff+1,diff+cnt+1);ll j=0;diff[0].y=-0xffffffffffffffffll;for(ll i=1,sum=0;i<=cnt;++i){sum+=diff[i].d;if(diff[i].y!=diff[i-1].y)++j;diff[j]={diff[i].y,sum};}cnt=j;while(q--){ll o,k;rd(o,k);if(o==1)printf("%lld\n",calc(std::lower_bound(l+1,l+n+1,k)-l-1,k));elseprintf("%lld\n",(std::upper_bound(diff+1,diff+cnt+1,k)-1)->d);}}