P5688 [CSP-SJX2019]散步

· · 题解

看到AC区清一色的线段树……

这里介绍一种堆+链表的做法。

基本思路是差不多的（可以参考其它题解），每次找到距离他可到出口最近的人，删除这个人，更新答案和出口。

关键就在于怎么更新一段区间的人到下一个可达出口的距离，我们可以发现，只需要关注每一个人的下一个可达出口的位置就可以了，因为人到出口的距离是固定的。

刚开始，把人分成顺时针走和逆时针走两组，再按照位于哪两个相邻出口之间分组，这可以用排序+指针扫描一遍解决。

对于每一组，按人到下一个可达出口的距离从小到大、从头到尾串成一个链表，那么用一个堆维护每一个链表表头最小值，每次取最小值删除后就将链表中下一个位置加入堆。

那么，就只剩下删除出口了。首先，也是把出口用链表串起来，删除直接在链表上删除。可以发现，每一次删除，都相当于把两个相邻的组合并， 然后把链表合并并维护到新的出口的距离的相对顺序。

设新的出口还是原来出口的组为A，新的出口变为A组原来出口的组为B，那么B组中每一个人到新的出口的距离都大于A组中每一个人到出口的距离，所以只要把B组的链表表头直接接到A组表尾就可以保证相对距离顺序不变了。

然后，就没有然后了……

时间复杂度O(nlogn)，但是常数小，而且比线段树好写（然而代码4k），很轻松就跑到了最优解……

Upd：修改了代码中一些错误（感谢@Owen_codeisking%%%）

代码如下：

