Codeforces Round #176 (Div. 1 + Div. 2)

A. IQ Test

• 模拟。

---

B. Pipeline

• 贪心。

---

C. Lucky Permutation

• 每4个数构成一个循环。
• 当n为偶数时，n=4k有解；当n为奇数时，n=4k+1有解。

---

D. Shifting

• 本质相当于每次把每段的首个数字移动到下段的首部。

---

E. Main Sequence

• 括号匹配。

---

D. Tourists

• 对于每个询问(q)来说，被墙的挡住的位置满足(l_ile xle r_i,t_ile q+x)，即(max{l_i,t_i-q}le x le r_i)。
• 当(l_i)为最大值时,(l_ige t_i - q)，即(qge t_i - li)，考虑到(q)是严格递增的，所以可以按照(t_i-l_i)对墙排序，小于等于(q)的贡献为(r_i-l_i)。这个贡献与(q)无关，所以直接求和即可。
• 当(t_i-q)为最大值时，这些墙体的贡献为(sum{r_i-(t_i-q)}=sum{r_i-t_i}+kq)。所以需要维护(r_i-ti)的值以及相应的墙的数量。
• 由于墙会出现重叠情况，所以需要按照时间顺序，将墙处理成不相交的状态。离散化的方法是：用(set)维护未被覆盖的小区间，均摊复杂度为(logn)。

---

E. Ladies' Shop

• 因为(1le a_i le m)，所以(p_j=a_i)，否则(p_j)无法用(sum{a_i})表示。
• 对于(a_k)来说，必然要存在(a_k=a_i+a_j,k>i,j)，否则会不满足条件2，剩下的就是用fft判断(a_k=a_i+a_j)这个等式是否成立。