还是离线把操作倒过来做，于是每个馒头只要看最后一种颜色就好了
如果一个馒头已经有颜色了，就把它并到右边的馒头的集合里去
1 /************************************************************** 2 Problem: 2054 3 User: rausen 4 Language: C++ 5 Result: Accepted 6 Time:3268 ms 7 Memory:39776 kb 8 ****************************************************************/ 9 10 #include <cstdio> 11 #include <algorithm> 12 13 using namespace std; 14 const int N = 1e6 + 5; 15 16 int c[N], fa[N]; 17 int n, m, p, q; 18 19 int find_f(int x) { 20 return x == fa[x] ? x : fa[x] = find_f(fa[x]); 21 } 22 23 int main() { 24 int i, j, x, y; 25 scanf("%d%d%d%d", &n, &m, &p, &q); 26 for (i = 1; i <= n + 1; ++i) fa[i] = i; 27 for (i = m; i; --i) { 28 x = (1ll * i * p + q) % n + 1, y = (1ll * i * q + p) % n + 1; 29 if (x > y) swap(x, y); 30 for (j = find_f(x); j <= y; j = find_f(j)) 31 c[j] = i, fa[j] = j + 1; 32 } 33 for (i = 1; i <= n; ++i) 34 printf("%d ", c[i]); 35 return 0; 36 }