题解：P10071 [CCO2023] Triangle Collection

简化题意

意思就是给你一堆棍子，问你最多可以组成多少等腰三角形。然后带修改。

正文

既然有这个围成三角形的限制条件：两边之和大于第三边。

放到等腰三角形中就是第三边长度 \le 2\times l -1。

我们把一个三角形分成 腰 和 底 分开来看，那一个腰要配上一个底，并且这个底的范围在 [1,2\times l-1] 的范围内，这个东西一一配对就想到了差分使得前缀和都不小于 0（别的题解有写括号序列的，确实是这样，但是我没有往这方面想）。

具体操作就是，对于每一个长度 l，我们先贪心得多取腰的对数，也就是 cnt_l/2，在 l\times 2-1 的位置减去这个值，然后再考虑剩下的可以作为底的，也就是在 l 的位置加上 cnt_l \bmod 2。

如果所有的前缀和都大于等于 0，那么答案就是我们贪心的结果。如果有小于 0 的怎么办呢。

首先我们一定是让某些腰变成底，计算变化后的结果，自然就是在 l\times 2-1 的位置加上 1，也就是撤销这一对边，并且在 l 的位置加上 2，因为一对腰是两条边，这样一共会导致前缀和加 3。

注意到我们只需要找到最小的那个不满足条件的值，记为 pos，可以证明，一定可以在这个位置前面找到足够的数量，使得前缀和每次都加 3（因为本身就是从前面减的贡献，既然这个位置小于 0 了，就证明前面多取了底，假设多取的位置为 l，那么 2\times l-1 一定小于等于当前 pos 的位置）。

至于 pos 的位置之后的位置，因为 pos 是最小的，既然最小的都满足条件了，这是前缀和，后面的肯定也满足条件。

那么 pos 的位置之前的位置也小于 0 怎么办，跟上面 pos 的证明是一样的。

注意大小开两倍，由于 2\times l-2 的原因。

代码

signed main() {
    read(n,q);
    xb = 2*n;
    for(int i = 1; i<=n; i++) {
        read(c[i]);
        int num1 = c[i]/2;  //作为腰
        all+=num1;
        a[i*2-1]-=num1;
        num1 = c[i]%2;
        a[i]+=num1;
    }
    for(int i = 1; i<=xb; i++) {
        a[i] = a[i-1]+a[i];
    }

    build(1,1,xb);

    while(q--) {
        int x,d;
        read(x,d);
        int num1 = c[x]/2;
        all-=num1;
        update(1,2*x-1,xb,num1);
        num1 = c[x]%2;
        update(1,x,xb,-num1);
        c[x] +=d;
        num1 = c[x]/2;
        all+=num1;
        update(1,2*x-1,xb,-num1);
        num1 = c[x]%2;
        update(1,x,xb,num1);
        int minn = tr[1].minn;
        int ans = all;
        if(minn<=0)
            ans = all+minn/3-(minn%3!=0);
        write(ans);
        LF;

    }
    return 0;
}