C.Count Triangles(組み合わせ数学)

C.Count Triangles(組み合わせ数学)
トランスファゲート
構想:すべてのx+y x+y x+y x+y組成の実行可能な解を考慮する.
明らかにx,y,z x,y,z x,y,zは三角形→x+y>zrightarrow x+y>z→x+y>zを構成し,z mi n=c z_{min}=c zmin=cなので(x+y)m i n>c(x+y){min}>c (x+y)min​>c.
またxm i n=a,y m i n=b x_{min}=a,y_{min}=b xmin=a,ymin=bであるため、x+y x+y x+yが実行可能な解を有する最小値は、m a x(c+1,a+b)max(c+1,a+b)max(c+1,a+b)max(c+1,a+b)である.
最大値、すなわちb+cb+cb+c.
したがってx+y∈[m a x(c+1,a+b),b+c]x+yin[max(c+1,a+b),b+c]x+y∈[max(c+1,a+b),b+c]
次に、各x+y x+y x+yの答えへの寄与を考慮し、まず、現在のi=x+y i=x+y i=x+yに対して、z z zの値を考慮する.
明らかにz zはc,c+1...i−2,i−1 c,c+1dots i−2,i−1 c,c+1...i−2,i−1しか取れない.またc m a x=d c_{max}=d cmax=d.だから
z z zのオプション個数は、cntz=mi n(d,i−1)−c+1=mi n(d+1,i)−c cnt_z=min(d,i-1)-c+1=min(d+1,i)-c cntz​=min(d,i−1)−c+1=min(d+1,i)−c.
次に、x+y x+y x+yの選択可能な個数を考える.
y:[b,...,c]x:[a,...,b]対y,xの対応値は[i−c,...,i−b]である.i≧a+b,i≦b+c⇒i−b≧a,i−c≦cのためyの値の範囲は,[m a x[i−c,a],m i n[i−b,b],すなわちx+yの選択可能な個数は,c n t x+y=m i n(i−b,b)−m a x(i−c,a)+1である.y:[b,dots,c]\x:[a,dots,b]\y毎にxの対応値は[i-c,dots,i-b].\igeq a+b,ileq b+cRightarrow i-bgeq a,i-cleq c\だからyの値の範囲は:[max[i-c,a],min[i-b,b]\つまりx+yのオプションの個数は:cnt_{x+y}=min(i-b,b)-max(i-c,a)+1個.y:[b,...,c]x:[a,...,b]対y,xの対応値は[i−c,...,i−b]である.i≧a+b,i≦b+c⇒i−b≧a,i−c≦cのためyの値の範囲は,[max[i−c,a],min[i−b,b]]すなわちx+yオプションの個数は,cntx+y=min(i−b,b)−max(i−c,a)+1個である.乗算原理に基づいて、現在のx+yx+yx+yの寄与は、cn t x+yである.× c n t z cnt_{x+y}\times cnt_z cntx+y​×cntzは,x+y x+y x+y x+yを遍歴することによって答えを得ることができる.
時間複雑度:O(m a x(b,c−a＋1))O(max(b,c−a＋1)))O(max(b,c−a＋1)))
ACコード:

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