S2OJ - 1824. qiu

#题面

#题目描述

小 P 在二维平面的原点 $(0, 0)$，他现在朝着 y 轴正方向。

他会以如下方式放 $10^{10^{100}}$ 个球，第 $i$ 个的重量为 $i$：

在 $i$ 步，他会放下第 $i$ 个球；若他的右方第一个整点没有放球，那么向右转；向前走一单位长度。

前 25 步为：

21 22 23 24 25
20 7 8 9 10
19 6 1 2 11
18 5 4 3 12
17 16 15 14 13

小 P 回询问 $q$ 次，所有横坐标在 $[x_1, x_2]$ 中，纵坐标在 $[y_1, y_2]$ 中的整点，上面球的重量的和，答案可能很大，对 $2^{63} $取模。

#输入格式

第一行一个整数 $q$。

接下来 $q$ 行，每行四个整数 $x_1, x_2, y_1, y_2$。

#输出格式

一行一个整数，你的答案。

#输入输出样例

样例输入 #1

1
0 0 0 1

样例输出 #1

9

样例解释 #1

$1 + 8 = 9$。

#数据范围与约定

令 $W$ 为满足以下条件的最小正整数：$0 ≤ x_1, x_2, y_1, y_2 ≤ W$。

有：$W ≤ 10^{18}, x_1 ≤ x_2, y_1 ≤ y_2, q ≤ 10^6$。

• Subtask 1 (1 pts)：$W ≤ 10^4$；
• Subtask 2 (2 pts)：$W ≤ 10^7$；
• Subtask 3 (3 pts)：$W ≤ 10^9$；
• Subtask 4 (4 pts)：$W ≤ 10^{12}$；
• Subtask 5 (5 pts)：$q = 1$；
• Subtask 6 (85 pts)：$W ≤ 10^{18}$。

#思路

显然可以使用类似二维前缀和的思想将每次询问转化为求 $(0, 0) - (x, y)$ 矩形内所有数的和。

可以发现一个规律，在直线 $x = y$ 上的点 $(x, x)$ 的值为 $(2x + 1)^2$。则有 $(0, x)$ 的值为 $(2x + 1)^2 - x$，$(x, 0)$ 的值为 $\left(2(x - 1) + 1\right)^2 + 1 + (x - 1)$。为了方便后面的计算，可以用 $(x + 1, 0)$ 来表示，其值为 $(2x + 1)^2 + 1 + x$，其中 $(2x + 1)^2 + 1$ 为 $(x + 1, x)$ 的值。

接下来，对于矩形 $(0, 0) - (x, y)$，可以将其分为三部分：

1. 有行有列的折线，这条折线的和为：

   $$\begin{aligned} & \sum_{i = 0}^{\min(x - 1, y)} \underbrace{\left(\sum_{j = 0}^{x} (2i + 1)^2 - j \right)}_{(i, 0) \sim (i, i)} + \underbrace{\left(\sum_{j = 0}^{x} (2x + 1)^2 + 1 + j\right)}_{(i + 1, i) \sim (i + 1, 0)} \\ =& \sum_{i = 0}^{\min(x - 1, y)} \frac{\left(2(2i + 1)^2 + 1 \right) \times 2(i + 1)}{2} \\ =& 8 \sum i^3 + 16 \sum i^2 + 11 \sum i + 3 \times \left(\min(x - 1, y) + 1 \right) \\ \end{aligned}$$

2. 仅有行（$x - 1 \leq y$）

   $$\begin{aligned} & \sum_{i = x}^{y} \sum_{j = 0}^{x} (2i + 1)^2 - i + j \\ =& \sum_{i = x}^{y} \frac{\Big( \left((2i + 1)^2 - i \right) + \left((2i + 1)^2 - i + x \right) \Big) (x + 1)}{2} \\ =& \frac{x + 1}{2} \times \left(8 \sum i^2 + 6 \sum i + (y - x + 1)(x + 2) \right) \\ \end{aligned}$$

3. 仅有列（$x - 1 > y$）

   $$\begin{aligned} & \sum_{i = x}^{y} \sum_{j = 0}^{x} (2i + 1)^2 + 1 + i - j \\ =& \sum_{i = x}^{y} \frac{\Big( \left((2i + 1)^2 + 1 + i \right) + \left((2i + 1)^2 + 1 + i - y \right) \Big) (y + 1)}{2} \\ =& \frac{y + 1}{2} \times \left(8 \sum i^2 + 10 \sum i + (x - y - 1)(4 - y) \right) \end{aligned}$$

