悲报：复活赛没打赢。

· · 题解

寄喽，CSP-S 2023 只会这一道，场外写的，还惨遭卡常，真进场了大概分数还要折半。

思路很粗暴，当 c\neq 0 时每天树的增长量要么是常数 1 要么是等差数列，c\lt 0 考虑直接算出分段函数分界点，之后左边部分处理和 c\gt 0 一样等差数列求和公式，右边部分和 c = 0 一样直接 r-l+1 。

因此，对于树 (a_i,b_i,c_i) 在时间段 [x,y] 的总生长高度计算有如下实现：

using i128=__int128;
i128 calc(i128 x,i128 b,i128 c,i128 y=1e9)
{
    if(c==0) return (y-x+1)*b;
    else if(c<0)
    {
        i128 z=(-b)/c;
        if(z*c+b==0) --z;
        if(y<=z) return (y-x+1)*(b+c*x+b+c*y)/2;
        if(x>z) return y-x+1;
        return (z-x+1)*(b+c*x+b+c*z)/2+y-z;
    }
    else
    {
        return (y-x+1)*(b+c*x+b+c*y)/2;
    }
}

问题在于，种树的决策过于复杂，直接推过去貌似不太可做，注意题目的提示 “所有答案均不超过 10^9”，并且显然时间越长越有可能种完所有树，考虑二分答案转判定性问题。

那么，设当前二分值为 x，此时问题被极大简化：只需要在时刻 x 到来时让所有树都长好即可，直接卡这个最后时限，我们可以算出每棵树最晚何时种下才能使其高度最后合法，显然 \operatorname{calc} 是关于天数单调的，这一步可以直接二分。

那么，考虑一个贪心：每次去撅时限最小的点。正确性证明的话，直接考虑如果时限最小的点都得不到满足那么其他点一定无法满足，至于有多个点先撅哪个，答案是无所谓，考虑对撅这个点集的代价求和，这个和是一定的（因为一定是撅了若干条根到某个结点的路径上全部结点，这些路径的交集一定），只要这个和超了时限那无论内部怎么调整顺序都一定不合法，反之亦然。同理，也可以从此方面证明全局贪心策略的正确性。

就这些，结束了。具体实现的话，考虑最粗暴的一套：直接拿个堆按照最晚被撅的时刻维护所有结点，再开个桶标记被撅的点，最晚被撅时刻刚才说过了直接二分求，撅点的话就暴力往上跳父亲同时一路标记直到跳到被标记的点或者跳出整棵树，同时一边跳一边计时刻，一旦超了当前点时限或者当前二分的限制时限直接返回假。不用特别处理根，第一个肯定撅她。

时间复杂度 \Theta(n\log^2 V)（因为求最晚种树时间用了二分），其中 V=10^9，由于滥用 __int128 与瞎开数据结构 （比如拿 std::set 当堆使），笔者拿到了 40 分的高分。更可喜可贺的是，由于脑瘫笔者滥用某数据类型导致该写法卡常拉满也只能在数据更强的云斗搞个令人眼前一黑的 75 分。

因此，考虑优化时间复杂度。

首先，求每个点的被撅最晚时刻不需要使用二分，考虑本质是等差数列求和加上一个斜率为 1 的一次函数，拼接后者只有可能是在 c\lt 0 的情况下，因此是否需要拼接后者直接求出分段点，之后对分段点到最种时刻的增长量求和(实际就是前面说的一次函数)，看这一部分能否满足要求即可，若不满足要求，把要求的长度减去这一部分，继续算等差数列部分即可。

考虑等差数列求和公式本质是二次函数，问题转化为求一元二次不等式的最大正整数解问题，按照前面写的 \operatorname{calc} 函数写方程求解即可，注意要取下整，至于这样可能不好判无解，直接算出第一天就撅她能不能合法即可。

实现出来可能长这样：

using i128=__int128;
using lld=long double;
int calc2(i128 x,i128 a,i128 b,i128 c)
{
    if(c==0) return x+1-ceil((long double)((long double)a/(long double)b));
    else if(c<0)
    {
        i128 z=(-b)/c;
        if(z*c+b==0) --z;
        if(z<x&&calc(z+1,b,c,x)>=(i128)a)
        {
            return x-a+1;
        }
        else if(z<x)
        {
            a-=calc(z+1,b,c,x);
            x=z;
            i128 C=c*x*x+(2*b+c)*x+2*(b-a),A=-c,B=c-b*2;
            lld dlt=sqrt((lld)(B*B-4*A*C));
            lld a1=(dlt-B)/(2*A),a2=(-B-dlt)/(2*A);
            if(a1>0.5&&a2>0.5) return floor(min(a1,a2));
            else if(a1>0.5) return floor(a1);
            else return floor(a2);
        }
        else
        {
            i128 C=c*x*x+(2*b+c)*x+2*(b-a),A=-c,B=c-b*2;
            lld dlt=sqrt((lld)(B*B-4*A*C));
            lld a1=(dlt-B)/(2*A),a2=(-B-dlt)/(2*A);
            if(a1>0.5&&a2>0.5) return floor(min(a1,a2));
            else if(a1>0.5) return floor(a1);
            else return floor(a2);
        }
    }
    else
    {
        i128 C=c*x*x+(2*b+c)*x+2*(b-a),A=-c,B=c-b*2;
        lld dlt=sqrt((lld)(B*B-4*A*C));
        lld a1=(dlt-B)/(2*A),a2=(-B-dlt)/(2*A);
        if(a1>0.5&&a2>0.5) return floor(min(a1,a2));
        else if(a1>0.5) return floor(a1);
        else return floor(a2);
    }
}

如此可将时间复杂度降低至 \Theta(n \log n\log V) 级别，已经可以过了，但是能不能更优秀呢？

此时内层还有一个瓶颈是排序。

我会基数排序！

直接每个数每五位作为一个关键字，内层用计排，非常好线性排序算法，使我的计算机旋转，奖励一佰昏！

什么？你没被宇宙射线击中过，不会基数排序？

写不出优秀高贵的 \Theta (n \log V) 算法，急急急？

我知道你很急，但你先别急，注意一个性质：一棵树被撅完的总时间是固定的 n ，因为显然一次撅一个点。

那么，最晚被撅时刻大于 n 的点就不用处理了，显然她们不可能等不及。

现在值域降低到 \Theta(n) 级别了，别告诉我你不会桶排，不然急急急的就是我了。

这种写法常数也更小，实际实现也更容易，是更为优秀的 \Theta(n\log V) 解法，她并不高贵，只要你别急急急，急火攻心忘了撅掉所有点的总时刻开销是固定的 n。

最后，祝天下所有人不被卡常，也祝我早日适应 XCPC，这玩意儿要是放 XCPC 我搞不好就因为卡常饮恨西北了。