锐客网

  1. 首页 > it技术 > >

codeforce|Codeforces Round #643 (Div. 2) C. Count Triangles-- 差分、前缀和

数学思维codeforce

题意 给你A , B , C , D A , B , C , D A,B,C,D
问有多少种方法构造出三角形 ( X , Y , Z ) (X , Y , Z) (X,Y,Z)使得1 ≤ A ≤ X ≤ B ≤ Y ≤ C ≤ Z ≤ D < = 1 0 5 1≤A ≤ X ≤ B ≤ Y ≤ C ≤ Z ≤ D <= 10^5 1≤A≤X≤B≤Y≤C≤Z≤D<=105
思路 【codeforce|Codeforces Round #643 (Div. 2) C. Count Triangles-- 差分、前缀和】组成三角形的条件是2边之和大于第三边，这里因为 X ≤ Y ≤ Z X≤Y≤Z X≤Y≤Z
所以只需要 x + y > z x+y>z x+y>z，所以我们只要知道了 x + y x+y x+y的值之后，可以求出 z z z的可行范围，但分别枚举 x ， y x，y x，y肯定会超时，我们换个思路，直接枚举 x + y x+y x+y或者说能得到 x + y = p x+y=p x+y=p的 x , y x,y x,y有多少对，显然当 x = 1 时 ， B ≤ y ≤ C x=1时，B ≤ y ≤ C x=1时，B≤y≤C,所以组成的 x + y x+y x+y的值在 [ 1 + B , 1 + C ] [1+B ,1+C] [1+B,1+C]区间，当 x = 2 时 ， B ≤ y ≤ C x=2时，B ≤ y ≤ C x=2时，B≤y≤C,所以组成的 x + y x+y x+y的值在 [ 2 + B , 2 + C ] [2+B ,2+C] [2+B,2+C]区间,显然这些区间重叠到一起之后，对于某个点p的取值就是构成 x + y = p 的 x , y x+y=p的x,y x+y=p的x,y组合个数，然后这部分区间可以通过差分、前缀和求得 S [ ] S[] S[]，此时得到的 S [ i ] S[i] S[i]表示构成 x + y = i x+y=i x+y=i的组合对数。然后我们枚举 z z z，对应当前 z ， x + y > z z，x+y>z z，x+y>z,所以答案就是 S [ z + 1 ] + S [ z + 2 ] + . . . . . + S [ m a x n ? 1 ] S[z+1] + S[z+2] + ..... + S[maxn-1] S[z+1]+S[z+2]+.....+S[maxn?1] 然后这部分的区间值我们同样可以用前缀和来维护，最后 S [ m a x n ? 1 ] ? S [ z ] S[maxn-1] - S[z] S[maxn?1]?S[z]就是答案。

#pragma GCC optimize(2) #include using namespace std; const int man = 1e6+10; #define IOS ios::sync_with_stdio(0) typedef long long ll; const ll mod = 1e9+7; ll sum[man]; int main() { #ifndef ONLINE_JUDGE //freopen("in.txt", "r", stdin); //freopen("out.txt","w",stdout); #endif int a,b,c,d; cin >>a >> b >>c >> d; for(int i = a; i <= b; i++)sum[i+b]++,sum[i+c+1]--; //区间修改 for(int i = 1; i < man; i++)sum[i]+=sum[i-1]; //所有区间加1，重叠地方累加 for(int i = 1; i < man; i++)sum[i]+=sum[i-1]; //对x+y的数量求一个前缀和，O(1)得到答案 ll ans = 0; for(int i = c; i <= d; i++){ ans += sum[man-1] - sum[i]; } cout << ans << endl; return 0; }

    推荐阅读


    上一篇：在idea和eclipse部署Tomcat设置图片虚拟访问路径的操作

    下一篇：牛牛的等差数列