CFR-643C Count Triangles 题解

题目大意

给你四个数字$A,B,C,D$，$A≤x≤B≤y≤C≤z≤D$，其中$x,y,z$为三角形的三边，问$xyz$能够严格构成的三角形有多少个。（三顶点不共线）

解题思路

这次比赛就离谱，C题1800，D题1400。。

因为数据范围为$5·10^5$，所以复杂度尽量要控制在$O(n)$左右。

我们可以枚举x，$x∈[A,B]，y∈[B,C]$，将x作为常数，那么z的最大值范围为$[B-x-1,C-x-1]$。

分情况讨论

当$B-x-1≥D$时，显然y取任何值，z都是满足要求的。

$ans = (C-B+1)*(zr-zl+1)$

当$B-x-1<D$时，我们可以分为两部分来计算

1、在$[C,D]$中的部分，令$l = max(zl,C),r = min(zr,D)$。

在其中的部分，构成了一个以$l-C+1$为首项，$r-C+1$为末项的一个公差为1的等差数列，所以我们可以用等差数列求和公式来求和。

$ans = (r-l+1)*(l-C+1+r-C+1)/2$

2、在$[D+1,zr]$的部分

$ans = (zr-D)*(D-C+1)$

（哇。。这种数学题对我来说是真的苦手，数论咋办啊。。

区间问题一般都能杀我。

完整代码

#include <iostream>
#include <queue>
#include <cstring>
#include <cmath>
#include <string>
#include <vector>
#include <algorithm>
using namespace std;
typedef long long ll;
const int N = 1e6 + 5;

int main() {
	ios::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);
	ll A, B, C, D;
	cin >> A >> B >> C >> D;
	ll ans = 0;
	for (int x = A; x <= B; x++) {
		ll zl = x + B - 1, zr = x + C - 1;
		if (zl >= D)	ans += (D - C + 1) * (C - B + 1);
		else {
			ll l = max(zl, C), r = min(zr, D);
			ans += (r - l + 1) * (l - C + 1 + r - C + 1) / 2;
			if (zr > D)	ans += (zr - D) * (D - C + 1);
		}
	}
	cout << ans << endl;
}