codeforces C. Count Triangles

题目

题意：

给你$A,B,C,D$A,B,C,D，并且有$A\leq x\leq B\leq y\leq C\leq z \leq D$A≤x≤B≤y≤C≤z≤D，问有多少个$x+y>z$x+y>z。

思路：

对于$x+y>z$x+y>z，如果遍历的话$x,y$x,y的话，肯定就会超时了，因为对于每一个$x$x，如果加上$y$y全部$y$y的话，那么对应的区间就是$[x+B,x+C]$[x+B,x+C]，我们就可以用一个前缀和维护求出最后的$x+y$x+y的所有区间，然后我们要知道有多少$x+y>z$x+y>z那么我们遍历一下$z$z，然后求出再算一个前缀和代表着在$i$i前有多少个$x+y\leq i$x+y≤i，那么$i$i用$z$z代替，那么我们求出$x+y>z$x+y>z那么是不是就是$a_{maxn-1}-a_z$amaxn−1​−az​。

#include <iostream>
#include <cstring>
#include <cstdio>
#include <algorithm>
#include <queue>
#include <vector>
#include <string>
#include <cmath>
#include <set>
#include <map>
#include <deque>
#include <stack>
#include <cctype>
using namespace std;
typedef long long ll;
typedef vector<int> veci;
typedef vector<ll> vecl;
typedef pair<int, int> pii;
template <class T>
inline void read(T &ret) {
    char c;
    int sgn;
    if (c = getchar(), c == EOF) return ;
    while (c != '-' && (c < '0' || c > '9')) c = getchar();
    sgn = (c == '-') ? -1:1;
    ret = (c == '-') ? 0:(c - '0');
    while (c = getchar(), c >= '0' && c <= '9') ret = ret * 10 + (c - '0');
    ret *= sgn;
    return ;
}
inline void out(ll x) {
    if (x > 9) out(x / 10);
    putchar(x % 10 + '0');
}
const int maxn = 1e6 + 10;
ll cnt[maxn] = {0};
int main() {
    int A, B, C, D;
    read(A), read(B), read(C), read(D);
    for (int i = A; i <= B; i++) {
        cnt[i + B]++;
        cnt[i + C + 1]--;
    }
    for (int i = 0; i < maxn; i++) cnt[i] += cnt[i - 1];
    for (int i = 0; i < maxn; i++) cnt[i] += cnt[i - 1];
    ll ans = 0;
    for (int i = C; i <= D; i++) {
        ans += 1ll * (cnt[maxn - 1] - cnt[i]);
    }
    out(ans);
    return 0;
}