恰好可以学习一个知识叫做树上莫队，也就是求出这棵树的欧拉序然后在序上做莫队。注意 lca 不是 u 或 v 的话还需要特判一下。
然后就来到这个题：树上不带修，完全可以做莫队。
由于 n 和 q 都很大，所以莫队修改的时候就只有 $\mathcal{O}(1)$ 来搞，之前写了一发 $\mathcal{O}(\log n)$ 的完美 T 掉了（
设 cnt(c) 表示当前颜色 c 的出现次数，把颜色 1~n 分块来搞，处理每一块里面 cnt 为奇数的颜色个数，这样找到某一块个数大于 0 时再在这一块里面遍历一下就可以找到合法的颜色。
这样，询问的时候复杂度是 $\mathcal{O}(n(B+\frac{n}{B}))$（$B$ 是块大小），莫队的复杂度也是 $\mathcal{O}(n(B+\frac{n}{B}))$，那么总的时间复杂度也就是 $\mathcal{O}(n(B+\frac{n}{B}))$.
不过这个题也可以用 bitset 来乱搞。用一个 bitset 维护每一个颜色出现次数的奇偶性，不过 stl 里面的 bitset 不支持提取一段区间的操作，这个时候可以先预存 100 个 bitset，其中 1 是连续的一大段，比如 0000011， 0001100 这种。然后就是一坨一坨的这些 bitset 或起来，首尾单独处理一下，再和原 bitset 与一次，就可以提取相应段了，用 _Find_first() 函数可以较高效率求得第一个 1 的位置。这样，时间复杂度就是 $\mathcal{O}(\frac{nq}{w})$，勉强还是能跑过的。
不过官方题解做法更加神奇就是了......
#include <bits/stdc++.h>
#define ll long long
#define ls id << 1
#define rs id << 1 | 1
#define mem(array, value, size, type) memset(array, value, ((size) + 5) * sizeof(type))
#define memarray(array, value) memset(array, value, sizeof(array))
#define fillarray(array, value, begin, end) fill((array) + (begin), (array) + (end) + 1, value)
#define fillvector(v, value) fill((v).begin(), (v).end(), value)
#define pb(x) push_back(x)
#define st(x) (1LL << (x))
#define pii pair<int, int>
#define mp(a, b) make_pair((a), (b))
#define Flush fflush(stdout)
#define vecfirst (*vec.begin())
#define veclast (*vec.rbegin())
#define vecall(v) (v).begin(), (v).end()
#define vecupsort(v) (sort((v).begin(), (v).end()))
#define vecdownsort(v, type) (sort(vecall(v), greater<type>()))
#define veccmpsort(v, cmp) (sort(vecall(v), cmp))
using namespace std;
const int N = 300050;
const int inf = 0x3f3f3f3f;
const ll llinf = 0x3f3f3f3f3f3f3f3f;
const int mod = 998244353;
const int MOD = 1e9 + 7;
const double PI = acos(-1.0);
clock_t TIME__START, TIME__END;
void program_end()
{
#ifdef ONLINE
printf("\n\nTime used:
system("pause");
#endif
}
const int SIZ = 50000000 + 3;
char buf1[SIZ];
char *p1 = buf1, *p2 = buf1;
inline char readchar()
{
if (p1 == p2)
p1 = buf1, p2 = buf1 + fread(buf1, 1, SIZ, stdin);
return p1 == p2 ? EOF : *p1++;
}
inline int read()
{
int ret, c;
while ((c = readchar()) > '9' || c < '0')
;
ret = c - '0';
while ((c = readchar()) >= '0' && c <= '9')
ret = ret * 10 + c - '0';
return ret;
}
int n, Q, a[N];
int euler[N << 1], tim, in[N], out[N];
int belong[N << 1], B, bl[1050], br[1050];
struct querys
{
int id;
int u, v, l, r, lca;
int L, R;
querys() {}
querys(int id, int u, int v, int l, int r) : id(id), u(u), v(v), l(l), r(r) {}
bool operator<(const querys &rhs) const
{
return belong[L] != belong[rhs.L] ? L < rhs.L : ((belong[L] & 1) ? R < rhs.R : R > rhs.R);
}
} q[N];
const int MAXN = 300050, MAXM = 600050;
struct Edge
{
int v, nxt;
} e[MAXM];
int head[MAXN], ecnt;
void add_edge(int u, int v)
{
e[++ecnt] = {v, head[u]}, head[u] = ecnt;
e[++ecnt] = {u, head[v]}, head[v] = ecnt;
}
int dep[MAXN], fa[MAXN][20], dfn[MAXN], dfncnt, m;
void LCA_pre_dfs(int u, int f, int d)
{
dep[u] = d;
fa[u][0] = f;
dfn[u] = ++dfncnt;
euler[++tim] = u;
in[u] = tim;
for (int i = head[u]; i; i = e[i].nxt)
{
if (e[i].v != f)
LCA_pre_dfs(e[i].v, u, d + 1);
}
euler[++tim] = u;
out[u] = tim;
}
int ans[N];
void LCA_pre()
{
LCA_pre_dfs(1, 0, 1);
for (int j = 1; j <= 19; j++)
for (int i = 1; i <= n; i++)
fa[i][j] = fa[fa[i][j - 1]][j - 1];
}
inline int getlca(int u, int v)
{
if (dep[u] < dep[v])
swap(u, v);
int delta = dep[u] - dep[v];
for (int i = 19; i >= 0; i--)
if ((delta >> i) & 1)
u = fa[u][i];
for (int i = 19; i >= 0; i--)
if (fa[u][i] ^ fa[v][i])
{
u = fa[u][i];
v = fa[v][i];
}
if (u == v)
return u;
return fa[u][0];
}
int tt[1050];
inline void update(int &c, int val)
{
tt[belong[c]] += val;
}
int used[N], cnt[N];
inline void add(int &c)
{
if (cnt[a[c]] & 1)
update(a[c], -1);
cnt[a[c]]++;
if (cnt[a[c]] & 1)
update(a[c], 1);
}
inline void del(int &c)
{
if (cnt[a[c]] & 1)
update(a[c], -1);
cnt[a[c]]--;
if (cnt[a[c]] & 1)
update(a[c], 1);
}
inline void Add(int &c)
{
used[c] ? del(c) : add(c);
used[c] ^= 1;
}
inline void getans(const querys &nowq)
{
int lca = nowq.lca, l = nowq.l, r = nowq.r;
if (lca)
{
int c = lca;
if (cnt[a[c]] & 1)
update(a[c], -1);
cnt[a[c]]++;
if (cnt[a[c]] & 1)
update(a[c], 1);
}
int res = -1;
if (belong[l] == belong[r] || belong[l] == belong[r] - 1)
{
for (int i = l; i <= r; ++i)
if (cnt[i] & 1)
{
res = i;
break;
}
}
else
{
for (int i = l; belong[i] <= belong[l]; ++i)
{
if (cnt[i] & 1)
{
res = i;
break;
}
}
if (res == -1)
{
for (int i = r; belong[i] >= belong[r]; --i)
{
if (cnt[i] & 1)
{
res = i;
break;
}
}
}
if (res == -1)
{
for (int i = belong[l] + 1; i < belong[r]; ++i)
{
if (tt[i])
{
for (int j = bl[i]; j <= br[i]; ++j)
if (cnt[j] & 1)
{
res = j;
break;
}
break;
}
}
}
}
ans[nowq.id] = res;
if (lca)
{
int c = lca;
if (cnt[a[c]] & 1)
update(a[c], -1);
cnt[a[c]]--;
if (cnt[a[c]] & 1)
update(a[c], 1);
}
}
inline void solve()
{
memarray(ans, -1), memarray(bl, inf);
n = read(), Q = read();
for (int i = 1; i <= n; ++i)
a[i] = read();
for (int i = 1; i < n; ++i)
{
int x = read(), y = read();
add_edge(x, y);
}
LCA_pre();
for (int i = 1; i <= Q; ++i)
{
int u, v, l, r;
u = read(), v = read(), l = read(), r = read();
q[i] = (querys){i, u, v, l, r};
int _lca = getlca(u, v);
if (in[u] > in[v])
swap(u, v);
if (_lca == u || _lca == v)
q[i].L = in[u], q[i].R = in[v];
else
q[i].L = out[u], q[i].R = in[v], q[i].lca = _lca;
}
B = 2000;
for (int i = 1; i <= n * 2; ++i)
{
belong[i] = i / B + 1;
if (i <= n)
bl[belong[i]] = min(bl[belong[i]], i), br[belong[i]] = max(br[belong[i]], i);
}
sort(q + 1, q + Q + 1);
int L = 1, R = 0;
for (int i = 1; i <= Q; ++i)
{
while (L > q[i].L)
--L, Add(euler[L]);
while (R > q[i].R)
Add(euler[R]), --R;
while (R < q[i].R)
++R, Add(euler[R]);
while (L < q[i].L)
Add(euler[L]), ++L;
getans(q[i]);
}
for (int i = 1; i <= Q; ++i)
printf(
}
int main()
{
TIME__START = clock();
int Test = 1;
// scanf(
while (Test--)
{
solve();
// if (Test)
// putchar('\n');
}
TIME__END = clock();
program_end();
return 0;
}
Comments 1 条评论
大佬高考是有多失利才会来中南