[HEOI]2015公约数序列

Posted on Edited on In Word count in article: 602 Reading time ≈ 2 mins.
分块好题

[HEOI2015]公约数数列

题目大意

给定一个序列，有两种操作

  • 修改第 \(id\) 个数，让它变成\(x\)
  • 查询最小的\(id\)，让他满足 \[ (\otimes_{i=0}^{id}a_i)*\gcd(a_0,a_1\cdots a_{id})=x \]

分析

这个\(\gcd\)有点东西，是这只可能不断变小的

所以这个是单调的，没鸟用

所以直接暴力分块乱搞，练练代码能力还是不错的选择

只是说有地方时可以优化的

比如说，当前\(\gcd\)前缀不是查询的\(x\)的约数，就可以直接跳过的

还有，如果说这个块对答案没有\(\gcd\)没有贡献，就可以直接二分查找异或前缀和了

然后似乎就完了

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
#include <bits/stdc++.h>

using namespace std;

typedef long long ll;
const ll maxn = 1e5 + 10;
const ll mod = 1e9 + 7;

inline ll __read()
{
    ll x(0), t(1);
    char o (getchar());
    while (o < '0' || o > '9') {
        if (o == '-') t = -1;
        o = getchar();
    }
    for (; o >= '0' && o <= '9'; o = getchar()) {
        x = (x << 1) + (x << 3) + (o ^ 48);
    }
    return x * t;
}

ll gcd(ll x, ll y)
{
    if (y == 0) return x;
    return gcd(y, x % y);
}

ll n, p, q, a[maxn], l[505], r[505], id[maxn];
ll gd[maxn], xr[maxn], map_id[maxn];

inline bool cmp(int x, int y)
{
    if (xr[x] == xr[y]) return x < y;
    return xr[x] < xr[y];
}

void Update(ll pos)
{
    if (pos > l[id[pos]]) {
        gd[pos] = gcd(gd[pos - 1], a[pos]);
        xr[pos] = xr[pos - 1] ^ a[pos];
    } else {
        gd[pos] = xr[pos] = a[pos];
    }
    for (int i = pos + 1; i <= r[id[pos]]; ++i) {
        gd[i] = gcd(gd[i - 1], a[i]);
        xr[i] = xr[i - 1] ^ a[i];
    }

    sort(map_id + l[id[pos]], map_id + r[id[pos]] + 1, cmp);
}

inline ll Find(ll l, ll r, ll val)
{
    ll ans(l);
    while (l <= r) {
        ll mid ((l + r) >> 1);
        if (xr[map_id[mid]] >= val) ans = mid, r = mid - 1;
        else l = mid + 1;
    }
    return ans;
}

inline ll Query(ll x)
{
    ll ans(-1), q_gd(a[1]), q_xr(0);
    for (int i = 1; i <= id[n] && ans == -1; ++i) {
        if (x % gcd(q_gd, gd[r[i]])) {
            q_gd = gcd(q_gd, gd[r[i]]);
            q_xr ^= xr[r[i]];
            continue;
        }
        if (gcd(q_gd, gd[r[i]]) == q_gd) {
            if (x % q_gd == 0) {
                ll targer = (x / q_gd) ^ q_xr;
                ll pos = Find(l[i], r[i], targer);
                if (xr[map_id[pos]] == targer) ans = map_id[pos];
            }
            q_xr ^= xr[r[i]];
        } else {
            for (int j = l[i]; j <= r[i]; ++j) {
                q_gd = gcd(q_gd, a[j]);
                q_xr = q_xr ^ a[j];
                if (q_gd * q_xr == x) {
                    ans = j;
                    break;
                }
            }
        }
    }
    return ans;
}

char Opt[10];
signed main()
{
    n = __read();
    p = sqrt(n);
    for (int i = 1; i <= n; ++i) {
        a[i] = __read();
        id[i] = (i - 1) / p + 1;
        map_id[i] = i;
        if (!l[id[i]]) l[id[i]] = i;
        r[id[i]] = i;
    }
    for (int i = 1; i <= id[n]; ++i) Update(l[i]);

    q = __read();
    while (q--) {
        scanf ("%s", Opt);
        if (*Opt == 'M') {
            ll pos = __read() + 1, x = __read();
            a[pos] = x;
            Update(pos);
        } else {
            ll x = __read();
            ll ans = Query(x);
            if (ans == -1) puts("no");
            else printf ("%lld\n", ans - 1);
        }
    }
    system("pause");
}