题解 CF1525C 【Robot Collisions】
SSerxhs
2021-05-17 01:07:41
首先按位置奇偶分类，只有奇偶性相同才会相撞。
不考虑反弹的情况下，如果记 $\texttt R$ 为 $\texttt ($，$\texttt L$ 为 $\texttt )$，那么碰撞情况等于括号匹配情况，用栈维护即可。
考虑从 $x=0$ 反弹，那么如果当前出现了一个失配的右括号，它不可能与前面的括号匹配，等价于坐标变为 $-x$ 并向右走。因此可以翻转括号并改变坐标，入栈。
考虑从 $x=m$ 反弹，显然是进行完所有括号匹配后剩下的 $\texttt ($ 有一部分反弹，且反弹的恰好为剩下的一半。那么同样坐标变为 $2m-x$ 再翻转括号即可。
```cpp
struct Q
{
int u,v,w;//坐标，是否为 L，原下标
bool operator<(const Q &o) const {return u<o.u;}
};
void cal()
{
sort(a+1,a+n+1);tp=0;
for (i=1;i<=n;i++) if (a[i].v)
{
if (!tp)
{
a[i].u=-a[i].u;a[i].v=0;
st[++tp]=a[i];
}
else
{
ans[a[i].w]=ans[st[tp].w]=a[i].u-st[tp].u>>1;
--tp;
}
}
else
{
st[++tp]=a[i];
}
if (tp<=1) return;
if (tp&1) {for (i=1;i<tp;i++) st[i]=st[i+1];--tp;}
for (i=2;i<=tp;i+=2) st[i].u=2*m-st[i].u;
for (i=1;i<=tp;i+=2) ans[st[i].w]=ans[st[i+1].w]=st[i+1].u-st[i].u>>1;
}
```