自动搬运

查看原文

来自洛谷，原作者为

	yyyx_ 怎么还有条船不远万里。

搬运于2025-08-24 22:53:55，当前版本为作者最后更新于2025-06-09 12:44:17，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

题意

$q$ 次查询：

• 1 l r：令 $S_0$ 为 $[l,r]$ 的最小虹，$\forall u \in S_0$，将 $w_u$ 加 $1$。
• 2 l r u：求 $\left(\sum_{i=l}^r 19901991^{z_{\gcd(i,u)} w_i} \right) \bmod {20242024}$ 的值。

Solution

注意到 $19901991^2 \equiv 1 \pmod{20242024}$。

问题转变为求 $\sum_{i=l}^r [z_{\gcd(i,u)} \bmod 2 = 1 \wedge w_i \bmod 2 = 1]$。

令上述式子的值为 $V$，询问的区间为 $[L,R]$。容易得到答案为 $19901991\times V + R - L + 1 - V$，化简得 $19901990\times V + R - L + 1$。

模 $2$ 意义下的 $+1$ 等价于 $\operatorname{xor} 1$，这启发我们使用 bitset 维护。

考虑分块。把操作离线下来，对于修改区间为 $[L,R]$ 的 $1$ 操作：

• $L,R$ 不属于同一块：

  可以把 $[L,R]$ 拆成 $[L,p],[p + 1,R]$ 两个区间。令 $p$ 为某一块的右端点，把所有 $1$ 操作按 $p$ 排序。

  对于每一块，从它的右端点 $p'$ 遍历到 $1$，每次加入一个点。从这个点不断地跳父亲，经过的所有点都标记为 $1$，直到当前跳到的点已经被访问。令该过程的标记数组为 $S$。

  在加入点的过程中，所有点的公共祖先深度单调不降。我们维护祖先所在的点编号 $pos$，$T$ 表示祖先到树根简单路径的节点 bitset，令 $1$ 表示节点在该路径上，$0$ 反之。则每次加入点后让 $pos$ 一直跳父亲，将经过的点设为 $0$，直到跳到了新的公共祖先。

  S ^ T 的 bitset 集合即为 $[L,p]$ 的最小虹，把这个集合存下来。

  对于 $[p + 1,R]$ 的处理同理。

  某种实现会带来一个问题：左部分与右部分不相连。这个时候可以把左部分与右部分的 lca 和他们公共的 lca 挂在节点上，dfs 维护一个 bitset，到哪个点就处理一下 $S_i$ 即可。

  容易证明每个节点只会被访问一次，总复杂度 $O(n\sqrt n)$。

• $L,R$ 属于同一块：

  我们没有什么好方法去处理这种情况。题目保证了 $L,R$ 在 $[1,n]$ 中等概率随机，所以期望下 $L,R$ 属于同一块的次数为 $O(\sqrt n)$。

  类似第一种，对于 $[L,R]$ 每个点跳父亲，暴力 $O(n)$ 处理这种情况下的 bitset 即可。

  总复杂度 $O(n\sqrt n)$。

对于每个 $2$ 操作，将他们的 bitset 中的 $[L,R]$ 位全部置为 $1$，其他都置为 $0$。

把操作按原顺序拍回去。令 $S_i$ 是上面预处理的 bitset。令 bitset 类型的 $ans$ 初始全为 $0$。若为 $1$ 操作则令 $ans\gets ans \operatorname{xor} S_i$；若为 $2$ 操作则令 $S_i\gets S_i \operatorname{and} ans$。

对于 $z_i$，我们可以直接爆搜所有质数乘积组合。过程中注意要有 $vis$ 数组，不然复杂度会退化。维护一个 $T$ 表示第 $i$ 位上是奇数还是偶数。搜到 $u$ 直接将对应的询问 $S_i \gets S_i \operatorname{and} T$ 即可。

时间复杂度大约是 $O(n\sqrt n)$，据说是 $O(4\times 10^7)$。

总复杂度 $O(n\sqrt n + \frac{nq}{w})$。

输出时使用 bitset<N>().count() 统计即可。

