记录编号	599539	评测结果	AAAAAAAAAA
题目名称	[HEOI 2015]公约数数列	最终得分	100
用户昵称	wdsjl	是否通过	通过
代码语言	C++	运行时间	2.667 s
提交时间	2025-03-20 22:02:18	内存使用	8.27 MiB

#include <bits/stdc++.h> 
using namespace std;

const int N = 100005, siz = 318;
#define gcd std::__gcd
#define bel(x) ((x - 1) / siz + 1)
#define mp std::make_pair
typedef long long LL;

int n, m, K, a[N], xp[N];
LL qry;

struct kuan {
    int val[320], L, R, len, Gcd, Xor[320], tag;
    set<pair<int, int>> s;

    void re() {
        Gcd = val[1];
        for (int i = 2; i <= len; ++i) {
            Gcd = gcd(Gcd, val[i]);
        }
    }

    void build(int l, int r) {
        L = l;
        R = r;
        len = r - l + 1;
        for (int i = l; i <= r; ++i) {
            val[i - l + 1] = a[i];
            Xor[i - l + 1] = xp[i];
            s.insert(mp(xp[i], i - l + 1));
        }
        re();
    }

    void modify(int pos, int dlt) {
        pos = pos - L + 1;
        for (int i = pos; i <= len; ++i) {
            s.erase(mp(Xor[i], i));
            s.insert(mp(Xor[i] ^= dlt, i));
        }
        val[pos] ^= dlt;
        re();
    }

    void get(int gg, int& ans) {
        for (int i = 1; i <= len; ++i) {
            gg = gcd(gg, val[i]);
            if ((LL)gg * (Xor[i] ^ tag) == qry) {
                ans = L + i - 1;
                return;
            }
        }
    }

    void find(int gg, int& ans) {
        if (qry % gg != 0) {
            return;
        }
        auto it = s.lower_bound(mp((qry / gg) ^ tag, 0));
        if (it == s.end() || (it->first ^ tag) != (qry / gg)) {
            return;
        }
        ans = it->second + L - 1;
    }
};

kuan b[320];

int main() {
	freopen("gcdxor.in", "r", stdin);
    freopen("gcdxor.out", "w", stdout);
    scanf("%d", &n);
    K = bel(n);
    for (int i = 0; i < n; ++i) {
        scanf("%d", a + i);
        xp[i] = xp[i - 1] ^ a[i];
    }
    for (int i = 1; i < K; ++i) {
        b[i].build((i - 1) * siz, i * siz - 1);
    }
    b[K].build((K - 1) * siz, n - 1);
    for (scanf("%d", &m); m--;) {
        char opt[12];
        scanf("%s", opt);
        if (*opt == 'M') {
            int pos, x;
            scanf("%d%d", &pos, &x);
            const int dlt = a[pos] ^ x;
            a[pos] = x;
            for (int i = bel(pos) + 1; i <= K; ++i) {
                b[i].tag ^= dlt;
            }
            b[bel(pos)].modify(pos, dlt);
        } else {
            scanf("%lld", &qry);
            int Gcd = 0, ans = -1;
            for (int i = 1; i <= K && ans == -1; ++i) {
                int lst = Gcd;
                Gcd = gcd(Gcd, b[i].Gcd);
                if (Gcd != lst) {
                    b[i].get(lst, ans);
                } else {
                    b[i].find(Gcd, ans);
                }
            }
            if (ans == -1) {
                puts("no");
            } else {
                printf("%d\n", ans);
            }
        }
    }
    return 0;
}