[BZOJ2877][Noi2012]魔幻棋盘

这题很囧，去年被炫教抓到题目（虽然炫教抓到的是一维的），可惜我们学校的人恰好都没有去省队培训……唉……首先讲一下一维怎么做吧。

欧几里得说过gcd(a, b, c, d) = gcd(b-a, c-b, d-c, a)。嗯，所以我们就对数列进行差分，b[i] = a[i]-a[i-1]，这样我们在查询[L, R]的gcd的时候，只要查询gcd(a[L], gcd(b[L+1] ... b[R])即可，而修改的时候，只要修改a[L..R]和b[L], b[R+1]即可。这样做法就很明显了，用两个线段树分别维护a和b。实际上做的时候，维护a可以直接用树状数组维护前缀和sum：对区间[L, R]加c，等同于sum[L] += c, sum[R+1] -= c，查询i直接求sum[i]即可。

我们再来看一下二维的怎么做。。然后我们换一种维护的方法。因为题目要求一定会查询到守护者a[x, y]，所以我们以(x, y)为原点，建立直角座标系。二维的一样是得差分，对于第四象限的点：b[i, j] = a[i, j] - a[i-1, j] - a[i, j-1] + a[i-1, j-1]，其他三个象限类似。

  • 原点的值：就是原点的值
  • 座标轴上的值：用离原点比较远的那个点-和他相邻、离原点近的点
  • 某个象限上的值：同理，用离原点远的点+离原点近的点-2个旁边的点。

查询的时候，很愉悦的在线段树里面查询[x1, y1]到[x2, y2]即可。

但是修改就很麻烦了，四个象限、座标轴、原点分别单点修改（有关象限的4个点，有关座标轴2个点，有关原点1个点）。

题外话：其实这题的主要思想就是把区间乃至矩阵修改转化成单点修改，因为二维线段树无法实现区间修改。做这题的时候一直忽略守护者一定会被计算，变成随意查询和修改，程序打完才发现根本无法保证修改的时间复杂度。后来十分努力的研读了一下题解才发现必须得用到守护者这个条件，似乎没有这个条件的话就做不了了。

果然还是很弱，数据结构都虐不过。

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
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178

#include <cstdio>
#include <algorithm>

//------Common things & Memory pool
inline long long gcd(long long a, long long b)
{
  if (a < 0) a = -a;
  if (b < 0) b = -b;
  for (long long r; b; a = b, b = r) r = a%b;
  return a;
}
const int MAXN = 500002;
char _memory[1<<26], *_memory_top = _memory;
template<typename T> inline T* newmemory(const size_t length)
{
  _memory_top += length * sizeof(T);
  return reinterpret_cast<T*>(_memory_top - length * sizeof(T));
}

//------1D Segment Class
class SegmentTree
{
  int n, st, ed, mul;
  long long *s, x;
  void build(const int p, const int lef, const int rig, const long long *a)
  {
    if (lef == rig) { s[p] = a[lef]; return; }
    const int mid = (lef+rig)/2;
    build(p*2, lef, mid, a);
    build(p*2+1, mid+1, rig, a);
    s[p] = gcd(s[p*2], s[p*2+1]);
  }
  long long query(const int p, const int lef, const int rig)
  {
    if (st <= lef && rig <= ed) return s[p];
    const int mid = (lef+rig)/2;
    long long res = 0;
    if (st <= mid) res = query(p*2, lef, mid);
    if (mid+1 <= ed) res = gcd(res, query(p*2+1, mid+1, rig));
    return res;
  }
  void modify(const int p, const int lef, const int rig)
  {
    if (lef == rig) { s[p] = s[p]*mul+x; return; }
    const int mid = (lef+rig)/2;
    if (st <= mid) modify(p*2, lef, mid);
    else modify(p*2+1, mid+1, rig);
    s[p] = gcd(s[p*2], s[p*2+1]);
  }
public:
  SegmentTree(const int length, const long long* a): n(length), s(newmemory<long long>((n+1)*4)) { build(1, 1, n, a); }
  long long Query(const int lef, const int rig) { st = lef, ed = rig; return query(1, 1, n); }
  void Modify(const int pos, const long long value) { st = pos, x = value, mul = 0; modify(1, 1, n); }
  void Add(const int pos, const long long value) { st = pos, x = value, mul = 1; modify(1, 1, n); }
};

//------2D Matrix & Segment Class
typedef long long** Matrix;
class SegmentTree2D
{
  int n, m, stx, sty, edx, edy;
  long long x;
  SegmentTree* s;
  void build(const int p, const int lef, const int rig, const Matrix& mat)
  {
    if (lef == rig) { s[p] = SegmentTree(m, mat[lef]); return; }
    const int mid = (lef+rig)/2;
    build(p*2, lef, mid, mat);
    build(p*2+1, mid+1, rig, mat);
    long long *tmp = newmemory<long long>(m+1);
    for (int i = 1; i <= m; ++i) tmp[i] = gcd(s[p*2].Query(i, i), s[p*2+1].Query(i, i));
    s[p] = SegmentTree(m, tmp);
  }
  long long query(const int p, const int lef, const int rig)
  {
    if (stx <= lef && rig <= edx) return s[p].Query(sty, edy);
    const int mid = (lef+rig)/2;
    long long res = 0;
    if (stx <= mid) res = query(p*2, lef, mid);
    if (mid+1 <= edx) res = gcd(res, query(p*2+1, mid+1, rig));
    return res;
  }
  void modify(const int p, const int lef, const int rig)
  {
    if (lef == rig) { s[p].Add(sty, x); return; }
    const int mid = (lef+rig)/2;
    if (stx <= mid) modify(p*2, lef, mid);
    else modify(p*2+1, mid+1, rig);
    s[p].Modify(sty, gcd(s[p*2].Query(sty, sty), s[p*2+1].Query(sty, sty)));
  }
public:
  SegmentTree2D(const int a, const int b, const Matrix& mat): n(a), m(b), s(newmemory<SegmentTree>(4*(n+1))) { build(1, 1, n, mat); }
  long long Query(const int x1, const int y1, const int x2, const int y2)
  {
    stx = x1, sty = y1, edx = x2, edy = y2;
    return query(1, 1, n);
  }
  void Modify(const int i, const int j, const long long value)
  {
    if (i < 1 || j < 1 || i > n || j > m) return;
    stx = edx = i, sty = edy = j, x = value;
    modify(1, 1, n);
  }
};

//------Main program & functions
int n, m, t, x, y;
long long c;
int main()
{
  freopen("bzoj2877.in", "r", stdin);
  freopen("bzoj2877.out", "w", stdout);
  scanf("%d%d%d%d%d", &n, &m, &x, &y, &t);
  Matrix mat = newmemory<long long*>(n+1);
  for (int i = 0; i <= n; ++i) mat[i] = newmemory<long long>(m+1);

  for (int i = 1; i <= n; ++i)
    for (int j = 1; j <= m; ++j)
      scanf("%I64d", &mat[i][j]);
  for (int i = 1; i < x; ++i)
  {
    for (int j = 1; j < y; ++j) mat[i][j] += mat[i+1][j+1]-mat[i][j+1]-mat[i+1][j];
    for (int j = m; j > y; --j) mat[i][j] += mat[i+1][j-1]-mat[i][j-1]-mat[i+1][j];
  }
  for (int i = n; i > x; --i)
  {
    for (int j = 1; j < y; ++j) mat[i][j] += mat[i-1][j+1]-mat[i][j+1]-mat[i-1][j];
    for (int j = m; j > y; --j) mat[i][j] += mat[i-1][j-1]-mat[i][j-1]-mat[i-1][j];
  }
  for (int i = 1; i < y; ++i) mat[x][i] -= mat[x][i+1];
  for (int i = m; i > y; --i) mat[x][i] -= mat[x][i-1];
  for (int i = 1; i < x; ++i) mat[i][y] -= mat[i+1][y];
  for (int i = n; i > x; --i) mat[i][y] -= mat[i-1][y];
  SegmentTree2D seg(n, m, mat);

  for (int i = 0, op, x1, y1, x2, y2; i < t; ++i)
  {
    scanf("%d%d%d%d%d", &op, &x1, &y1, &x2, &y2);
    if (op == 0)
      printf("%I64d\n", seg.Query(x-x1, y-y1, x+x2, y+y2));
    else
    {
      scanf("%I64d", &c);
      if (x1<=x && y1<=y) seg.Modify(x1-1, y1-1,  c); else
      if (x1> x && y1> y) seg.Modify(x1  , y1  ,  c); else
      if (x1<=x && y1> y) seg.Modify(x1-1, y1  , -c); else
      if (x1> x && y1<=y) seg.Modify(x1  , y1-1, -c);

      if (x2< x && y2< y) seg.Modify(x2  , y2  ,  c); else
      if (x2>=x && y2>=y) seg.Modify(x2+1, y2+1,  c); else
      if (x2< x && y2>=y) seg.Modify(x2  , y2+1, -c); else
      if (x2>=x && y2< y) seg.Modify(x2+1, y2  , -c);

      if (x1<=x && y2>=y) seg.Modify(x1-1, y2+1,  c); else
      if (x1> x && y2< y) seg.Modify(x1  , y2  ,  c); else
      if (x1<=x && y2< y) seg.Modify(x1-1, y2  , -c); else
      if (x1> x && y2>=y) seg.Modify(x1  , y2+1, -c);

      if (x2< x && y1> y) seg.Modify(x2  , y1  ,  c); else
      if (x2>=x && y1<=y) seg.Modify(x2+1, y1-1,  c); else
      if (x2< x && y1<=y) seg.Modify(x2  , y1-1, -c); else
      if (x2>=x && y1> y) seg.Modify(x2+1, y1  , -c);

      if (x1<=x && x2>=x)
      {
        if (y1<=y) seg.Modify(x, y1-1, -c); else seg.Modify(x, y1  ,  c);
        if (y2>=y) seg.Modify(x, y2+1, -c); else seg.Modify(x, y2  ,  c);
      }
      if (y1<=y && y2>=y)
      {
        if (x1<=x) seg.Modify(x1-1, y, -c); else seg.Modify(x1  , y,  c);
        if (x2>=x) seg.Modify(x2+1, y, -c); else seg.Modify(x2  , y,  c);
      }

      if (x1<=x && x2>=x && y1<=y && y2>=y) seg.Modify(x, y, c);
    }
  }
}

Comments