ABC449 D - Make Target 2

题意: 在标准坐标系下，max(|x|,|y|)为偶数则标记为黑巧，奇数标记为白巧，我们圈出一个方框，x轴上范围是[L,R]，y轴上范围是[D,U]，求出方框中圈到了多少个黑巧。

知识点: 数学，思维

思路: 通过题目给出的示例的图我们可以发现这就是一个回形矩阵，这时我们可以沿着两条对角线切一下，如下图所示: alt

而此时的左右两个三角形区域，我们可以用|x|>|y|来表述，接下来我将详细讲解|x|>|y|的求取方法，|y|≤|x|的方法和这个类似。

因为max(|x|,|y|)为偶数才是黑色，所以我们可以枚举出在(L,R)中的|x|>|y|且x为偶数的点，接着对每个x=?的那条线，求[D,U]内满足|x|>|y|的点有多少个，我们可以通过图来轻易的得到y的范围就是

$y\in [max(-|x|+1,D), min(|x|-1,U)]\: \: \: (因为是<不是≤所以是-|x|+1而不是-|x|)$

所以对于每个x来说，y上满足的点的数量为

$y_{x} = max(0, min(|x|-1,U)-max(-|x|+1,D)+1)$

这样我们每个x就只要花O(1)的时间就可以算出黑巧的数量了，所以算出|x|>|y|的复杂度为O(X)。X即遍历x的次数。

参考代码:

#include<bits/stdc++.h>
#define ll long long
using namespace std;
int main()
{
	ll l,r,d,u;
	cin >> l >> r >> d >> u;
	ll startx=l+(l&1),starty=d+(d&1);  //这里用%2可能是-1所以直接用&
	ll cnt=0;
	for(ll i=startx;i<=r;i+=2)
		cnt+=max(0LL,min(abs(i)-1LL,u)-max(-abs(i)+1LL,d)+1LL);
	for(ll j=starty;j<=u;j+=2)
		cnt+=max(0LL,min(abs(j),r)-max(-abs(j),l)+1LL);
	cout << cnt << endl;
	return 0;
}