[Codeforces Round #700(Div.1)] 1479D – Odd Mineral Resource

发布于 2021-02-09  166 次阅读


恰好可以学习一个知识叫做树上莫队,也就是求出这棵树的欧拉序然后在序上做莫队。注意 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;
}