傳送門
思路：我們需要滿足 x + y > z , x + z > y , y + z > x .因為 A <= X <=B <= Y <= C <= Z <= D，所以 X + Z > Y和 Y + Z > X明顯一定滿足，所以我們只需要確定X + Y > Z的個數了.X∈[A,B],Y∈[B,C]，則我們發現若X = A,則 X + Y = [A + B, A + C], X = A + 1, X + Y = [A + B + 1, A + C + 1].可以看出這就是區間+1操作，這樣我們只需要列舉X的取值范圍得到一個[L,R]，讓該區間值+1，最后我們就可以得到X+Y=[A+B,B+C]中任意一個數值的方案數，然后得到一個前綴和陣列P[i]，表示X+Y=[1,i]的總方案數.這樣我們只需要列舉Z∈[C,D]，對于每個Z的答案就是P[B+C] - P[Z]，當然如果當前的Z>=B+C需要考慮，而上面的區間+1操作可以用差分來解決，或者線段樹也可以，復雜度就是O（N），
1 #include <iostream> 2 #include <cstdio> 3 #include <algorithm> 4 #include <cstring> 5 #include <cmath> 6 #include <queue> 7 #include <vector> 8 #include <cstring> 9 #include <functional> 10 #include <map> 11 #define LL long long 12 #define lson(rt) (rt << 1) 13 #define rson(rt) (rt << 1 | 1) 14 using namespace std; 15 16 const int N = 1e6 + 10; 17 long long x[N], y[N]; 18 19 void solve () 20 { 21 int a, b, c, d; 22 scanf("%d%d%d%d", &a, &b, &c, &d); 23 for(int i = a; i <= b; ++i) { 24 x[i + b] += 1; 25 x[i + c + 1] -= 1; 26 } 27 int n = b + c; 28 for(int i = 1; i <= n; ++i) x[i] += x[i - 1]; 29 for(int i = 1; i <= n; ++i) y[i] += y[i - 1] + x[i];/* 30 for(int i = 1; i <= s; ++i) cout << x[i] << " "; 31 cout << endl; 32 for(int i = 1; i <= s; ++i) cout << y[i] << " "; 33 cout << endl;*/ 34 long long tot = 0; 35 for(int i = c; i <= d; ++i) { 36 if(i >= b + c) break; 37 tot += (LL)y[b + c] - y[i]; 38 } 39 //cout << "tot = " << tot << endl; 40 printf("%lld\n", tot); 41 } 42 43 int main () 44 { 45 solve(); 46 47 return 0; 48 }
轉載請註明出處，本文鏈接：https://www.uj5u.com/qita/249375.html
標籤：其他
上一篇：2021寒假每日一題《貨艙選址》