C. Count Triangles(组合数学)

C. Count Triangles(组合数学)

传送门

思路：考虑所有的组成的可行解。

显然组成三角形, 因为，所以.

又因为.所以具有可行解的最小值为.

最大值即.

所以

接下来考虑每种对答案的贡献,首先考虑对于当前,的取值。

显然只能取.又因为.所以

可选的个数为.

接下来考虑可选的个数.

根据乘法原理可得当前的贡献为：
综上可以通过遍历得到答案。

时间复杂度:

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;
}