一种很新的区间染色
题目大意
有 \(n\) 个数初始都为 \(0\) ,有 \(m\) 次操作,第 \(i\) 次将 \((i \times p + q) \bmod n + 1\) 与 \((i \times q + p) \bmod n + 1\) 之间数都改为 \(i\) ,问 \(m\) 次操作后每个数分别是多少。
其中 \(1 \le n \le 10^6 , 1 \le m \le 10^7 , 1 \le m \times q + p , m \times p + q \le 2 \times 10^9\) 。
分析
首先不难想到 倒叙枚举数字 \(i\) ,这样就可以保证修改数字时 只修改数字 \(0\) 。
可是这样枚举并修改的时间复杂度是 \(O(n \times m)\) 的,明显无法通过本题。
所以我们需要一种算法来实现 区间跳跃 ,换句话说就是实现 维护每个数字左边(右边)第一个为 \(0\) 的数的位置 。
那么我们就可以想到使用 并查集 来维护这个值,然后进行修改操作就可以了。这样的时间复杂度就是 \(O(mlogn)\) 了。
跑不过暴力
代码
#include<bits/stdc++.h>
#define ll long long
#define ma 2000010
using namespace std;
//---------------------------------
ll read() {
ll x = 0, f = 1;
char ch = getchar();
while (!isdigit(ch)) {
if (ch == '-') f = -1;
ch = getchar();
}
while (isdigit(ch)) {
x = x * 10 + ch - '0';
ch = getchar();
}
return x * f;
}
//---------------------------------
ll n, m, p, q;
ll fa[ma];
ll get_fa(ll x) {
if (fa[x] == x) return x;
return fa[x] = get_fa(fa[x]);
}
ll col[ma];
//---------------------------------
int main() {
n = read(), m = read(), p = read(), q = read();
for (ll i = 1;i <= n;i++) fa[i] = i;
for (ll i = m;i >= 1;i--) {
ll l = (i * p + q) % n + 1, r = (i * q + p) % n + 1;
if (l > r) swap(l, r);
for (ll j = r;j >= l;j = get_fa(j)) {
ll t = get_fa(j);
if (t == j) {
col[t] = i;
fa[t] = get_fa(t - 1);// 维护每个数字左第一个为 0 的数的位置
}
}
}
for (ll i = 1;i <= n;i++) cout << col[i] << endl;
return 0;
}
为什么维护右边位置就会T呢?