LGP5688 [CSP-S-JX 2019] 散步 学习笔记
Luogu Link
前言
一题多解这一块。
题意简述
\(n\) 个人在公园内散步。公园可以看作一个环形，上有 \(m\) 个出口，按逆时针顺序记作 \(1\) 号口到 \(m\) 号口。
环总长 \(V\) 米。记 \(a_i\) 为 \(i\) 号出口从 \(1\) 号口按逆时针走到的距离，其中 \(a_1=0\)。每个出口有一个限制 \(l_i\) 表示最多有 \(l_i\) 个人能从 \(i\) 号出口离开。
每个人有一个编号，有一个初始方向（顺时针或逆时针，用 \(0\) 和 \(1\) 表示），有一个初始位置 \(b_i\)，表示其在离 \(1\) 号口沿逆时针走 \(b_i\) 距离处。所有人同时出发，如果经过一个还能过人的出口则从中离开。特别地，若一个出口迎来了高于当前剩余容量的人数，则编号小的优先从中离开。
问每个人最终从哪个出口离开？为了减少输出量，设 \(i\) 号人从 \(k_i\) 号口离开，你只需要输出 \(\bigoplus_{i=1}^n i\times k_i\)。特别地，如果一个人 \(i\) 最后无法离开（这合理吗），则 \(k_i=0\)。
\(n,m\le 2\times 10^5\)，\(a_i,b_i\le V\le 10^9\)。
做法解析
显然有 \(O(nL)\) 的暴力：你一秒一秒地考虑情况，对于每秒，更新每个人的位置，看他们是不是在某个能出人的门上，如果能就放他走。如果走了一圈都出不去那肯定就是出不去了，因此只用考虑 \(V\) 秒。
你发现这样太低效了：没有人出去的时刻是不需要考虑的。我们只应该考虑有人离开的时刻。于是想到用堆来维护每个人离下一个出口的距离。由于出口容量有限，所以对于那些编号相对大的人来说，“下一个出口”可能会变化，这就需要修改之后重新入堆。由于对于顺时针方向和逆时针方向走的人来说，同一个出口消失后的“下一个出口”不同，所以要把沿两个方向走的人分开处理。当然，你一眼就能看出来，这个算法最坏情况可以被直接卡到 \(O(n^2\log n)\)。这要怎么办呢？
第一种思路，遇事不决，线段树。显然在一个方向上“下一个出口”遭到改变的必然是一段连续的人，再加上“取堆顶”也等价于“求距离的全局最小值”，所以你直接换上线段树来维护就行了。对于线段树，需要支持线段树二分、整体改、维护区间最小值。当然你也需要一个链表用来找“某个出口消失后下一个是谁”。此做法详情参考这位巨佬的题解。细节很多，所以他说“这题写出来可以显著提升代码能力”是有道理的。时间复杂度 \(O(n\log n)\)。
第二种思路，如果你不想再写一坨线段树，也不是不行。因为实际上，我们维护的很多“下一个出口”是没有意义的。想象这样一个场景：如果有 \(a_i<b_i<b_j<a_j\)，且 \(i,j\) 二人都沿逆时针前进，在 \(b_j\) 离开之前，我们有考虑 \(b_i\) 的必要吗？没有！这启示我们同时考虑出口与人的相邻关系，也就是把所有出口和人都存在一个链表里面（注意链接的方向是人到出口，编号大的到编号小的），并且只把那些 nxt 为某个出口的人放在堆里。这样，一个人从出口离开只会影响到他在两个方向上的下一个人，由此时间复杂度便可控了，\(O(n\log n)\) 完美。
第三种思路。是的这题还有一种做法。我们不去从人的角度考虑下一个出口在哪，反倒从出口的角度考虑下一个人在哪。我们不断地对于一个未满的出口尝试 \(\texttt{DFS}\) 离它最近的人。当然，那个人可能会被这个出口和他之间的其他出口拦下来，要考虑这一点。实现上，仍然为两个方向维护两个同思路二的链表。再对于每个方向各维护一个并查集，并查集里每一颗子树都代表“一群与该子树内出口间没有任何行人的出口们”，然后最后反正可以以每个人 \(O(1)\) 的代价做完整个问题。此做法代码参考高赞题解……有点抽象，所以为什么要这么做呢。那个人说去掉排序 \(O(n)\)。鉴定为写线性做法写的。嗯，兑，英改式。
代码实现
这里写的是综合来说最好写好想的思路二。
#include <bits/stdc++.h>
using namespace std;
using namespace obasic;
const int MaxN=4e5+5;
int N,M,V,X,Y,E[MaxN],lim[MaxN],S[MaxN];
vector<pii> P[2];pii B[MaxN<<1];
struct anob{int x,y,z;friend bool operator>(const anob &a,const anob &b){return a.z==b.z?a.x>b.x:a.z>b.z;}
};
priority_queue<anob,vector<anob>,greater<anob> > pq;
struct LinkedList{pii lst[MaxN<<1],nxt[MaxN<<1];void link(int u,int v,int w,int k){u=abs(u),v=abs(v);if(k)swap(u,v);nxt[u]={v,w},lst[v]={u,w};if(u<=N&&v>N)pq.push({u,v,w});}void erase(int u){auto [ln,lw]=lst[u];auto [nn,nw]=nxt[u];link(ln,nn,lw+nw,0);}
}L[2];
int ans[MaxN];lolo fans;
int main(){readis(N,M,V);for(int i=2;i<=M;i++)readi(E[i]);for(int i=1;i<=M;i++)readi(lim[i]);for(int i=1;i<=N;i++)readis(S[i],X),P[S[i]].push_back({X,i});auto build=[&](int dir){int ccnt=0;for(int i=1;i<=M;i++)B[++ccnt]={E[i],(N+i)*(dir?-1:1)};for(auto [dis,id] : P[dir])B[++ccnt]={dis,id*(dir?1:-1)};sort(B+1,B+ccnt+1);for(int i=1;i<=ccnt;i++){auto [du,u]=B[i];auto [dv,v]=B[i%ccnt+1];if(i==ccnt)dv=V;L[dir].link(u,v,abs(dv-du),dir);}};build(0),build(1);int ecnt=M;while(ecnt&&pq.size()){auto [u,ce,dis]=pq.top();pq.pop();int te=ce-N;if(ans[u]||!lim[te])continue;ans[u]=te,lim[te]--;if(!lim[te])L[0].erase(ce),L[1].erase(ce),ecnt--;L[S[u]].erase(u);}for(int i=1;i<=N;i++)fans^=1ll*i*ans[i];writil(fans);return 0;
}