So We Back In The Mine

第一行输入一个正整数q，表示总共会有q次询问。
之后输入q行，表示每次询问。每一行输入四个整数，依次是 $x_1, y_1,x_2,y_2$ ，之间使用一个空格符分隔，表示要查询钻石数的矩形区域。

数据规范：
* $1 \le q \le 2 \times 10^5$ .
* $-2 \times 10^4 \le x_1,y_1,x_2, y_2 \le 2 \times 10^4$ .
* $x_1 \le x_2$ .
* $y_1 \le y_2$ .
* 保证所有输入的数都是整数。

对于每行询问，依次输出询问区域内的钻石数，使用一个整数表示，每个输出占一行。

注意用来存储答案的变量的数据类型，不能使用32位整型。
如果您使用C、C++，不能使用int类型（32位整型），请使用long long int类型（64位整型）。
如果您使用Java，不能使用int类型（32位整型），请使用long类型（64位整型）。
如果您使用Python2、Python3，请随意。。。

C++11(clang++ 3.9) 解法, 执行用时: 138ms, 内存消耗: 3556K, 提交时间: 2019-12-07 16:23:32

#include<iostream>
using namespace std;
typedef long long ll;
ll s[1<<16];
int q, x1, x2, y1, y2;
ll gt(ll x, ll y)
{
    if(x > y)
        swap(x, y);
    return s[x] + (x+1)*(x+3+y)*(y-x) / 2;
}
int main()
{
    s[0] = 1;
    for(int i = 1; i < 2e4+7; i++)
        s[i] = s[i-1] + (2*i+1) * (i+1);
    scanf("%d", &q);
    while(q-- > 0)
    {
        scanf("%d%d%d%d", &x1, &y1, &x2, &y2);
        if(x2 <= 0)
        {
            swap(x1, x2);
            x1 = -x1, x2 = -x2;
        }
        if(y2 <= 0)
        {
            swap(y1, y2);
            y1 = -y1, y2 = -y2;
        }
        if(x1 > 0 && y1 > 0)
        {
            printf("%lld\n", gt(x2, y2) - gt(x1-1, y2) - gt(x2, y1-1) + gt(x1-1, y1-1));
        }
        else if(x1 > 0 && y1 <= 0)
        {
            printf("%lld\n", gt(x2, y2) - gt(x1-1, y2) + gt(x2, -y1) - gt(x1-1, -y1) - gt(x2, 0) + gt(x1-1, 0));
        }
        else if(x1 <= 0 && y1 > 0)
        {
            printf("%lld\n", gt(x2, y2) - gt(x2, y1-1) + gt(-x1, y2) - gt(-x1, y1-1) - gt(0, y2) + gt(0, y1-1));
        }
        else
        {
            printf("%lld\n", gt(x2, y2) + gt(-x1, y2) + gt(x2, -y1) + gt(-x1, -y1) - gt(0, x2) - gt(0, -x1) - gt(0, y2) - gt(0, -y1) + 1);
        }
    }
}

C++14(g++5.4) 解法, 执行用时: 232ms, 内存消耗: 8408K, 提交时间: 2019-12-09 16:10:21

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N = 1e5+10;
ll q,a,b,c,d;
ll cal1(ll n)
{
	return n*(n+1)/2;
}
ll cal2(ll n)
{
	return n*(n+1)*(2*n+1)/6; 
}
ll pre(ll n,ll m)//(0,0)-(n,m)
{
	if(n<0||m<0)
	return 0;
	n++;m++;
	ll mi=min(n,m);
	ll ma=max(n,m);
	ll ans=cal2(mi)*2-cal1(mi);//(0,0)-(mi,mi)正方形
	ans+=mi*(cal1(ma)-cal1(mi));//剩余矩形 
	return ans; 
}
ll solve(ll a,ll b,ll c,ll d)//(a,b)-(c,d)
{
	return pre(c,d)+pre(a-1,b-1)-pre(c,b-1)-pre(a-1,d);
}
int main()
{
	scanf("%lld",&q);
	while(q--)
	{
		ll ans=0;
		scanf("%lld%lld%lld%lld",&a,&b,&c,&d);
		if(c>=0&&d>=0)
		{
			if(a>=0&&b>=0)
			ans=solve(a,b,c,d);
			else if(a>=0&&b<0)
			ans=solve(a,0,c,d)+solve(a,1,c,-b);
			else if(a<0&&b>=0)
			ans=solve(0,b,c,d)+solve(1,b,-a,d);
			else if(a<0&&b<0)
			ans=solve(0,0,c,d)+solve(1,0,-a,d)+solve(0,1,c,-b)+solve(1,1,-a,-b);
		}
		else if(c>=0&&d<0)
		{
			if(a>=0)
			ans=solve(a,-d,c,-b);
			else if(a<0)
			ans=solve(0,-d,c,-b)+solve(1,-d,-a,-b);
		}
		else if(c<0&&d>=0)
		{
			if(b>=0)
			ans=solve(-c,b,-a,d);
			else if(b<0)
			ans=solve(-c,0,-a,d)+solve(-c,1,-a,-b);
		}
		else if(c<0&&d<0)
		ans=solve(-c,-d,-a,-b);
		printf("%lld\n",ans);
	}
}

详情