P8929 「TERRA-OI R1」别得意小子题目背景战至中途蓝紫色天空瞬间变为黑压压一片噬神者身上一些紫色外壳开始脱落化为更小的蟒蛇这些小家伙从出现开始便不要命的向你冲过来刚清理掉这些小家伙迷雾中忽然涌现出一张血盆大口噬神者正向你冲击而来…题目描述现给定一个有nnn段的分段函数每一段可能是一个一次函数或者一个二次函数并有qqq次询问每次询问xkxkxk时yyy的取值或是ykykyk与函数有多少个交点。输入格式第一行两个用空格分隔的整数n,qn,qn,q表示函数段数与询问次数。从第222行到n1n1n1行先给出lil_ili​rir_iri​表示这个分段函数对应的取值范围为(li,ri](l_i,r_i](li​,ri​]保证l10l_10l1​0∀i∈[1,n−1],rili1\forall i\in [1,n-1],r_il_{i1}∀i∈[1,n−1],ri​li1​。然后读入有以下两种情况111kkkbbb表示这个区间内是ykxbykxbykxb的一个一次函数保证k≠0k\ne 0k0。222aaabbbccc表示这个区间内是yax2bxcyax^2bxcyax2bxc的二次函数保证a≠0a\ne 0a0。从第n2n2n2行到第nq1nq1nq1行每行两个用空格分隔的整数op,kop,kop,k若op1op1op1表示求出当xkxkxk时yyy的值保证k∈(0,rn]k\in (0,r_n]k∈(0,rn​]。若op2op2op2表示求出直线ykykyk在(0,rn](0,r_n](0,rn​]范围内与整个分段函数有几个交点。输出格式一共qqq行每行一个整数表示对于每个询问的答案。输入输出样例 #1输入 #13 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输出 #19 2 0 0输入输出样例 #2输入 #26 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】三段函数分别为yx2yx2yx2yx2−2x1yx^2-2x1yx2−2x1yxyxyx。对于当x4x4x4时套入第二段函数可以得到结果为999。而直线y5y5y5只与第一段与第二段函数相交并且各只有一个交点所以结果为222。显而易见第三个询问对应的直线不与函数相交。第四个询问虽然与第一段函数交于x0x0x0的位置但000不在该函数区间内故舍去。【数据范围】本题采用捆绑测试。SubtaskScoren,q≤n,q\len,q≤limit111101010100100100无22215151510310^3103rn≤5×103r_n\le 5\times 10^3rn​≤5×1033332020202×1052\times 10^52×105不存在询问2224442525252×1052\times 10^52×105不存在二次函数5553030302×1052\times 10^52×105无对于100%100\%100%的数据1≤n,q≤2×1051\le n,q\le 2\times 10^51≤n,q≤2×1050≤li,ri≤1090\le l_i,r_i\le10^90≤li​,ri​≤109∀i∈[1,n],rili\forall i\in [1,n],r_il_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实现#includecstdio#includecmath#includealgorithmtemplatetypenameTvoidrd(Tx){x0;intf1;charcgetchar();while(c0||c9){if(c-)f-1;cgetchar();}while(c0c9){xx*10c-48;cgetchar();}x*f;}templatetypenameTTrd(){T x;rd(x);returnx;}templatetypenameT,typename...T2voidrd(Tx,T2...y){rd(x),rd(y...);}typedeflongdoubledb;typedeflonglongll;llrd(){returnrdll();}constll N2e510;ll n,q;ll l[N],r[N],a[N],b[N],c[N];ll cnt;structD{ll y,d;operatorll(){returny;}}diff[N2];templatetypenameTTcalc(ll i,T x){returna[i]*x*xb[i]*xc[i];}voidadd(ll i,db l,db r){db xcalc(i,l),ycalc(i,r);if(xy)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 i1;in;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]zzr[i])add(i,l[i],z),add(i,z,r[i]);elseadd(i,l[i],r[i]);}std::sort(diff1,diffcnt1);ll j0;diff[0].y-0xffffffffffffffffll;for(ll i1,sum0;icnt;i){sumdiff[i].d;if(diff[i].y!diff[i-1].y)j;diff[j]{diff[i].y,sum};}cntj;while(q--){ll o,k;rd(o,k);if(o1)printf(%lld\n,calc(std::lower_bound(l1,ln1,k)-l-1,k));elseprintf(%lld\n,(std::upper_bound(diff1,diffcnt1,k)-1)-d);}}后续接下来我会不断用C来实现信奥比赛中的算法题、GESP考级编程题实现、白名单赛事考题实现记录日常的编程生活、比赛心得感兴趣的请关注我后续将继续分享相关内容