D1T1 - P10217 [省选联考 2024] 季风

约定：令 \(a_i,b_i\) 代替原来的 \(x_i,y_i\)，避免变量重名。

显然地，考虑按 \(m\bmod n\) 的值分类，那么每一类都相当于若干个整段 \(+\) 一段前缀。

假设加上的是 \([1,i]\) 前缀，选了 \(m'\) 个整段，那么 \(a\) 的和可以表示为\(m'\times suma_n+suma_i\)，\(b\) 同理。现在考虑如何对于一个 \(m'\) check，注意到 \(a',b'\) 是实数，于是不难猜测，有解当且仅当：

注：\(m'n+i\) 是实际的 \(m\)。

于是做一点转化，令 \(x\to x-suma_i,y\to y-sumb_i\)，那么不难发现此时绝对值内的 \(suma_i,sumb_i\) 消失了。于是只需要分四段大力分讨即可。

注意到答案实际上相当于维护 \(\le 3\) 个形如 \(ax\le b\) 的不等式的解集。这个随便做就行，我赛时写繁了，用了一个 pair<int,int> 和 array<int,3> 存储最终的解集（可以直接维护左右端点，比较好写），同时细节也很多，比如我就挂了 \(60\text{pts}\)。

复杂度 \(O(n)\)，可以通过。

Code