CF914D Bash and a Tough Math Puzzle

发表于 | 分类于

Description

你有一个长为\(n\)的正整数序列\(A\)，要求滋磁如下操作（\(q\)次）：

  • 1 l r x：对于区间\([l, r]\)，询问是否可以修改其中的至多一个数，使得这段区间内数的最大公约数为\(x\)。
  • 2 i x：将\(A_i\)修改为\(x\)。

\(1\leq n, q\leq 500000, A_i, x\leq 10^9\)。

Solution

考虑询问那个条件的本质……

首先如果区间内恰有一个数不是\(x\)的倍数，那么改掉那个数就行；如果没有一个不是\(x\)的倍数，那么随便改一个就完事了；对于其他情况，就玩不动了。因此，条件等价于区间内不是\(x\)的倍数的数至少有一个。

那么我们考虑从\(l\)开始向右，构造一个极长的为\(x\)倍数的段，再从\(r\)向左构造这么一个，那么如果区间内全是\(x\)的倍数的话这两个段就重了，只有一个不是的话那么这两个段会在一个地方断开。

然后考虑怎么去求这两个段……首先显然可以维护区间\(\gcd\)，然后二分答案求出这个段长度，但是这样的话复杂度是\(O(n\log^3 n)\)的，很吃不消。因此我们把那个普通的二分，改成线段树上二分，就跑的匪快了（单次求复杂度只有\(O(\log n)\)）。

Code

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
#include <cstdio>
#include <cstring>
#include <cstdlib>
#include <algorithm>
#include <functional>
#include <utility>
#include <vector>
const int maxn = 500005;
const int maxno = maxn << 2;
int gcd(int a, int b) {
  if(!b) return a;
  else return gcd(b, a % b);
}

struct rec {
  int o, L, R;
  rec(int a = 0, int b = 0, int c = 0) {
    o = a; L = b; R = c;
  }
};
int A[maxn]; int val[maxno];
void maintain(int o) {
  val[o] = gcd(val[o << 1], val[o << 1 | 1]);
}
void build_tree(int o, int L, int R) {
  if(L == R) {
    val[o] = A[L];
  } else {
    int M = (L + R) / 2;
    build_tree(o << 1, L, M);
    build_tree(o << 1 | 1, M + 1, R);
    maintain(o);
  }
}
void modify(int o, int L, int R, const int &p, const int &v) {
  if(L == R) {
    val[o] = A[L] = v;
  } else {
    int M = (L + R) / 2;
    if(p <= M) modify(o << 1, L, M, p, v);
    else modify(o << 1 | 1, M + 1, R, p, v);
    maintain(o);
  }
}
void obtain(int o, int L, int R, int ql, int qr, std::vector<rec> &V) {
  if(ql <= L && R <= qr) {
    V.push_back(rec(o, L, R));
  } else {
    int M = (L + R) / 2;
    if(ql <= M) obtain(o << 1, L, M, ql, qr, V);
    if(qr > M) obtain(o << 1 | 1, M + 1, R, ql, qr, V);
  }
}

int n;
int query_l(int p, int x) {
  if(A[p] % x) return p - 1;
  std::vector<rec> V; obtain(1, 1, n, p, n, V);
  rec rb;
  for(int i = 0; i < V.size(); i ++) {
    const rec &th = V[i];
    if(val[th.o] % x) {
      rb = th; break;
    }
  }
  if(rb.o == 0) return n;
  int o = rb.o, L = rb.L, R = rb.R;
  if(A[L] % x) return L - 1;
  while(L < R) {
    int lc = o << 1, rc = o << 1 | 1;
    int M = (L + R) / 2;
    if(val[lc] % x == 0 && A[M + 1] % x == 0) o = rc, L = M + 1;
    else o = lc, R = M;
  }
  return L;
}
int query_r(int p, int x) {
  if(A[p] % x) return p + 1;
  std::vector<rec> V; obtain(1, 1, n, 1, p, V);
  rec rb;
  for(int i = V.size() - 1; i >= 0; i --) {
    const rec &th = V[i];
    if(val[th.o] % x) {
      rb = th; break;
    }
  }
  if(rb.o == 0) return 1;
  int o = rb.o, L = rb.L, R = rb.R;
  if(A[R] % x) return R + 1;
  while(L < R) {
    int lc = o << 1, rc = o << 1 | 1;
    int M = (L + R) / 2;
    if(val[rc] % x == 0 && A[M] % x == 0) o = lc, R = M;
    else o = rc, L = M + 1;
  }
  return L;
}

int main() {
  scanf("%d", &n);
  for(int i = 1; i <= n; i ++) scanf("%d", &A[i]);
  build_tree(1, 1, n);
  int q; scanf("%d", &q);
  while(q --) {
    int op; scanf("%d", &op);
    if(op == 1) {
      int l, r, x; scanf("%d%d%d", &l, &r, &x);
      int rv = query_l(l, x), lv = query_r(r, x);
#ifdef LOCAL
      printf("Block : (%d, %d) and (%d, %d)\n", l, rv, lv, r);
#endif
      if(rv + 2 >= lv) puts("YES");
      else puts("NO");
      // fflush(stdout);
    } else {
      int p, v; scanf("%d%d", &p, &v);
      modify(1, 1, n, p, v);
    }
  }
  return 0;
}