[ABC254F] Rectangle GCD Solution

[ABC254F] Rectangle GCD Solution更好的阅读体验戳此进入题面SolutionCodeUPD

更好的阅读体验戳此进入

题面

$a_n, b_n$ $n \times n$ $(i, j)$ $a_i + b_j$ $q$ $h_1, h_2, w_1, w_2$ $(h_1, w_1)$ $(h_2, w_2)$ $\gcd$ 。

Solution

$\gcd(a, b) = \gcd(a, b - a)$ $(i, j)$ $(x, y)$ 为右下角的矩形：

$a_{i} + b_{j}$	$a_{i} + b_{j + 1}$	$a_{i} + b_{j + 2}$	$\cdots$	$a_{i} + b_{y}$
$a_{i + 1} + b_{j}$	$a_{i + 1} + b_{j + 1}$	$a_{i + 1} + b_{j + 2}$	$\cdots$	$a_{i + 1} + b_{y}$
$a_{i + 2} + b_{j}$	$a_{i + 2} + b_{j + 1}$	$a_{i + 2} + b_{j + 2}$	$\cdots$	$a_{i + 2} + b_{y}$
$\cdots$	$\cdots$	$\cdots$	$\cdots$	$\cdots$
$a_{x} + b_{j}$	$a_{x} + b_{j + 1}$	$a_{x} + b_{j + 2}$	$\cdots$	$a_{x} + b_{y}$

然后不难发现可以通过更相减损术，对这个矩形横向进行差分：

$a_{i} + b_{j}$	$b_{j + 1} - b_j$	$b_{j + 2} - b_{j + 1}$	$\cdots$	$b_{y} - b_{y - 1}$
$a_{i + 1} + b_{j}$	$b_{j + 1} - b_j$	$b_{j + 2} - b_{j + 1}$	$\cdots$	$b_{y} - b_{y - 1}$
$a_{i + 2} + b_{j}$	$b_{j + 1} - b_j$	$b_{j + 2} - b_{j + 1}$	$\cdots$	$b_{y} - b_{y - 1}$
$\cdots$	$\cdots$	$\cdots$	$\cdots$	$\cdots$
$a_{x} + b_{j}$	$b_{j + 1} - b_j$	$b_{j + 2} - b_{j + 1}$	$\cdots$	$b_{y} - b_{y - 1}$

$a$ $[w_1 + 1, w_2]$ $\gcd$ $b$ $[h_1 + 1, h_2]$ $\gcd$ $a_{h_1} + b_{w_1}$ $\gcd$ $w_1 \neq w_2$ $h_1 \neq h_2$ 。

$\gcd$ ，这个东西也就可以直接挂在线段树上，或者因为没有修改，用 ST表也行（不过我不喜欢 ST表，所以用的线段树维护）。

Code


xxxxxxxxxx
81
1
#define _USE_MATH_DEFINES
2
#include <bits/stdc++.h>
3

4
#define PI M_PI
5
#define E M_E
6
#define npt nullptr
7
#define SON i->to
8
#define OPNEW void* operator new(size_t)
9
#define ROPNEW(arr) void* Edge::operator new(size_t){static Edge* P = arr; return P++;}
10

11
using namespace std;
12

13
mt19937 rnd(random_device{}());
14
int rndd(int l, int r){return rnd() % (r - l + 1) + l;}
15
bool rnddd(int x){return rndd(1, 100) <= x;}
16

17
typedef unsigned int uint;
18
typedef unsigned long long unll;
19
typedef long long ll;
20
typedef long double ld;
21

22
#define MAXN (210000)
23

24
template < typename T = int >
25
inline T read(void);
26

27
int N, Q;
28
int A[MAXN], B[MAXN], dA[MAXN], dB[MAXN];
29

30
class SegTree{
31
private:
32
    int tr[MAXN << 2];
33
    #define LS (p << 1)
34
    #define RS (LS | 1)
35
    #define MID ((gl + gr) >> 1)
36
public:
37
    void Pushup(int p){tr[p] = __gcd(tr[LS], tr[RS]);}
38
    void Build(bool flag, int p = 1, int gl = 1, int gr = N){//true - line(y), false - row(x)
39
        if(gl == gr)return tr[p] = flag ? dB[gl] : dA[gl], void();
40
        Build(flag, LS, gl, MID), Build(flag, RS, MID + 1, gr);
41
        Pushup(p);
42
    }
43
    int Query(int l, int r, int p = 1, int gl = 1, int gr = N){
44
        if(l <= gl && gr <= r)return tr[p];
45
        if(r <= MID)return Query(l, r, LS, gl, MID);
46
        if(l >= MID + 1)return Query(l, r, RS, MID + 1, gr);
47
        return __gcd(Query(l, r, LS, gl, MID), Query(l, r, RS, MID + 1, gr));
48
    }
49
}stLine, stRow;
50

51
int main(){
52
    N = read(), Q = read();
53
    for(int i = 1; i <= N; ++i)A[i] = read(), dA[i] = A[i] - A[i - 1];
54
    for(int i = 1; i <= N; ++i)B[i] = read(), dB[i] = B[i] - B[i - 1];
55
    stLine.Build(true), stRow.Build(false);
56
    while(Q--){
57
        int h1 = read(), h2 = read(), w1 = read(), w2 = read();
58
        int ans = A[h1] + B[w1];
59
        if(w1 != w2)ans = __gcd(ans, stLine.Query(w1 + 1, w2));
60
        if(h1 != h2)ans = __gcd(ans, stRow.Query(h1 + 1, h2));
61
        printf("%d\n", abs(ans));
62
    }
63
    fprintf(stderr, "Time: %.6lf\n", (double)clock() / CLOCKS_PER_SEC);
64
    return 0;
65
}
66

67
template < typename T >
68
inline T read(void){
69
    T ret(0);
70
    int flag(1);
71
    char c = getchar();
72
    while(c != '-' && !isdigit(c))c = getchar();
73
    if(c == '-')flag = -1, c = getchar();
74
    while(isdigit(c)){
75
        ret *= 10;
76
        ret += int(c - '0');
77
        c = getchar();
78
    }
79
    ret *= flag;
80
    return ret;
81
}

UPD

update-2022_12_06 初稿