我的代码真的很长，还是打的时候没带脑子了哎。

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

namespace Fread
{
    const int SIZE = 1 << 21;
    char buf[SIZE], *S, *T;
    inline char getchar()
    {
        if (S == T)
        {
            T = (S = buf) + fread(buf, 1, SIZE, stdin);
            if (S == T)
                return '\n';
        }
        return *S++;
    }
}
namespace Fwrite
{
    const int SIZE = 1 << 21;
    char buf[SIZE], *S = buf, *T = buf + SIZE;
    inline void flush()
    {
        fwrite(buf, 1, S - buf, stdout);
        S = buf;
    }
    inline void putchar(char c)
    {
        *S++ = c;
        if (S == T)
            flush();
    }
    struct POPOSSIBLE
    {
        ~POPOSSIBLE() { flush(); }
    } ztr;
}
#define getchar Fread::getchar
#define putchar Fwrite::putchar
namespace Fastio
{
    struct Reader
    {
        template <typename T>
        Reader &operator>>(T &x)
        {
            char c = getchar();
            T f = 1;
            while (c < '0' || c > '9')
            {
                if (c == '-')
                    f = -1;
                c = getchar();
            }
            x = 0;
            while (c >= '0' && c <= '9')
            {
                x = x * 10 + (c - '0');
                c = getchar();
            }
            x *= f;
            return *this;
        }
        Reader &operator>>(char &c)
        {
            c = getchar();
            while (c == ' ' || c == '\n')
                c = getchar();
            return *this;
        }
        Reader() {}
    } cin;
    struct Writer
    {
        template <typename T>
        Writer &operator<<(T x)
        {
            if (x == 0)
            {
                putchar('0');
                return *this;
            }
            if (x < 0)
            {
                putchar('-');
                x = -x;
            }
            static int sta[45];
            int top = 0;
            while (x)
            {
                sta[++top] = x % 10;
                x /= 10;
            }
            while (top)
            {
                putchar(sta[top] + '0');
                --top;
            }
            return *this;
        }
        Writer &operator<<(char c)
        {
            putchar(c);
            return *this;
        }
        Writer &operator<<(const char *str)
        {
            int cur = 0;
            while (str[cur])
                putchar(str[cur++]);
            return *this;
        }
        Writer() {}
    } cout;
}
#define endl '\n'
#define cin Fastio::cin
#define cout Fastio::cout
#define de(x) cerr << '[' << #x << ' ' << '=' << ' ' << x << ']' << ' '
#define ed() cerr << endl
const int N = 8e4 + 2;
const int B = 283;
typedef long long ll;
constexpr void dd(bitset<N> &x)
{
    for (int i = 0; i <= 10; i++)
        cerr << x[i];
}

