p5688

Link_Cut_qwq · 2021-09-03 01:35:48 · 题解

介绍一种 dfs + 并查集的做法。

这是目前的最优解。复杂度为排序复杂度 O(n\log n)，其余部分 O(n)。

• 大致做法

我们找到距离每个出口最近的人。这个人离该出口最近不等于从该出口出，因为这个人可能在途中另外一个出口出了。于是我们搜索他俩之间的所有出口，看看有没有出口把那个人拦下。如果没有，那个人就可以放心地从该出口出了。

• 具体实现

维护两条链表，分别是按位置递减排序过后的逆时针走的人+出口和按位置递增排序后的顺时针走的人+出口，称为 L 链和 R 链。在排序过程中，我们让 type 作为第二关键字，id 作为第三关键字。我们需要让链表里同位置的出口始终在人的左侧且同位置的 id 小的人在 id 大的人的左侧（代码采用的是一个倒着扫一个正着扫的方法建链表）。

再维护两个并查集 L 集和 R 集，把 L 集定义为一些出口且任意两个出口之间没有逆时针走的人，R 集定义为一些出口且任意两个出口之间没有顺时针走的人。再维护每个 L 集合最靠顺时针的出口 vL 和每个 R 集合最靠逆时针的出口 vR。

任意一个点的顺时针侧最近的逆时针走的人就是这个点所在 L 集合的 vL 在 L 链表中右侧的位置，逆时针侧最近的顺时针走的人就是这个点所在 R 集合的 vR 在 R 链表中右侧位置（并查集就是为了干这事用的）。我们取这两个人中距离该出口最近的人作为搜索目标。

然后由距离该出口从远到近（也就是从该出口对应的 vL 或 vR 开始搜）的顺序搜索该出口与搜索目标之间的出口，这样确定一个人对应的出口只需要 O(2)，因为最多延伸两次就会出现该出口与最近的人之间没有别的出口的情况。

不能从近到远搜，因为这样确定一个人可能需要把所有出口都搜一遍，最坏需要 O(n)。

如果这个出口已经满了就标记一下，每次会取一个没有满的出口进函数，可以证明搜完以后要么这个出口满了要么没人了，因此不会有遗漏。

因为每次在达成目的后会退出，所以不会造成一个出口搜出去以后再次搜到这个出口的情况。

• 维护方法

只要一个出口满了或一个人确定了出口就把他们从 L 链表或 R 链表中删掉，这很容易办。

并查集的维护就繁琐一点了。若删掉的人在 L 链表或 R 链表中的前一个位置和后一个位置都是出口，那么将两个出口所在的 L 集合或 R 集合合并，并将新集合的 vL 或 vR 保留为后一个位置的集合的 vL 或 vR，代码实现方面可以直接将前一个位置的爹连到后一个位置的爹上。

如果删掉的出口是某个集合的 vL 或 vR，那么将该集合的 vL 或 vR 设为原本的 vL 或 vR 在 L 链表或 R 链表里左侧的位置。可以证明操作后的位置如果集合不为空一定是出口，若不是出口则这个集合为空，报废了，连的什么都无所谓。

• 复杂度

算法 O(n) + 排序 O(n\log n)

• 代码

#include <bits/stdc++.h>
#define N 1000010
using namespace std;

typedef long long ll;

struct Node
{
    ll data;
    int id;
    bool tp;
} bL[N], bR[N], b1[N], b2[N];

struct List
{
    ll to, la;
} tL[N], tR[N];

ll ans, a[N], w[N];
int n, m, l, fL[N], fR[N], s[N], vL[N], vR[N], cL, cR;
bool used[N], type;

int read ()
{
    int reat = 0, z = 1;
    char ch = getchar (); 
    while (ch < '0' || ch > '9')
        ch = getchar ();
    while (ch <= '9' && ch >= '0')
        reat = reat * 10 + ch - '0', ch = getchar ();
    return z * reat; 
}

bool cmp1 (Node x, Node y)
{
    if (x.data != y.data) return x.data < y.data;
    return x.id > y.id;
}
// 排序，方便建链表 
bool cmp2 (Node x, Node y)
{
    if (x.data != y.data) return x.data < y.data;
    return x.id < y.id;
}

ll c (ll x, ll y)   //计算距离 
{
    if (x - y < 0)
        return x + l - y;
    return x - y;
}

ll findL (int x) //常规Find 
{
    if (cL <= m) return 0;
    if (fL[x] == x) return x;
    fL[x] = findL (fL[x]);
    return fL[x];
}

ll findR (int x) //常规Find 
{
    if (cR <= m) return 0;
    if (fR[x] == x) return x;
    fR[x] = findR (fR[x]);
    return fR[x];
}

