Give you a tree with \(n\) nodes and point weights, \(m\) queries, each query for the number of chain colors.
Force online.
\(1\leq n \leq 4\times 10^4,1\leq m\leq 10^5\).
sol
First, if you don't force online, you can use the tree instead.
But there are more forced online, it is easy to think of a preprocessing problem.
A better way to query the number of chain colors is to use bitset, which builds a BitSet for the range, and the answer is the number of \(1\) in the bitset.
The problem now is how to combine bitset s on a path.
Remember to discretize.
Fa I
Consider tree blocking.
Consider a simple tree-splitting technique: sprinkling trees.
Simply put, set a threshold value \(S\), select no more than \(\frac{n}{S}\) points on the tree as key points, satisfying that each key point is no more than \(S\) from its nearest ancestor key point.
Specifically, each time you select a non-critical point with the largest current depth, if its \(1\sim S\) ancestor is not a critical point, mark its \(S\) ancestor as a critical point.
Since at least \(S\) points will not be marked for each key point marked in the above method, the number of key points is correct.
When you think about it carefully, it is easy to see that each key point is not farther than the closest ancestor key point to it, and that the condition is also met.
After scattering the key points, record the bitsets between the two key points, find the bitsets of the two adjacent key points with (\mathcal O(S)\), and process the bitsets between them. The total time complexity of the preprocessing is \(\mathcal O(\frac{n^2}{S}+\frac{n^3}{wS^2})\.
Then consider asking, at which point the path being asked is split into two blocks and one block, block violence, and the bitset of the block is intersected with a total time complexity of \(\mathcal O(mS+\frac{nm}{w})\).
Taking \(S=\sqrt n\), the total time complexity is \(\mathcal O((n+m)\sqrt n+\frac{n^2+n m}{w})\, which is acceptable.
\(\text{1.88s / 20.14MB / 4.15KB C++14 (GCC 9) O2}\).
#include <cstdio>
#include <bitset>
#include <algorithm>
#define re register
namespace Fread
{
const int SIZE = 1 << 23;
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 << 23;
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 NTR
{
~NTR()
{
flush();
}
} ztr;
}
#ifdef ONLINE_JUDGE
#define getchar Fread::getchar
#define putchar Fwrite::putchar
#endif
inline int read()
{
re int x = 0, f = 1;
re char c = getchar();
while (c < '0' || c > '9')
{
if (c == '-')
f = -1;
c = getchar();
}
while (c >= '0' && c <= '9')
{
x = x * 10 + c - '0';
c = getchar();
}
return x * f;
}
inline void write(re int x)
{
if (x < 0)
{
putchar('-');
x = -x;
}
if (x > 9)
write(x / 10);
putchar(x % 10 + '0');
}
inline void swap(re int &x, re int &y)
{
x ^= y ^= x ^= y;
}
const int _ = 4e4 + 7;
std::bitset<_> bt[42][42], nw;
int n, m, B, arr[_], a[_], fa[_], dep[_], mxd[_], FF[_], siz[_], tp[_], hson[_];
int id[_], cnt, head[_], tot, ans, sta[_], top, gg[_];
struct edge
{
int to, nxt;
} e[_ << 1];
void dfs1(re int now, re int D)
{
siz[now] = 1;
dep[now] = D;
mxd[now] = dep[now];
for (re int i = head[now]; i; i = e[i].nxt)
{
re int v = e[i].to;
if (!dep[v])
{
fa[v] = now;
dfs1(v, D + 1);
siz[now] += siz[v];
if (mxd[v] > mxd[now])
mxd[now] = mxd[v];
if (siz[hson[now]] < siz[v])
hson[now] = v;
}
}
if (mxd[now] - dep[now] >= 1000)
id[now] = ++tot, mxd[now] = dep[now];
}
void dfs2(re int now)
{
for (re int i = head[now]; i; i = e[i].nxt)
{
re int v = e[i].to;
if (dep[v] > dep[now])
{
if (id[v])
{
int ip = id[sta[top]], in = id[v];
for (int x = v; x != sta[top]; x = fa[x])
bt[ip][in].set(a[x]);
nw = bt[ip][in];
for (int i = 1; i < top; ++i)
{
std::bitset<_> &bs = bt[id[sta[i]]][in];
bs = bt[id[sta[i]]][ip];
bs |= nw;
}
FF[v] = sta[top], gg[v] = gg[sta[top]] + 1;
sta[++top] = v;
}
dfs2(v);
if (id[v])
--top;
}
}
}
void dfs3(re int now, re int tf)
{
tp[now] = tf;
if (hson[now])
dfs3(hson[now], tf);
for (re int i = head[now]; i; i = e[i].nxt)
{
re int v = e[i].to;
if (!tp[v])
dfs3(v, v);
}
}
inline int LCA(re int x, re int y)
{
while (tp[x] != tp[y])
{
if (dep[tp[x]] < dep[tp[y]])
swap(x, y);
x = fa[tp[x]];
}
return dep[x] < dep[y] ? x : y;
}
signed main()
{
n = read(), m = read();
for (re int i = 1; i <= n; ++i)
arr[i] = a[i] = read();
std::sort(arr + 1, arr + 1 + n);
arr[0] = std::unique(arr + 1, arr + 1 + n) - arr - 1;
for (re int i = 1; i <= n; ++i)
a[i] = std::lower_bound(arr + 1, arr + 1 + arr[0], a[i]) - arr;
for (re int i = 1, u, v; i < n; ++i)
{
u = read(), v = read();
e[++cnt] = (edge){v, head[u]}, head[u] = cnt;
e[++cnt] = (edge){u, head[v]}, head[v] = cnt;
}
dfs1(1, 1);
if (!id[1])
id[1] = ++tot;
sta[top = 1] = gg[1] = 1;
dfs2(1);
dfs3(1, 1);
while (m--)
{
int u = read() ^ ans, v = read();
nw.reset();
int l = LCA(u, v);
while (u != l && !id[u])
nw.set(a[u]), u = fa[u];
while (v != l && !id[v])
nw.set(a[v]), v = fa[v];
if (u != l)
{
int pre = u;
while (dep[FF[pre]] >= dep[l])
pre = FF[pre];
if (pre != u)
nw |= bt[id[pre]][id[u]];
while (pre != l)
nw.set(a[pre]), pre = fa[pre];
}
if (v != l)
{
int pre = v;
while (dep[FF[pre]] >= dep[l])
pre = FF[pre];
if (pre != v)
nw |= bt[id[pre]][id[v]];
while (pre != l)
nw.set(a[pre]), pre = fa[pre];
}
nw.set(a[l]);
write(ans = nw.count()), putchar('\n');
}
return 0;
}
Fa II
Consider splitting the light and heavy chains, and when asked, combine bitset s of several heavy chains along the path.
Since the dfn order of the points on the heavy chain is continuous, sequence blocking is sufficient.
For each query, the contribution of the heavy chain can be calculated by dividing the heavy chain into blocks.
The time complexity is (\mathcal O(\frac{n^2}{w}+m\log n(\sqrt{n}+\frac{n}{w}))\).
\(\text{1.05s / 18.14MB / 3.47KB C++14 (GCC 9) O2}\).
#include <cstdio>
#include <bitset>
#include <algorithm>
#define re register
namespace Fread
{
const int SIZE = 1 << 23;
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 << 23;
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 NTR
{
~NTR()
{
flush();
}
} ztr;
}
#ifdef ONLINE_JUDGE
#define getchar Fread::getchar
#define putchar Fwrite::putchar
#endif
inline int read()
{
re int x = 0, f = 1;
re char c = getchar();
while (c < '0' || c > '9')
{
if (c == '-')
f = -1;
c = getchar();
}
while (c >= '0' && c <= '9')
{
x = x * 10 + c - '0';
c = getchar();
}
return x * f;
}
inline void write(int x)
{
if (x < 0)
{
putchar('-');
x = -x;
}
if (x > 9)
write(x / 10);
putchar(x % 10 + '0');
}
const int _ = 4e4 + 7, W = 4e4 + 7, B = 1e3;
std::bitset<W> f[42][42], nw;
int n, m, cnt_node, ans, tot, a[_], arr[_], fa[_], dep[_], siz[_], hson[_], top[_], dfn[_], b[_], bel[_], L[_], R[_], head[_], to[_ << 1], nxt[_ << 1];
inline void swap(re int &x, re int &y)
{
x ^= y ^= x ^= y;
}
inline void add(re int u, re int v)
{
to[++tot] = v;
nxt[tot] = head[u];
head[u] = tot;
}
void dfs1(re int u, re int D)
{
dep[u] = D, siz[u] = 1;
for (re int i = head[u]; i; i = nxt[i])
{
re int v = to[i];
if (siz[v])
continue;
fa[v] = u;
dfs1(v, D + 1);
siz[u] += siz[v];
if (siz[hson[u]] < siz[v])
hson[u] = v;
}
}
void dfs2(re int u, re int tf)
{
top[u] = tf, dfn[u] = ++cnt_node, a[cnt_node] = b[u];
if (!hson[u])
return;
dfs2(hson[u], tf);
for (re int i = head[u]; i; i = nxt[i])
{
re int v = to[i];
if (top[v])
continue;
dfs2(v, v);
}
}
inline void pre()
{
for (re int i = 1; i <= n; ++i)
{
bel[i] = (i - 1) / B + 1;
f[bel[i]][bel[i]].set(a[i]);
}
for (re int i = 1; i <= bel[n]; ++i)
L[i] = R[i - 1] + 1, R[i] = i * B;
R[bel[n]] = n;
for (re int i = 1; i < bel[n]; ++i)
for (re int j = i + 1; j <= bel[n]; ++j)
f[i][j] = f[i][j - 1] | f[j][j];
}
inline void Query_on_block(re int l, re int r)
{
if (bel[l] == bel[r])
{
for (re int i = l; i <= r; ++i)
nw.set(a[i]);
return;
}
nw |= f[bel[l] + 1][bel[r] - 1];
for (re int i = l; i <= R[bel[l]]; ++i)
nw.set(a[i]);
for (re int i = L[bel[r]]; i <= r; ++i)
nw.set(a[i]);
}
inline void Query_on_tree(re int u, re int v)
{
while (top[u] != top[v])
{
if (dep[top[u]] < dep[top[v]])
swap(u, v);
Query_on_block(dfn[top[u]], dfn[u]);
u = fa[top[u]];
}
if (dep[u] > dep[v])
swap(u, v);
Query_on_block(dfn[u], dfn[v]);
}
signed main()
{
n = read(), m = read();
for (re int i = 1; i <= n; ++i)
arr[i] = b[i] = read();
std::sort(arr + 1, arr + 1 + n);
arr[0] = std::unique(arr + 1, arr + 1 + n) - arr - 1;
for (re int i = 1; i <= n; ++i)
b[i] = std::lower_bound(arr + 1, arr + 1 + arr[0], b[i]) - arr;
re int u, v;
for (re int i = 1; i < n; ++i)
{
u = read(), v = read();
add(u, v), add(v, u);
}
dfs1(1, 1), dfs2(1, 1);
pre();
while (m--)
{
nw.reset();
u = read() ^ ans, v = read();
Query_on_tree(u, v);
write(ans = nw.count()), putchar('\n');
}
}