int n, q, z[N];
vector<int> g[N];
bitset<N> b[N], S, T;
struct node1
{
    int l, r, id;
};
vector<node1> md;
struct node2
{
    int u, id;
};
vector<node2> qy;
int dfn[N], pos;
int f[N][18], fa[N];
void dfs0(int x)
{
    f[dfn[x] = ++pos][0] = fa[x];
    for (auto y : g[x])
    {
        if (y == fa[x])
            continue;
        fa[y] = x;
        dfs0(y);
    }
}
int Min(int x, int y)
{
    return dfn[x] < dfn[y] ? x : y;
}
void init()
{
    dfs0(1);
    for (int j = 1; j <= __lg(n); j++)
        for (int i = 1; i + (1 << j) - 1 <= n; i++)
            f[i][j] = Min(f[i][j - 1], f[i + (1 << j - 1)][j - 1]);
}
int lca(int x, int y)
{
    if (x == y)
        return x;
    x = dfn[x];
    y = dfn[y];
    if (x > y)
        swap(x, y);
    ++x;
    int t = __lg(y - x + 1);
    return Min(f[x][t], f[y - (1 << t) + 1][t]);
}
int blo[N];
void init2()
{
    int cnt = 0;
    for (int l = 1; l <= n; l += B)
    {
        ++cnt;
        int r = min(n, l + B - 1);
        for (int i = l; i <= r; i++)
            blo[i] = cnt;
    }
}
int st[N][18];
void init3()
{
    for (int i = 1; i <= n; i++)
        st[i][0] = i;
    for (int j = 1; j <= __lg(n); j++)
        for (int i = 1; i + (1 << j) - 1 <= n; i++)
            st[i][j] = lca(st[i][j - 1], st[i + (1 << j - 1)][j - 1]);
}
int totlca(int x, int y)
{
    int t = __lg(y - x + 1);
    return lca(st[x][t], st[y - (1 << t) + 1][t]);
}
int idx[N];
vector<pair<int, int>> tmp[B + 2];
vector<int> br0[N];
vector<int> prime;
vector<bool> isPrime;
void LinearSieves(const int n)
{
    isPrime.resize(n + 1, 1);
    isPrime[0] = isPrime[1] = 0;
    for (int i = 2; i <= n; i++)
    {
        if (isPrime[i])
        {
            prime.emplace_back(i);
        }
        for (int &x : prime)
        {
            if (i * x > n)
                break;
            isPrime[i * x] = 0;
            if (i % x == 0)
            {
                break;
            }
        }
    }
}
void dfs(int x)
{
    // de(x), dd(S), ed();
    T[x] = 1;
    for (auto &id : br0[x])
        b[id] &= S;
    for (auto &P : prime)
    {
        x *= P;
        if (x > n)
            break;
        if (!T[x])
        {
            vector<bool> trp(1, 0);
            for (int i = P; i <= n; i += P)
                trp.emplace_back(bool(S[i])), S[i] = z[__gcd(x, i)];
            dfs(x);
            for (int i = P; i <= n; i += P)
                S[i] = trp[i / P];
        }
        x /= P;
    }
}
int len[N];
const int mod = 20242024;
vector<int> b0[N], b1[N];
void dfs2(int x)
{
    for (auto id : b1[x])
        b[id] |= S;
    S[x] = 1;
    for (auto y : g[x])
    {
        if (y == fa[x])
            continue;
        dfs2(y);
    }
    S[x] = 0;
    for (auto id : b0[x])
        b[id] ^= S;
}