bool dfs (int x, int k)
{
    while (s[x])
    {
        //逆时针集合最靠左的出口和顺时针集合最靠右的出口 
        int x0 = vL[findL(x)], x1 = vR[findR(x)]; 
        //顺时针方向第一个逆时针人和逆时针方向第一个顺时针人 
        ll a0 = tL[x0].to, a1 = tR[x1].to;
        if (cL == m && cR == m) return 0;   //如果人走完了就结束  
        if (cL > m && (c (a[x], w[a0-m]) < c (w[a1-m], a[x]) || c (a[x], w[a0-m]) == c (w[a1-m], a[x]) && a0 < a1 || cR == m))
        {
            while (x0 != x && !dfs (x0, a0))
                x0 = tL[x0].la; //从远到近爆搜每个路径上的出口 
            if (x0 == x)    //这个人被保留下来 
            {
                s[x]--;
                cL--;   //逆时针人数减一 
                ans ^= (a0 - m) * x;
                tL[tL[a0].to].la = tL[a0].la;   //链表里删掉这个人 
                tL[tL[a0].la].to = tL[a0].to;
                if (tL[a0].to <= m) //把人两侧的两个出口集合合并 
                    fL[findL(tL[a0].la)] = findL(tL[a0].to);    
            }
            if (a0 == k) return true;   //达成目的return true 
        } else
        {
            while (x1 != x && !dfs (x1, a1))
                x1 = tR[x1].la;
            if (x1 == x)
            {
                s[x]--;
                cR--;
                ans ^= (a1 - m) * x;
                tR[tR[a1].to].la = tR[a1].la;
                tR[tR[a1].la].to = tR[a1].to;
                if (tR[a1].to <= m)
                    fR[findR(tR[a1].la)] = findR(tR[a1].to);
            }
            if (a1 == k) return true;
        }
    }
    used[x] = 1;    //标记一下 
    ll x0 = findL(x), x1 = findR(x);
    tL[tL[x].la].to = tL[x].to; //链表里删掉出口 
    tL[tL[x].to].la = tL[x].la;
    tR[tR[x].la].to = tR[x].to;
    tR[tR[x].to].la = tR[x].la;
    if (x == vL[x0]) vL[x0] = tL[x].la; //这个出口作为某逆时针集合最左侧点则向右移动一格
    if (x == vR[x1]) vR[x1] = tR[x].la; //这个出口作为某顺时针集合最右侧点则向左移动一格
    return false;   //未达成return false 
}

int main ()
{
    cin >> n >> m >> l;
    b1[1].id = b2[1].id = 1;
    for (int i = 2; i <= m; i++)
    {
        a[i] = read ();
    }
    for (int i = 1; i <= m; i++)
        s[i] = read ();
    for (int i = m + 1; i <= m + n; i++)
    {
        type = read ();
        if (!type)
            b1[++cL].data = read (), b1[cL].id = i, w[i-m] = b1[cL].data;
        else
            b2[++cR].data = read (), b2[cR].id = i, w[i-m] = b2[cR].data;
    }
    sort (b1 + 1, b1 + cL + 1, cmp1);
    sort (b2 + 1, b2 + cR + 1, cmp2);
    cL += m, cR += m;
    int r1 = 1, r2 = 1;
    for (int i = 1; i <= cL; i++)   //排序常数优化，时间紧可以不加
    {
        if (r1 <= m && a[r1] < b1[r2].data || r2 > cL - m)
            bL[i].data = a[r1], bL[i].id = r1, bL[i].tp = 1, r1++;
        else
            bL[i] = b1[r2], r2++;
    }
    r1 = r2 = 1;
    for (int i = 1; i <= cR; i++)
    {
        if (r1 <= m && (a[r1] < b2[r2].data || a[r1] == b2[r2].data) || r2 > cR - m)
            bR[i].data = a[r1], bR[i].id = r1, bR[i].tp = 1, r1++;
        else
            bR[i] = b2[r2], r2++;
    }
    //以下为建链表 
    for (int i = cL; i >= 1; i--)
    {
        tL[bL[i].id].to = bL[i-1].id;
        tL[bL[i].id].la = bL[i+1].id;
        if (bL[i+1].tp && bL[i].tp)
            fL[bL[i+1].id] = bL[i].id;
        fL[bL[i].id] = bL[i].id;
        vL[bL[i].id] = bL[i].id;
    }
    tL[bL[1].id].to = bL[cL].id;
    tL[bL[cL].id].la = bL[1].id;
    if (bL[1].tp && bL[cL].tp)
        fL[bL[1].id] = bL[cL].id;
    for (int i = 1; i <= cR; i++)
    {
        tR[bR[i].id].to = bR[i+1].id;
        tR[bR[i].id].la = bR[i-1].id;
        if (bR[i-1].tp && bR[i].tp)
            fR[bR[i-1].id] = bR[i].id;
        fR[bR[i].id] = bR[i].id;
        vR[bR[i].id] = bR[i].id;
    }
    tR[bR[cR].id].to = bR[1].id;
    tR[bR[1].id].la = bR[cR].id;
    if (bR[cR].tp && bR[1].tp)
        fR[bR[cR].id] = bR[1].id;
    for (int i = 1; i <= m; i++)
    {
        if (!used[i]) dfs (i, 0);
    }
    cout << ans << endl;
    return 0;
}

不开 o2 377ms，开 o2 242ms。代码大多是对称的，并查集也不算毒瘤。所以在结尾求个赞不过分吧。。