首页 > 编程学习 > CF1083C Max Mex

CF1083C Max Mex

发布时间:2022/9/1 10:56:47

传送门


思路

对线段树的功能理解又加深了

假设我们枚举答案为 \(x\),那么要满足有一条链包含了 \(1\) ~ \(x-1\) 的数

我们考虑建立一棵线段树,下标为点权,区间记录的是 \([l,r]\) 是否存在一条链使得 \(l\) ~ \(r\) 都在链上,如果有,我们只需要记录链的两个端点即可

考虑如何合并两个区间:首先我们要学会怎么判断一个结点 \(z\) 是否在某条链 \((x,y)\) 上,假如满足 \((\text{LCA}(x,z)==z||\text{LCA}(y,z)==y)\&\&(\text{LCA}(w,z)==w)\),其中 \(w=\text{LCA}(x,y)\),那么 \(z\) 就是在链上的

合并两个区间时,我们只需要在这四个端点中枚举其中两个作为新链的端点,再判断另外两个是否在新链上即可,情况为 \(6\)

对于查询,由于我们要的链一定是从 \(1\) 到某个数,那么我们进行线段树二分,求前缀链,具体实现可以看代码的 query 函数部分

这里需要引入一种 \(O(n\log n)\) 预处理,\(O(1)\) 查询 \(\text{LCA}\) 的方法:

我们先记录树遍历的欧拉序,即进入某个结点时,记录这个结点;当从子结点返回到这个结点时,也再记录一次这个结点

我们令 \(in[u]\) 表示 \(u\) 第一次被记录的编号

对于两个结点 \(u,v\),我们只需要找到 \(in[u]\)\(in[v]\) 之间深度最小的节点,这个就是他们的 \(\text{LCA}\)

我们只需要用 ST表 来预处理深度最小的结点即可

这样我们就能做到 \(O((n+q)\log n)\)


代码

