题解 P4108【[HEOI2015]公约数数列】

看到这种奇怪的操作，首先想到分块。

以下记值域为 \(w\)，块长为 \(B\)。

前缀 \(\gcd\) 显然单调不增，而且后一个必须是前一个的因数，如果变化至少要减半。因此，我们知道，共有 \(\mathcal O(\log w)\) 个不同的前缀 \(\gcd\)。我们可以接受对这些块暴力，只需要对前缀 \(\gcd\) 都相同的块能快速求答案即可。

有以上思路做铺垫，容易想到设 \(\operatorname{l}(x)\) 为第 \(x\) 块的左端点（含），\(\operatorname{r}(x)\) 为第 \(x\) 块的右端点（含），\(\operatorname{pos}(i)\) 为第 \(i\) 个数所在块，\(\operatorname{bgcd}(x)\) 为第 \(x\) 块的 \(\gcd\)，\(\operatorname{bxor}(i)\) 表示区间 \([\operatorname{l}(\operatorname{pos}(i)),i]\) 的异或和。同时，我们对每个块维护一个 map \(\operatorname{bfirst}\)，表示这个块内每个值作为 \(\operatorname{bxor}\) 第一次出现的位置。

对于查询 \(x\) 操作，从前往后扫描每个块，维护当前 \(\gcd\) 和异或和。利用 \(\operatorname{bgcd}\) 容易判断这个块内前缀 \(\gcd\) 是否发生变化。如果发生变化，我们暴力整个块检查；如果未发生变化，即求 \(\operatorname{bfirst}(\frac{x}{g}\oplus s)\)，其中 \(g,s\) 为此前所有块的 \(\gcd\) 和异或和。暴力检查的块数为 \(\mathcal O(\log w)\)，这部分复杂度 \(\mathcal O(B\log^2w)\)（另一只 \(\log\) 是求 \(\gcd\)）；其他块的复杂度为 \(\mathcal O(\frac{n}{B}\log B)\)。

对于单点修改操作，暴力改所在块即可。复杂度 \(\mathcal O(B\log B)\)。

取 \(B=\sqrt{n}\)，总复杂度 \(\mathcal O(n\log n+q\sqrt{n}\log^2w)\)。

//By: OIer rui_er
#include <bits/stdc++.h>
#define rep(x,y,z) for(ll x=(y);x<=(z);x++)
#define per(x,y,z) for(ll x=(y);x>=(z);x--)
#define debug(format...) fprintf(stderr, format)
#define fileIO(s) do{freopen(s".in","r",stdin);freopen(s".out","w",stdout);}while(false)
using namespace std;
typedef long long ll;

mt19937 rnd(std::chrono::duration_cast<std::chrono::nanoseconds>(std::chrono::system_clock::now().time_since_epoch()).count());
ll randint(ll L, ll R) {
    uniform_int_distribution<ll> dist(L, R);
    return dist(rnd);
}

template<typename T> void chkmin(T& x, T y) {if(x > y) x = y;}
template<typename T> void chkmax(T& x, T y) {if(x < y) x = y;}

const ll N = 1e5+5, BS = 505;

ll n, a[N], q, L[BS], R[BS], pos[N], B, tot, bgcd[BS], bxor[N];
map<ll, ll> bfirst[BS];

void init() {
    B = sqrt(n);
    chkmin(B, n);
    chkmax(B, 1LL);
    while(++tot) {
        L[tot] = R[tot-1] + 1;
        R[tot] = min(tot*B, n);
        rep(i, L[tot], R[tot]) {
            pos[i] = tot;
            bgcd[tot] = __gcd(bgcd[tot], a[i]);
            bxor[i] = (i == L[tot] ? 0 : bxor[i-1]) ^ a[i];
            if(!bfirst[tot].count(bxor[i])) bfirst[tot][bxor[i]] = i;
        }
        if(R[tot] == n) break;
    }
}

void modify(ll p, ll k) {
    a[p] = k;
    bgcd[pos[p]] = 0;
    map<ll, ll>().swap(bfirst[pos[p]]);
    rep(i, L[pos[p]], R[pos[p]]) {
        bgcd[pos[p]] = __gcd(bgcd[pos[p]], a[i]);
        bxor[i] = (i == L[pos[p]] ? 0 : bxor[i-1]) ^ a[i];
        if(!bfirst[pos[p]].count(bxor[i])) bfirst[pos[p]][bxor[i]] = i;
    }
}

ll query(ll x) {
    ll gcd = 0, now = 0;
    rep(i, 1, tot) {
        if(gcd != __gcd(gcd, bgcd[i])) {
            rep(j, L[i], R[i]) {
                gcd = __gcd(gcd, a[j]);
                now ^= a[j];
                if(gcd * now == x) return j;
            }
        }
        else {
            if(x % gcd == 0 && bfirst[i].count((x/gcd)^now)) return bfirst[i][(x/gcd)^now];
            now ^= bxor[R[i]];
        }
    }
    return -1;
}

int main() {
    scanf("%lld", &n);
    rep(i, 1, n) scanf("%lld", &a[i]);
    init();
    for(scanf("%lld", &q); q; q--) {
        char op[8];
        scanf("%s", op);
        if(op[0] == 'M') {
            ll p, k;
            scanf("%lld%lld", &p, &k);
            modify(p+1, k);
        }
        else {
            ll x;
            scanf("%lld", &x);
            ll ans = query(x);
            if(ans == -1) puts("no");
            else printf("%lld\n", ans-1);
        }
    }
    return 0;
}