摘要:倒序处理跳过无用区间

luogu2391白雪皑皑

题面

题目分析

因为只用询问最后一次,所以直接倒序处理即可,让一个位置覆盖后直接跳过.

因为跳过的是一个区间,所以在每个点上记录跳到哪里即可.

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
#include "iostream"
#include "cstdlib"
#include "cstdio"
#include "cstring"
#include "cmath"
#include "cctype"
#include "ctime"
#include "iomanip"
#include "algorithm"
#include "set"
#include "queue"
#include "map"
#include "stack"
#include "deque"
#include "vector"
#define R register
#define INF 0x3f3f3f3f
#define debug(x) printf("debug:%lld\n",x)
#define debugi(x) printf("debug:%d\n",x)
#define debugf(x) printf("debug:%llf\n",x)
#define endl putchar('\n')
typedef int lxl;
const lxl big=1000010,large=10000010;
lxl n,m,p,q,sum,top;
lxl link[big],color[big];
struct _Modify
{
lxl l,r;
}mod[large];
inline lxl read()
{
char c(getchar());
lxl f(1),x(0);
for(;!isdigit(c);(c=='-')&&(f=-1),c=getchar());
for(;isdigit(c);x=(x<<1)+(x<<3)+(c^48),c=getchar());
return f*x;
}
lxl find(lxl x){return x==link[x]?x:link[x]=find(link[x]);}
int main(void)
{
sum=n=read(),m=read();
p=read(),q=read();
// for(R int i(1);i<=n+1;++i)link[i]=i;
for(R int i(1);i<=m;++i)
{
lxl l=(i*p+q)%n+1,r=(i*q+p)%n+1;
// lxl l=read(),r=read();
if(l>r)std::swap(l,r);
mod[i]=(_Modify){l,r};
// debug(l),debug(r),endl;
}
while(sum&&m)
{
lxl nl=mod[m].l,nr=mod[m].r,nc=m--;
for(R int i(nl);i<=nr;++i)
if(!color[i])color[i]=nc,link[i]=nr,--sum;
else i=link[i];
}
for(R int i(1);i<=n;++i)printf("%d\n",color[i]);
return 0;
}