#include<iostream>
#include<fstream>
#include<algorithm>
#include<cmath>
#include<cstdlib>
#include<cstring>
#include<queue>
#include<map>
#include<set>
#include<bitset>
#define LL long long
#define FOR(i, x, y) for(int i = (x); i <= (y); i++)
#define ROF(i, x, y) for(int i = (x); i >= (y); i--)
#define PFOR(i, x) for(int i = he[x]; i; i = e[i].nxt)
template<typename T> inline void rd(T &x)
{
    T sign = 1, re = 0; char c = getchar();
    while(c < '0' || c > '9'){if(c == '-') sign = -1; c = getchar();}
    while('0' <= c && c <= '9'){re = re * 10 + (c - '0'); c = getchar();}
    x = sign * re;
}
int n, q, a[200005], id[200005];
struct Node
{
    int to, nxt;
}e[400005]; int he[200005];
inline void Edge_add(int u, int v)
{
    static int cnt = 0;
    e[++cnt] = (Node){v, he[u]};
    he[u] = cnt;
}
int in[200005], dep[200005], pcnt;
int len[400005];
int st1[400005][20], st2[400005][20]; // The longest is 18
void dfs(int now, int fa)
{
    in[now] = ++pcnt, st1[pcnt][0] = st2[pcnt][0] = now;
    PFOR(i, now)
    {
        int to = e[i].to;
        if(to == fa) continue;
        dep[to] = dep[now] + 1, dfs(to, now);
        ++pcnt, st1[pcnt][0] = st2[pcnt][0] = now;
    }
}
inline void Initst()
{
    int h = 1, cur = -1;
    FOR(i, 1, pcnt)
    {
        if(i == h) {cur++, h <<= 1;}
        len[i] = cur;
    }
    h = 1;
    FOR(j, 1, len[pcnt])
    {
        for(int i = 1; i + (h << 1) - 1 <= (pcnt); i++)
        {
            int pos = (dep[st1[i][j - 1]] < dep[st1[i + h][j - 1]]) ? st1[i][j - 1] : st1[i + h][j - 1];
            st1[i][j] = pos;
        }
        for(int i = (pcnt); i - (h << 1) + 1 >= 1; i--)
        {
            int pos = (dep[st2[i][j - 1]] < dep[st2[i - h][j - 1]]) ? st2[i][j - 1] : st2[i - h][j - 1];
            st2[i][j] = pos;
        }
        h <<= 1;
    }
}
inline int LCA(int x, int y)
{
    if(in[x] > in[y]) std::swap(x, y);
    int dis = len[in[y] - in[x] + 1];
    return (dep[st1[in[x]][dis]] < dep[st2[in[y]][dis]]) ? st1[in[x]][dis] : st2[in[y]][dis];
}
#define pii std::pair<int, int>
#define mp std::make_pair
pii p[800005];
#define ls (now << 1)
#define rs ((now << 1) | 1)
inline bool check(int x, int y, int z)
{
    int w = LCA(x, y);
    return (LCA(x, z) == z || LCA(y, z) == z) && LCA(w, z) == w;
}
inline pii combine(pii x, int y)
{
    if(x.first < 0 || y < 0) return mp(-1, -1);
    int u = x.first, v = x.second;
    if(check(u, v, y)) return x;
    if(check(u, y, v)) return mp(u, y);
    if(check(v, y, u)) return mp(v, y);
    return mp(-1, -1);
}
inline pii merge(pii x, pii y)
{
    if(x.first < 0 || y.first < 0) return mp(-1, -1);
    pii re = combine(x, y.first);
    if(re.first < 0) return mp(-1, -1);
    return combine(re, y.second);
}
void build(int now, int l, int r)
{
    if(l == r)
    {
        p[now] = mp(id[l], id[r]);
        return;
    }
    int mid = (l + r) >> 1;
    build(ls, l, mid), build(rs, mid + 1, r);
    p[now] = merge(p[ls], p[rs]);
}
void modify(int now, int l, int r, int to)
{
    if(l == r)
    {
        p[now] = mp(id[l], id[r]);
        return;
    }
    int mid = (l + r) >> 1;
    if(to <= mid) modify(ls, l, mid, to);
    else modify(rs, mid + 1, r, to);
    p[now] = merge(p[ls], p[rs]);
}
int query(int now, int l, int r, pii &pre)
{
    if(p[now].first >= 0)
    {
        if(pre.first < 0)
        {
            pre = p[now];
            return r + 1;
        }
        pii rp = merge(pre, p[now]);
        if(rp.first >= 0)
        {
            pre = rp;
            return r + 1;
        }
    }
    if(l == r) return l;
    int mid = (l + r) >> 1;
    int re = query(ls, l, mid, pre);
    if(re <= mid) return re;
    return query(rs, mid + 1, r, pre);
}
signed main()
{
#ifndef ONLINE_JUDGE
    freopen("test.in", "r", stdin);
    freopen("test.out", "w", stdout);
#endif
    rd(n);
    FOR(i, 1, n) rd(a[i]), a[i]++, id[a[i]] = i;
    FOR(i, 2, n)
    {
        int to;
        rd(to);
        Edge_add(i, to), Edge_add(to, i);
    }
    dep[1] = 1, dfs(1, 0);
    Initst();
    build(1, 1, n);
    rd(q);
    FOR(i, 1, q)
    {
        int ty; rd(ty);
        if(ty == 1)
        {
            int x, y;
            rd(x), rd(y);
            std::swap(id[a[x]], id[a[y]]); std::swap(a[x], a[y]);
            modify(1, 1, n, a[x]), modify(1, 1, n, a[y]);
        }
        else
        {
            pii rp = mp(-1, -1);
            printf("%d\n", query(1, 1, n, rp) - 1);
        }
    }
    return 0;
}
Copyright © 2010-2022 mfbz.cn 版权所有 |关于我们| 联系方式|豫ICP备15888888号