题解：P10016 [集训队互测 2023] 虹
yyyx_
·
·
题解
题意
- `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()` 统计即可。
我的代码真的很长，还是打的时候没带脑子了哎。
```cpp
#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;
}
```