之后分别统计矩形中这三部分的元素和即可。

附录

$$\begin{aligned} \sum_{i = 0}^{n} i^3 &= \left(\frac{n (n + 1)}{2}\right)^2 \\ \sum_{i = 0}^{n} i^2 &= \frac{n (n + 1) (2n + 1)}{6} \\ \sum_{i = 0}^{n} i &= \frac{n (n + 1)}{2} \\ \end{aligned}$$

注：本文的推导过程中省略了一些非关键步骤。

#代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152

#include <iostream>
#include <algorithm>

using std::cin;
using std::cout;
const char endl = '\n';

const unsigned long long mod = 1ull << 63,
                         mod_mask = mod - 1;

/**
 * Calculates the sum of i from 1 to x
 *
 * @return x * (x + 1) / 2
 */
unsigned long long sum_i_1(unsigned long long x) {
    unsigned long long t1 = x,
                       t2 = x + 1;

    if (x % 2 == 0) t1 /= 2;
    else t2 /= 2;

    return t1 * t2;
}

/**
 * Calculates the sum of i^2 from 1 to x
 *
 * @return x * (x + 1) * (2 * x + 1) / 6
 */
unsigned long long sum_i_2(unsigned long long x) {
    unsigned long long t1 = x,
                       t2 = x + 1,
                       t3 = x * 2 + 1;

    if (t1 % 2 == 0) t1 /= 2;
    else t2 /= 2;

    if (t1 % 3 == 0) t1 /= 3;
    else if (t2 % 3 == 0) t2 /= 3;
    else t3 /= 3;

    return t1 * t2 * t3;
}

/**
 * Calculates the sum of i^3 from 1 to x
 *
 * @return (x * (x + 1) / 2) * (x * (x + 1) / 2)
 */
unsigned long long sum_i_3(unsigned long long x) {
    return sum_i_1(x) * sum_i_1(x);
}

/**
 * Calculates this:
 *
 * @code
 * --#+
 *    |
 *    |
 * @endcode
 *
 * #: (2x + 1)^2
 */
unsigned long long calc_all(unsigned long long x) {
    if (x < 0) return 0;

    return sum_i_3(x) * 8 + sum_i_2(x) * 16 + sum_i_1(x) * 11 + (x + 1) * 3;
}

/**
 * Calculates this:
 *
 * @code
 * --#(+)
 *    (|)
 *    (|)
 * @endcode
 *
 * #: (2x + 1)^2
 * (): not included
 */
unsigned long long calc_top(unsigned long long x, unsigned long long y) {
    unsigned long long res = sum_i_2(y) * 8 + sum_i_1(y) * 6 + (y - x + 1) * (x + 2),
                       t = x + 1;

    if (x > 0) {
        res -= sum_i_2(x - 1) * 8 + sum_i_1(x - 1) * 6;
    }

    if (res % 2 == 0) res /= 2;
    else t /= 2;

    return res * t;
}

/**
 * Calculates this:
 *
 * @code
 * (--#)+
 *      |
 *      |
 * @endcode
 *
 * #: (2x + 1)^2
 * (): not included
 */
unsigned long long calc_right(unsigned long long x, unsigned long long y) {
    unsigned long long res = sum_i_2(x - 1) * 8 + sum_i_1(x - 1) * 10 + (x - y - 1) * (4 - y),
                       t = y + 1;

    if (y > 0) {
        res -= sum_i_2(y) * 8 + sum_i_1(y) * 10;
    }

    if (res % 2 == 0) res /= 2;
    else t /= 2;

    return res * t;
}

unsigned long long calc(long long x, long long y) {
    if (x < 0 || y < 0) return 0;

    if (x - 1 <= y) {
        return calc_all(x - 1) + calc_top(x, y);
    }

    // x - 1 > y
    return calc_all(y) + calc_right(x, y);
}

int main() {
    std::ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int q;

    cin >> q;

    while (q--) {
        long long x1, x2, y1, y2;

        cin >> x1 >> x2 >> y1 >> y2;

        cout << ((calc(x2, y2) - calc(x1 - 1, y2) - calc(x2, y1 - 1) + calc(x1 - 1, y1 - 1)) & mod_mask) << endl;
    }

    return 0;
}