分析
① 区间合并
② 并查集,并查集图解转自:彩色铅笔
将所有同一个区间内的点都合并到一个点上
③ 线段树
将同一个区间内的点都统一标记
$Example$:
①用对区间的覆盖次数来算数组的可行构造方式:$Acwing4412.$构造数组
②$Acwing3115$.疯狂的馒头
可以发现馒头最终的颜色只和最后一次染色有关,如果按照顺序染色模拟,那么肯定$T$飞了,可以考虑倒着染色,因为每次染完一个区间,它的颜色就确定了
$Code1$-$O(m)$
并查集,每从后往前染色一个区间,那么就将这个区间内的所有点都合并到区间右端点的下一个点上(这里其实是右端点的父节点,但是因为会自动路径压缩,所以可以直接$pl=pl+1$),相当于将这个已经被染色的区间都挂到这个点上,不会再被重复染色
#include<bits/stdc++.h>
using namespace std;
const int N = 1e6+10;
int p[N], color[N];
int n, m, _p, q;
int find(int x)
{
if (x != p[x]) p[x] = find(p[x]);
return p[x];
}
int main()
{
scanf("%d%d%d%d", &n, &m, &_p, &q);
for (int i = 1; i <= n + 1; i ++) p[i] = i;
for (int i = m; i >= 1; i --)
{
int l = (i * _p + q) % n + 1, r = (i * q + _p) % n + 1;
if (l > r) swap(l, r);
int pl = find(l); // 找到实际可以染色的左端点
while (pl <= r)
{
color[pl] = i;
p[pl] = pl + 1; // 将当前点合并到右边点的点上
pl = find(pl);
}
}
for (int i = 1; i <= n; i ++) printf("%d\n", color[i]);
return 0;
}
$code2$-$O(mlogn)$
线段树标记已经被染色的点,如果被染色了就直接$return$
#include<bits/stdc++.h>
using namespace std;
const int N = 1e6+10;
int n, m, p, q;
struct node
{
int l, r, v;
}tr[N << 2];
void pushup(int u)
{
if (tr[u << 1].v && tr[u << 1 | 1].v) tr[u].v = true;
}
void build(int u, int l, int r)
{
tr[u] = {l, r, 0};
if (l == r) return;
int mid = l + r >> 1;
build(u << 1, l, mid), build(u << 1 | 1, mid + 1, r);
}
void modify(int u, int l, int r, int v)
{
if (tr[u].v) return;
if (tr[u].l == tr[u].r) tr[u].v = v; // 注意modify的时候继续递归使用tr[u].l、tr[u].r
else
{
int mid = tr[u].l + tr[u].r >> 1;
if (l <= mid) modify(u << 1, l, r, v);
if (r > mid) modify(u << 1 | 1, l, r, v);
pushup(u);
}
}
void print(int u)
{
if (tr[u].l == tr[u].r) printf("%d\n", tr[u].v);
else print(u << 1), print(u << 1 | 1);
}
int main()
{
scanf("%d%d%d%d", &n, &m, &p, &q);
build(1, 1, n);
for (int i = m; i >= 1; i --)
{
int l = (i * p + q) % n + 1, r = (i * q + p) % n + 1;
if (l > r) swap(l, r);
modify(1, l, r, i); // 将区间染色
}
print(1);
return 0;
}