[题解]CF1355C-Count Triangles

Posted on In

写这个不是因为这题多难或者有意思,纯粹是纪念一下自己有多傻逼=-=

题意

给出\(A,B,C,D\)求满足\(A \leq x \leq B \leq y \leq C \leq z \leq D\),的\(x,y,z\)能组成的三角形个数

\(1 \leq A \leq B \leq C \leq D \leq 5e5\)

思路

很显然只要满足\(z < x+y\)且\(C \leq z \leq D\)就行=-=

那么枚举\(x\),把\([x+B,x+C]\)加1(用前缀和维护一下就行),再枚举\(z\)统计满足\(z < x+y\)的个数就行=-=

复杂度\(O(C)\)

就这玩意都做不出来,我是傻逼

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
//C 
#include <bits/stdc++.h>
using namespace std;
const int maxn = 2e6+10;
typedef long long ll;
int pre[maxn];
int main(){
	ll a,b,c,d,ans = 0;
	cin >> a >> b >> c >> d;
	for(int i = a;i <= b;i++)pre[i+b]++,pre[i+c+1]--;
	for(int i = 1;i < maxn;i++)pre[i] += pre[i-1];
	for(int i = 0;i < maxn;i++)ans += pre[i]*max(0ll,min(d,(ll)(i-1)) - c + 1); 
	cout << ans;
	return 0;
}