F - Takahashi on Grid
用线段树上的节点维护一下 \((l,r,c)\)，如果 \(c\) 为 \(-1\)：\(l,r\) 表示这一段区间内 \([l,r]\) 的交。
如果 \(c\ne -1\)，\(l,r\) 表示这一段第一次上下界相等的时候的位置为 \(l\)，合并后走出来的位置为 \(r\)，然后转折的步数为 \(c\)。然后这玩意可以合并，每一次查询相当于首尾插入两个元素 \((sy,sy,0)\)，\((ty,ty,0)\)，然后并一下就行了。然后这一题似乎不用修改，所以我们可以用 \(ST\) 表预处理，然后 \(O(\log n)\) 倍增求答案。怕写挂还是写线段树吧。
friend node operator + (const node &a, const node &b) {
node res;
if (~a.p) {
if (~b.p) {
res.l = a.l, res.r = b.r;
res.p = a.p + b.p + abs(a.r - b.l);
} else {
res.l = a.l, res.p = a.p;
if (a.r < b.l)
res.r = b.l, res.p += b.l - a.r;
else if (a.r > b.r)
res.r = b.r, res.p += a.r - b.r;
else
res.r = a.r;
}
} else {
if (~b.p) {
res.r = b.r, res.p = b.p;
if (a.l > b.l)
res.l = a.l, res.p += a.l - b.l;
else if (a.r < b.l)
res.l = a.r, res.p += b.l - a.r;
else
res.l = b.l;
} else {
if (a.r < b.l)
res = node(a.r, b.l, b.l - a.r);
else if (a.l > b.r)
res = node(a.l, b.r, a.l - b.r);
else
res = node(max(a.l, b.l), min(a.r, b.r));
}
}
return res;
}
\(10\) 种情况分讨的信息合并。。
G - AtCoder Office
我们考虑将询问去重，离线下来，将询问度数求出来，然后每次连边将度数大的挂在度数小的上面，假设 \(B = \sqrt q\)，那么对于度数小于等于 \(B\) 的连出去的边至多 \(B\) 条，对于度数大于 \(B\) 的点，相连的点也一定大于 \(B\)，那么去重后的点数也至多 \(B\) 个。
然后我们用 \(sum_i\) 表示 \(t_i\) 时间之前，\(p_i\) 这个人的在办公室的时间。
然后从前往后扫 \((t_i,p_i)\)，每次记录一下每个人是否在办公室，以及上一次操作这个人的时间，然后遍历出边（询问），和扫描线一样的去做差分即可。
整体复杂度：\(O(m\sqrt q)\)。