bzoj 4028: [HEOI2015]公约数数列

题意：

设计一个数据结构. 给定一个正整数数列 $a_0, a_1, …, a_{n - 1}$，你需要支持以下两种操作：

1. MODIFY id x: 将 $a_{id}$ 修改为 $x$.
2. QUERY x: 求最小的整数 p (0 <= p < n)，使得 $gcd(a_0, a_1, …, a_p) * XOR(a_0, a_1, …, a_p) = x$. 其中 $XOR(a_0, a_1, …, a_p)$ 代表 $a_0, a_1, …, a_p$ 的异或和，$gcd$表示最大公约数。

题解：

分块
每个块记录一下块内的gcd和异或和，并用map记录一下每个异或值出现的位置，然后修改的话就直接暴力重构整个块，查询就从前往后找，如果当前块的gcd是它前面的gcd的倍数，那么块内的所有的gcd都是前面的gcd，在map里面找就好了；否则就暴力在块里面找。因为gcd最多只会变化$log$次，所以复杂度是有保证的。

#include <cstdio>
#include <cstring>
#include <algorithm>
#include <map>
#include <cmath>
using namespace std;

int n, blocksize, m, blocknum;
long long a[100010];
struct block
{
    int sz;
    long long d, x;
    map<long long, int> mp;
} b[350];

long long gcd(long long x, long long y) { return y == 0 ? x : gcd(y, x % y); }
void build(int l, int r)
{
    int id = l / blocksize;
    b[id].sz = r - l;
    b[id].mp.clear();
    for (int i = l; i < r; i++)
    {
        int j = i - l;
        if (j == 0) b[id].d = b[id].x = a[i];
        else
        {
            b[id].d = gcd(b[id].d, a[i]);
            b[id].x = b[id].x ^ a[i];
        }
        if (!b[id].mp.count(b[id].x)) b[id].mp[b[id].x] = i;
    }
}
void wk(long long x)
{
    long long nowd = 0, nowx = 0;
    for (int i = 0; i < blocknum; i++)
    {
        if (nowd == gcd(nowd, b[i].d))
        {
            if (x % nowd == 0 && b[i].mp.count(x / nowd ^ nowx))
            {
                printf("%d\n", b[i].mp[x / nowd ^ nowx]);
                return;
            }
            nowx ^= b[i].x;
        }
        else
        {
            for (int j = 0; j < b[i].sz; j++)
            {
                nowd = gcd(nowd, a[j + i * blocksize]);
                nowx ^= a[j + i * blocksize];
                // printf("*%lld %lld\n", nowd, nowx);
                if (nowd * nowx == x)
                {
                    printf("%d\n", j + i * blocksize);
                    return;
                }
            }
        }
    }
    puts("no");
}/*
void print()
{
    for (int i = 0; i < blocknum; i++)
    {
        for (int j = 0; j < b[i].sz; j++)
            printf("%lld %lld\n", b[i].g[j], b[i].x[j]);
        printf("%lld\n", b[i].d);
        for (auto x : b[i].mp)
            printf("%lld %d\n", x.first, x.second);
        puts("");
    }
}*/
int main()
{
    scanf("%d", &n);
    blocksize = sqrt(n);
    // blocksize = 1;
    for (int i = 0; i < n; i++)
        scanf("%lld", &a[i]);
    for (int i = 0; i < n; i += blocksize)
    {
        build(i, min(i + blocksize, n));
    }
    blocknum = (n - 1) / blocksize + 1;
    // print();
    scanf("%d", &m);
    while (m--)
    {
        char s[10];
        scanf("%s", s);
        if (s[0] == 'M')
        {
            int id;
            long long x;
            scanf("%d%lld", &id, &x);
            a[id] = x;
            int l = id / blocksize * blocksize;
            build(l, min(l + blocksize, n));
        }
        else
        {
            long long x;
            scanf("%lld", &x);
            wk(x);
        }
        // print();
    }
}