#include<bits/stdc++.h>
using namespace std;
#define res register int
#define ll long long
//#define cccgift
#define lowbit(x) ((x)&-(x))
#define rep(i,l,r) for(res i=l,_r=r;i<=_r;++i)
#define per(i,r,l) for(res i=r,_l=l;i>=_l;--i)
#define mkp make_pair
#define pb push_back
#define mem0(a) memset(a,0,sizeof(a))
#define mem0n(a,n) memset(a,0,(n)*sizeof(a[0]))
#define iter(x,v) for(res v,_p=head[x];v=ver[_p],_p;_p=nxt[_p])
#ifdef cccgift //by lqh
#define SHOW(x) cerr<<#x"="<<(x)<<endl
#else
#define SHOW(x) 0
#endif
#define getchar()(ip1==ip2&&(ip2=(ip1=ibuf)+fread(ibuf,1,1<<21,stdin),ip1==ip2)?EOF:*ip1++)
char ibuf[1<<21],*ip1=ibuf,*ip2=ibuf;
template<typename T>
inline void read(T &x)
{
    static char ch;bool f=1;
    for(x=0,ch=getchar();!isdigit(ch);ch=getchar()) if(ch=='-') f=0;
    for(;isdigit(ch);x=(x<<1)+(x<<3)+(ch^48),ch=getchar());x=f?x:-x;
}
template<typename T>
void print(T x)
{
    if (x<0) x=-x,putchar('-');
    if (x>9) print(x/10);
    putchar(x%10+48);
}
template<typename T>
inline void print(T x,char ap) {print(x);if (ap) putchar(ap);}
template<typename T>
inline void chkmax(T &x,const T &y) {x=x<y?y:x;}
template<typename T>
inline void chkmin(T &x,const T &y) {x=x<y?x:y;}
struct person{
    int x,id;
    person() {}
    person(int x,int id):x(x),id(id) {}
    bool operator <(const person &b)const {return x<b.x||(x==b.x&&id>b.id);}
} b[400010],c[400010];
struct node{
    int op,id,peo,peid,val; //op:方向，id:所属组，peo:人在组中的编号，peid:人的编号，val:人到下一个可达出口的距离。
    node() {}
    node(int op,int id,int peo,int peid,int val):op(op),id(id),peo(peo),peid(peid),val(val) {}
    bool operator <(const node &b)const {return val>b.val||(val==b.val&&peid>b.peid);}
};
priority_queue<node> q; //堆
int n,m,L,x,y,a[200010],cnt[200010],len1,len2,nxt[2][600010],pre[2][600010],nxt1[200010],pre1[200010];
ll tot;
inline void ins(int op,int id,int x) { //加入表头
    int now=nxt[op][id];
    pre[op][now]=x,nxt[op][x]=now,pre[op][x]=id,nxt[op][id]=x;
}
inline void del(int op,int x) {nxt[op][pre[op][x]]=nxt[op][x],pre[op][nxt[op][x]]=pre[op][x];}
inline int getdis(int x,int y) { //两点之间在环上的距离
    if(x<=y) return y-x;
    return L-x+y;
}
inline void hebing(int op,int x,int y) {
    int nowl=nxt[op][x+n],nowr=pre[op][n+m+x],now=pre[op][n+m+y]; //把nowl到nowr这一段插到y的链表表尾
    if(nowl==n+m+x) return;
    if(now==n+y) q.push(node(op,y,nowl,(op?c[nowl].id:b[nowl].id),getdis((op?c[nowl].x:b[nowl].x),(op?(L-a[y]):a[y])))); //如果插入y的堆中后nowl变成表头了，也要加入堆中。
    nxt[op][x+n]=n+m+x,pre[op][n+m+x]=x+n;
    pre[op][n+m+y]=nowr,nxt[op][nowr]=n+m+y;
    nxt[op][now]=nowl,pre[op][nowl]=now;
}
int main()
{
    read(n),read(m),read(L),a[1]=0;
    rep(i,2,m) read(a[i]);
    rep(i,1,m) read(cnt[i]);
    rep(i,1,n) {
        read(x),read(y);
        if(!x) b[++len1]=person(y?y:L,i);
        else c[++len2]=person(L-y,i); //b表示逆时针的人，c表示顺时针的人。
    }
    sort(b+1,b+1+len1),sort(c+1,c+1+len2);
    rep(i,1,m) nxt1[i]=i%m+1,pre1[i]=i-1;pre1[1]=m; //维护出口的链表
    rep(i,1,m) nxt[0][i+n]=nxt[1][i+n]=n+m+i,pre[0][n+m+i]=pre[1][n+m+i]=i+n; //这里维护了表头(n+1~n+m)和表尾(n+m+1~n+m+m)
    int p=1;
    rep(i,1,len1) {
        while(p<=m&&b[i].x>a[p]) ++p;
        if(p>m) ins(0,n+1,i);else ins(0,n+p,i);
    }
    p=m;
    rep(i,1,len2) {
        while(p&&c[i].x>L-a[p]) --p;
        ins(1,n+p,i);
    } //指针扫描
    rep(i,1,m) {
        int now1=nxt[0][n+i],now2=nxt[1][n+i];
        if(now1!=n+m+i) q.push(node(0,i,now1,b[now1].id,getdis(b[now1].x,a[i])));
        if(now2!=n+m+i) q.push(node(1,i,now2,c[now2].id,getdis(c[now2].x,L-a[i])));
    }
    int cntp=n,cntc=m;
    while(cntc&&cntp) {
        node now=q.top();
        while(nxt[now.op][n+now.id]==n+m+now.id) q.pop(),now=q.top();q.pop(); //懒惰删除，因为被合并之后的组不再有独立的最小值，需要在堆中删除。
        int op=now.op,id=n+now.id;
        --cntp,--cnt[now.id],del(op,now.peo);
        int h=nxt[op][id];
        if(h!=n+m+now.id) q.push(node(op,now.id,h,(op?c[h].id:b[h].id),getdis((op?c[h].x:b[h].x),(op?(L-a[now.id]):a[now.id]))));
        tot^=(ll)now.peid*now.id;
        if(!cnt[now.id]) { //删除出口
            id-=n;
            if(id!=nxt1[id]) hebing(0,id,nxt1[id]),hebing(1,id,pre1[id]);
            --cntc,nxt1[pre1[id]]=nxt1[id],pre1[nxt1[id]]=pre1[id];
        }
    }
    print(tot,'\n');
    return 0;
}