发现了一个水思路

思路：

每次染色的边界是a,b,用book数组标记a,b的边界值为i

这时不难发现性质：$ans_i$就是book数组后i个数的最大值与前i个数的最大值的最小值（有点绕）

所以可以预处理前缀后缀最大值

时间复杂度只有O(m+3∗n)

我不知道这对不对，但愿这是对的，反正ac了

AC Code（只有短短28行）

#include <iostream>
#include <cmath>
using namespace std;
typedef long long ll;
const ll INF = 1e6 + 10;
ll book[INF], maxn1[INF], maxn2[INF];
int main() {
    ll n,m,p,q;
    cin>>n>>m>>p>>q;
    ll a,b;
    for (int i=1; i<=m; i++) {
        a=min(((i*q+p)%n)+1,((i*p+q)%n)+1);
        b=max(((i*q+p)%n)+1, ((i*p+q)%n)+1);
        book[a]=i;
        book[b]=i;
    }
    ll ans1,ans2;
    for (int i=1; i<=n; i++)
        maxn1[i]=max(maxn1[i-1],book[i]);
    for (int i=n;i>=1;i--)
        maxn2[i]=max(maxn2[i+1],book[i]);
    for (int i=1;i<=n;i++) {
        ans1=-0x7fffffff;
        ans2=-0x7fffffff;
        cout<<min(maxn1[i], maxn2[i])<<endl;
    }
    return 0;
}