signed main()
{
    cin >> n >> q;
    for (int i = 1; i <= n; i++)
        cin >> z[i], z[i] &= 1;
    for (int i = 1, x, y; i < n; i++)
    {
        cin >> x >> y;
        g[x].emplace_back(y);
        g[y].emplace_back(x);
    }
    init();
    init2();
    for (int i = 1; i <= q; i++)
    {
        int op;
        cin >> op;
        if (op == 1)
        {
            int l, r;
            cin >> l >> r;
            md.emplace_back(node1{l, r, i});
            if (blo[l] != blo[r])
                tmp[blo[r / B * B]].emplace_back(l, i);
        }
        else
        {
            int l, r, u;
            cin >> l >> r >> u;
            len[i] = r - l + 1;
            if (len[i] >= B)
                idx[i] = r / B * B;
            b[i].set();
            b[i] >>= N - len[i];
            b[i] <<= l;
            qy.emplace_back(node2{u, i});
        }
    }
    int bcnt = (n + B - 1) / B;
    for (int i = 1; i <= bcnt; i++)
    {
        sort(tmp[i].begin(), tmp[i].end());
        // for (auto x : tmp[i])
        //     de(i), de(x.first), de(x.second), ed();
    }
    for (int l = 1; l <= n; l += B)
    {
        int r = min(n, l + B - 1);
        auto &h = tmp[blo[r]];
        int j = h.size() - 1;
        if (~j)
        {
            auto jmp = [&](int x)
            {
                while (x && !S[x])
                {
                    S[x] = 1;
                    x = fa[x];
                }
            };
            S.reset();
            jmp(r);
            T = S;
            T[r] = 0;
            int tag = r;
            auto clear = [&](int gl)
            {
                while (tag != gl)
                {
                    T[tag] = 0;
                    tag = fa[tag];
                }
                T[tag] = 0;
            };
            while (~j && h[j].first == r)
            {
                b[h[j].second] |= S ^ T;
                --j;
            }
            if (!~j)
                continue;
            for (int i = r - 1; i >= 1; i--)
            {
                jmp(i);
                clear(lca(tag, i));
                while (~j && h[j].first > i)
                    --j;
                while (~j && h[j].first == i)
                {
                    b[h[j].second] |= S ^ T;
                    --j;
                }
                if (!~j)
                    break;
            }
        }
    }
    // for (auto &[l, r, id] : md)
    //     dd(b[id]), ed();
    for (int i = 1; i <= bcnt; i++)
    {
        tmp[i].clear();
    }
    for (auto &[l, r, id] : md)
    {
        if (blo[l] != blo[r])
        {
            int R = r / B * B;
            if (R != r)
                tmp[blo[R + 1]].emplace_back(r, id);
        }
    }
    for (int i = 1; i <= bcnt; i++)
    {
        sort(tmp[i].begin(), tmp[i].end(), greater<pair<int, int>>());
        // for (auto x : tmp[i])
        //     de(i), de(x.first), de(x.second), ed();
    }
    for (int l = 1; l <= n; l += B)
    {
        int r = min(n, l + B - 1);
        auto &h = tmp[blo[r]];
        int j = h.size() - 1;
        if (~j)
        {
            auto jmp = [&](int x)
            {
                while (x && !S[x])
                {
                    S[x] = 1;
                    x = fa[x];
                }
            };
            S.reset();
            jmp(l);
            T = S;
            T[l] = 0;
            int tag = l;
            auto clear = [&](int gl)
            {
                while (tag != gl)
                {
                    T[tag] = 0;
                    tag = fa[tag];
                }
                T[tag] = 0;
            };
            while (~j && h[j].first == l)
            {
                b[h[j].second] |= S ^ T;
                --j;
            }
            if (!~j)
                continue;
            for (int i = l + 1; i <= n; i++)
            {
                jmp(i);
                clear(lca(tag, i));
                while (~j && h[j].first < i)
                    --j;
                while (~j && h[j].first == i)
                {
                    b[h[j].second] |= S ^ T;
                    --j;
                }
                if (!~j)
                    break;
            }
        }
    }
    init3();
    for (auto &[l, r, id] : md)
    {
        if (blo[l] == blo[r])
        {
            auto jmp = [&](int x)
            {
                while (x && !S[x])
                {
                    S[x] = 1;
                    x = fa[x];
                }
            };
            S.reset();
            jmp(l);
            T = S;
            T[l] = 0;
            int tag = l;
            auto clear = [&](int gl)
            {
                while (tag != gl)
                {
                    T[tag] = 0;
                    tag = fa[tag];
                }
                T[tag] = 0;
            };
            for (int i = l + 1; i <= r; i++)
            {
                jmp(i);
                clear(lca(tag, i));
            }
            b[id] |= S ^ T;
            // dd(b[id]), ed();
            // dd(S), ed();
            // dd(T), ed();
        }
        else
        {
            int R = r / B * B;
            if (R != r)
            {
                b1[totlca(l, R)].emplace_back(id);
                b1[totlca(R + 1, r)].emplace_back(id);
                b0[totlca(l, r)].emplace_back(id);
            }
        }
    }
    // for (auto &[l, r, id] : md)
    //     dd(b[id]), ed();
    S.reset();
    dfs2(1);
    auto op = md.begin();
    S.reset();
    for (auto &[u, id] : qy)
    {
        while (op != md.end() && (*op).id < id)
            S ^= b[(*op).id], ++op;
        b[id] &= S;
        br0[u].emplace_back(id);
    }
    LinearSieves(n);
    S.reset();
    T.reset();
    for (int i = 1; i <= n; i++)
        S[i] = z[1];
    for (auto &P : prime)
    {
        for (int i = P; i <= n; i += P)
            S[i] = z[P];
        dfs(P);
        for (int i = P; i <= n; i += P)
            S[i] = z[1];
    }
    for (auto &id : br0[1])
        b[id] &= S;
    for (auto &[u, id] : qy)
    {
        cout << (19901990ll * b[id].count() + len[id]) % mod << endl;
    }

    return 0;
}