C

给定一个排列,和一些数对,表示这两个数不能放在同一区间
问满足要求的区间有多少个

滑窗

我们记录每个位置上左边第一个与之不能在一起的数的位置

左端点依此移动一个位置
移动右端点使滑窗内始终保持存在不满足关系的数对
统计不满足关系的区间(每次加 n+1-r)

复杂度 $O(n)$

D

求n个区间每个区间分别包含多少区间

树状数组

先按将所有端点排序
遇到右端点则得到对应区间的答案
然后更新对应左端点之前的区间的答案

复杂度 $O(nlogn)$

F

长m的环上有n只蚂蚁,给定他们的初始运动方向
每个时间单位移动一格,两只蚂蚁相撞后就立即调转方向
求最后所有蚂蚁的位置

智商题 QAQ

大白书上Ants On Line的进化版
我们可以认为蚂蚁是幽灵…
相撞就是互换编号,然后穿过
这样可以求出最后n只蚂蚁的相对位置
难点就在确定其中一只蚂蚁的位置

题解做法比较复杂而且看不懂…下面是一个智商压制的做法…

设某一时刻设编号i的蚂蚁为x>=0的第一只
若此时有一只蚂蚁从x=m-1走到了x=0,那么此时第一只变为i-1
若此时有一只蚂蚁从x=0走到了x=m-1,那么此时第一只变为i+1

这样我们就能确定第一只蚂蚁的编号了…

复杂度 $O(nlogn + n)$