题解 P5688 【[CSP-SJX2019]散步】
前言：和同学刷联赛题，然后看到线段树做法好长（）。
为了避免繁琐的线段树，我们考虑换一种思考方式。
我们不考虑每一个人到终点的距离，而是考虑每个出口左边与右边离他最近的人。这样我们只要在这些出口中选取一个距离最短的人而并不用更新距离，所以可以用set来解决。
那么问题就变成了如何维护每个出口它的左边和右边离他最近的人。
- 1.初始化
对于每个方向的人和每个出口都建出一个链表，方便之后的删除操作。同时为了方便处理位置相同时的编号问题，我们可以在建链表时以编号为第二关键字进行排序。
之后先预处理出每一个出口左边与右边离他最近的人。这里以处理左边的人为例：
从任意的人开始，之后不断往左移动，直到下一个人跨过了一个出口，如果在同一个位置则从编号大的向编号小的连边。
最后看一下开始的人与结束的人之间有没有出口。
将距离和每个点的编号合起来存在set里，同时存储每个被选择的人与出口对应的关系，若出口的左边或者右边没有人对应，则将它的值设为0（后面有用）。
- 2.删除与加入
选择出距离最近的人后，就要对它对应的出口状态进行修改。
假如出口还能出人，则对出口所对应左边最近或右边最近的人进行修改
即先找到人所对应的出口，再将它连向这个人的前驱，将对应的值存进set里。
当然如果前驱已经有对应的出口了，那么就将它的值设为0.
如果出口满了，那么就要修改该出口下一个出口的状态，因为该出口所对应的人一定是在下一个出口所对应的人的后面，所以只有在对应关系为0的出口要将它与这个人的前驱建立关系，并加入set。
假如删除了出口则要将出口从链表中删除，同时将所选到的人从链表中删除。
最后出口所对应的关系没了就退出。
然后发现细节极多，实际长度和数据结构差不多（）。
#include <iostream>
#include <cstdio>
#include <set>
#include <algorithm>
#define int long long
using namespace std;
const int N = 2e5 + 10;
int n, m, l;
struct people
{
int ids, opt, b;
}p[N], zz[N], nn[N];
struct list
{
int l, r;
}ls[N];
int a[N], L[N], num1, num2, ss[N], bb[N];
bool pd(people i, people j)
{
return i.b < j.b || (i.b == j.b && i.ids > j.ids);
}
bool pd1(people i, people j)
{
return i.b < j.b || (i.b == j.b && i.ids < j.ids);
}
int sf[N];
set <pair<int, int> > s;
int dl[N], dr[N];
int _l[N], _r[N];
int ans;
int next[N], pre[N];
int ff[N];
void re(int to, pair<int, int> now)
{
int a1 = dl[to], a2 = dr[to];
if(ss[now.second] == 0)
a2 = ls[a2].l;
else
a1 = ls[a1].r;
if(dr[next[to]] == 0 && a2 && L[_r[a2]] <= 0)
{
dr[next[to]] = a2;
_r[a2] = next[to];
if(ff[a2] == 0 && next[to] != to)
if(a[next[to]] < bb[a2])
s.insert(make_pair(l - bb[a2] + a[next[to]], a2));
else
s.insert(make_pair(a[next[to]] - bb[a2], a2));
}
if(dl[pre[to]] == 0 && a1 && L[_l[a1]] <= 0)
{
dl[pre[to]] = a1;
_l[a1] = pre[to];
if(ff[a1] == 0 && next[to] != to)
if(a[pre[to]] > bb[a1])
s.insert(make_pair(l + bb[a1] - a[pre[to]], a1));
else
s.insert(make_pair(bb[a1] - a[pre[to]], a1));
}
ls[ls[now.second].l].r = ls[now.second].r;
ls[ls[now.second].r].l = ls[now.second].l;
pre[next[to]] = pre[to];
next[pre[to]] = next[to];
}
signed main()
{
freopen("walk.in","r",stdin);
freopen("walk.out","w",stdout);
scanf("%lld%lld%lld", &n, &m, &l);
for (int i = 2; i <= m; ++ i)
{
scanf("%lld", &a[i]);
}
for (int i = 1; i <= m; ++ i)
{
scanf("%lld", &L[i]);
pre[i] = (i - 2 + m) % m + 1;
next[i] = i % m + 1;
}
for (int i = 1; i <= n; ++ i)
{
scanf("%lld%lld", &p[i].opt, &p[i].b);
ss[i] = p[i].opt;
bb[i] = p[i].b;
p[i].ids = i;
}
sort(p + 1, p + 1 + n, pd);
for (int i = 1; i <= n; ++ i)
{
if(p[i].opt == 0)
{
nn[++ num1] = p[i];
}
else
{
zz[++ num2] = p[i];
}
}
sort(zz + 1, zz + 1 + num2, pd1);
for (int i = 1; i <= num1; ++ i)
{
ls[nn[i].ids].l = nn[i - 1].ids;
ls[nn[i].ids].r = nn[i + 1].ids;
}
ls[nn[1].ids].l = nn[num1].ids;
ls[nn[num1].ids].r = nn[1].ids;
for (int i = 1; i <= num2; ++ i)
{
ls[zz[i].ids].l = zz[i - 1].ids;
ls[zz[i].ids].r = zz[i + 1].ids;
}
ls[zz[1].ids].l = zz[num2].ids;
ls[zz[num2].ids].r = zz[1].ids;
int now = 1, S;
while(ss[p[now].ids] == 1 && now <= n) ++ now;
S = ls[p[now].ids].l;
int id = p[now].ids, qwq = 0;
if(bb[id] == 0)
{
while(bb[ls[id].r] <= a[1] && id != S)
id = ls[id].r;
dr[1] = id;
_r[id] = 1;
s.insert(make_pair(0, id));
qwq = 1;
}
int flag = 1;
for (int i = 2; i <= m; ++ i)
{
while(bb[ls[id].r] <= a[i]&& id != S)
id = ls[id].r, flag = 1;
if(flag == 1 && bb[id] <= a[i] && bb[id] != 0)
{
flag = 0;
dr[i] = id;
_r[id] = i;
s.insert(make_pair(a[i] - bb[id], id));
}
}
if(qwq == 0 && _r[S] == 0)
{
dr[1] = S;
_r[S] = 1;
s.insert(make_pair(l - bb[S], S));
}
sort(p + 1, p + 1 + n, pd1);
now = n;
while(ss[p[now].ids] == 0 && now > 0) -- now;
S = ls[p[now].ids].r;
id = p[now].ids;
flag = 1;
for (int i = m; i >= 2; -- i)
{
while(bb[ls[id].l] >= a[i] && id != S)
id = ls[id].l, flag = 1;
if(flag == 1 && bb[id] >= a[i] && bb[id] != 0)
{
dl[i] = id;
_l[id] = i;
s.insert(make_pair(bb[id] - a[i], id));
flag = 0;
}
}
if(_l[S] == 0)
{
dl[1] = S;
_l[S] = 1;
s.insert(make_pair(bb[S], S));
}
while(s.size())
{
pair<int, int> now = *s.begin();
s.erase(s.begin());
if(ff[now.second] || now.second == 0)
continue;
if(ss[now.second] == 0)
{
int to = _r[now.second];
int jl = 0;
if(a[to] < bb[now.second])
jl = l - bb[now.second] + a[to];
else
jl = a[to] - bb[now.second];
if(jl != now.first)continue;
-- L[to];
if(L[to] < 0)
{
_r[now.second] = 0;
continue;
}
if(ff[now.second] == 1)continue;
ff[now.second] = 1;
// printf("%d %d\n", now.second, to);
ans ^= now.second * to;
if(L[to] == 0)
{
re(to, now);
}
else
{
ls[ls[now.second].l].r = ls[now.second].r;
ls[ls[now.second].r].l = ls[now.second].l;
if(L[_r[ls[now.second].l]] > 0 || ff[ls[now.second].l] == 1)
{
dr[to] = 0;
}
else
{
if(a[to] < bb[ls[now.second].l])
s.insert(make_pair(l - bb[ls[now.second].l] + a[to], ls[now.second].l));
else
s.insert(make_pair(a[to] - bb[ls[now.second].l], ls[now.second].l));
dr[to] = ls[now.second].l;
_r[ls[now.second].l] = to;
}
}
}
else
{
int to = _l[now.second];
int jl = 0;
if(a[to] > bb[now.second])
jl = l + bb[now.second] - a[to];
else
jl = bb[now.second] - a[to];
if(jl != now.first)continue;
-- L[to];
if(L[to] < 0)
{
_l[now.second] = 0;
continue;
}
if(ff[now.second] == 1)continue;
ff[now.second] = 1;
// printf("%d %d\n", now.second, to);
ans ^= now.second * to;
if(L[to] == 0)
{
re(to, now);
}
else
{
ls[ls[now.second].l].r = ls[now.second].r;
ls[ls[now.second].r].l = ls[now.second].l;
if(L[_l[ls[now.second].r]] > 0 || ff[ls[now.second].r] == 1)
{
dl[to] = 0;
}
else
{
if(a[to] > bb[ls[now.second].r])
s.insert(make_pair(l + bb[ls[now.second].r] - a[to], ls[now.second].r));
else
s.insert(make_pair(bb[ls[now.second].r] - a[to], ls[now.second].r));
dl[to] = ls[now.second].r;
_l[ls[now.second].r] = to;
}
}
}
}
printf("%lld", ans);
}