C. Count Triangles(组合数学)

传送门

思路：考虑所有的 $x+y$ 组成的可行解。

显然 $x,y,z$ 组成三角形 $\rightarrow x+y>z$ , 因为 $z_{min}=c$ ，所以 $(x+y)_{min}>c$ .

又因为 $x_{min}=a,y_{min}=b$ .所以 $x+y$ 具有可行解的最小值为 $min(c+1,a+b)$ .

最大值即 $b+c$ .

所以 $x+y\in[min(c+1,a+b),b+c]$

接下来考虑每种 $x+y$ 对答案的贡献,首先考虑对于当前 $i=x+y$ , $z$ 的取值。

显然 $z$ 只能取 $c,c+1\dots i-2,i-1$ .又因为 $c_{max}=d$ .所以

$z$ 可选的个数为 $cnt_z=min(d,i-1)-c+1=min(d+1,i)-c$ .

接下来考虑 $x+y$ 可选的个数.

$y:[b,\dots,c]\\x:[a,\dots,b]\\对每个y，x的对应值为[i-c,\dots,i-b].\\因为i\geq a+b,i\leq b+c\Rightarrow i-b\geq a,i-c\leq c\\所以y的取值的范围为：[max[i-c,a],min[i-b,b]]\\即x+y可选的个数为:cnt_{x+y}=min(i-b,b)-max(i-c,a)+1个。$

根据乘法原理可得当前 $x+y$ 的贡献为： $cnt_{x+y}\times cnt_z$
综上可以通过遍历 $x+y$ 得到答案。

时间复杂度: $O(max(b,c-a+1))$

AC代码：

#include<iostream>
#include<algorithm>
typedef long long ll; 
using namespace std;
signed main(){
    ll a,b,c,d;
    cin>>a>>b>>c>>d;
    ll ans=0;
    for(ll i=max(c+1,a+b);i<=b+c;++i)
        ans+=(min(d+1,i)-c)*(min(i-b,b)-max(i-c,a)+1);
    cout<<ans<<endl;
}