Count Triangles

Created by LXC on Thu May 18 00:00:39 2023

https://codeforces.com/problemset/problem/1355/C

ranting: 1800

tag: binary search, implementation, math, two pointers

题意

给出由小到的大的四个数A,B,C,D。其中$A\le B \le C \le D \le 5e^5$

需要选出三个数x,y,z。满足$A\le x\le B \le x\le C \le z \le D$

使得xyz形成三角形。

问有多少种选法。

题解

由于$x<y<z$，我们要使得xyz能组成三角形，必须满足$x+y>z$

可以考虑每个$x+y$能组成的数出现的个数。不妨设$k = x+y$出现的次数t次。
那么分三种情况：

• $t<C$，则没有z可以满足这个k>z
• $C\le t\le D$，则可以选择$k-C$个小于k的z，那么贡献答案$t*(k-C)$
• $t > D$，则可以选择$D-C+1$个小于k的z，那么贡献答案$t*(D-C+1)$

我们可以对每一个数$x$，让其在区间$[x+B, x+C]$内的数都增加1，这个可以用差分数组在$O(B-A)$内实现，差分数组再求一次前缀和则可以得到每个$x+y$出现的个数。

代码

#include <bits/stdc++.h>
#define SINGLE_INPUT
#define ll long long
#define ull unsigned long long
#define N 500005
#define MOD 998244353
using namespace std;

ll dif[2 * N];

void sol() {
    ll a, b, c, d;
    cin >> a >> b >> c >> d;
    for (ll i = a; i <= b; i++) {
        dif[i + b]++;
        dif[i + c + 1]--;
    }
    ll ans = 0;
    for (ll i = a + b; i <= b + c + 1; i++) {
        dif[i] += dif[i - 1];
        ans += min(max(i - c, 0LL), d - c + 1) * dif[i];
    }
    cout << ans << "\n";
}

int main() {
    cout << setprecision(15) << fixed;
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
#ifndef SINGLE_INPUT
    int t;
    cin >> t;
    while (t--) {
        sol();
    }
#else
    sol();
#endif
    return 0;
}