题解：P5688 [CSP-S2019 江西] 散步

· · 题解

这一题其实不算太难，码量也不大。

一个 O(nm) 的做法是每一轮都寻找离任一出口最近的人，并且将他删掉，同时将他离开的门耐久度 -1，如果耐久度到了 0 就把这个门也删掉。至多 n 轮之后就不能再删除人了。容易发现暴力重构是 O(n+m) 的，所以可以用环状双向链表优化，这样删掉一个人或门变为 O(1) 的。

具体来讲，我们可以将所有门和逆时针的所有人排好序放在一个链表里，将所有门和顺时针的所有人排好序放在另一个链表里。每一轮都找到这两个链表中距离任一门最近的人中编号最小的那个，在对应连表里删掉这个人，如果门的耐久度降为 0，再在两个链表里均删掉这个门。

现在的瓶颈就在于如何快速地求出距离任一门最近的人。我们可以在建造两个链表时用优先队列存储在链表中下一个元素就是门的所有人。每次删除一个人或者一个门我们就考虑一下有没有让一个人的下一个元素变为一个新的门，如果有，加入优先队列即可。

注意到建造链表时优先队列中一共最多 n 个元素，每次删除也至多让一个人进队，每一轮至多删除 3 次，所以优先队列的进队次数不超过 4n，出队次数也不超过 4n，所以时间复杂度是 O(n\log n)。

代码仅 1.4kb。

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int _=4e5+5,inf=2e9;
ll s;
int n,m,L,a[_],b[_],d[_],e[_],i,z;
struct nb{
    int x,y,z;
    bool operator <(const nb v)const{return x==v.x?y>v.y:x>v.x;}//这是为了让大根堆距离小的和编号小的在根
}o,w;
struct lst{
    int l[_],r[_],t;//l 存储上一个元素，r 存储下一个元素，t 存储顺逆时针
    vector<nb>p;//x 存储从 0 开始逆时针的距离，y 存储门的编号或 m+人的编号，z 存储顺逆时针
    priority_queue<nb>q;//x 存储和下一个门的距离，y 存储 m+人的编号，z 存储顺逆时针
    int dis(int x){//求出第 x-m 个人距离他下一个门的距离
        z=a[r[x]]-d[x-m];
        if(t)z=-z;
        if(z<0)z+=L;
        return z;
    }
    void build(int ot){//建立环形双向链表
        t=ot;
        for(i=1;i<=m;i++)p.push_back({a[i],i,0});
        sort(p.begin(),p.end(),[&](nb u,nb v){return u.x==v.x?u.y>v.y:(u.x<v.x)^t;});//将人和门按照顺序排好
        p.push_back(p[0]);
        for(i=0;i<p.size()-1;i++){
            r[p[i].y]=p[i+1].y;l[p[i+1].y]=p[i].y;
            if(p[i].y>m&&p[i+1].y<=m)q.push({dis(p[i].y),p[i].y,t});
        }
    }
    void del(int x){//删除一个人或者一个门
        l[r[x]]=l[x];r[l[x]]=r[x];
        if(l[x]>m&&r[x]<=m)q.push({dis(l[x]),l[x],t});
    }
    nb find(){//寻找离任一门最近的人
        while(q.size()&&(e[(w=q.top()).y-m]||r[w.y]>m||w.x!=dis(w.y)))q.pop();//看一下这个人是否已经出门或者这个门已经被删除
        return q.size()?w:(nb){inf,0,0};
    }
}P[2];
int main(){
    ios::sync_with_stdio(0);
    cin.tie(0);cout.tie(0);
    cin>>n>>m>>L;
    for(i=2;i<=m;i++)cin>>a[i];
    for(i=1;i<=m;i++)cin>>b[i];
    for(i=1;i<=n;i++)cin>>z>>d[i],P[z].p.push_back({d[i],m+i,1});
    P[0].build(0);P[1].build(1);
    while((o=max(P[0].find(),P[1].find())).x!=inf){//o 就是离任一门最近的人中编号最小的，之所以用 max 是因为重载了运算符
        e[o.y-m]=P[o.z].r[o.y];P[o.z].del(o.y);//标记人对应的门并删除这个人
        if(!--b[e[o.y-m]])P[0].del(e[o.y-m]),P[1].del(e[o.y-m]);//减门的耐久，可能要删除门
    }
    for(i=1;i<=n;i++)s^=1ll*i*e[i];//求答案，要开 long long
    cout<<s<<'\n';
    return 0;
}