noi.ac 307 洛谷 2391 白雪皑皑(flower) 题解

发表于 | 阅读次数：
本文字数： 1.1k 字 | 阅读时长 ≈ 5 分钟

题意简述

老铁们，虽然不是同一个题目，但是是一样的题意，今天我来给大家打一个暴力模拟线段树，奥利给

一个长度为 $n$ 的序列，初始全 $0$ 。有 $m$ 次修改操作。给你两个常数 $p,q$，第 $i$ 次操作会把第 $(i\times p+q)\mod n+1$ 和 $(i\times q+p)\mod n+1$ 之间的所有数赋值为 $i$。求出最后$n$个数的状态。

$n\le 10^6,m\le 10^7$。

思路框架

这个是不一样的做法，是线段树+一点点思维优化。

（大家似乎都是写的链表做法啊…我不会打链表啊…）

我们发现$(i\times p+q)\mod n+1$这个式子，可以先把$i$对$n$取膜之后再算！！！也就是说，有很多次区间覆盖操作都是覆盖的同一块区间！

那么本质不同的修改操作就只有$n$个，再加上最后$m\mod n$个除不尽的。

特判$m<n$的情况。

无论哪种情况，复杂度都是$O(n \log n)$的。对于$n\le 10^6$的数据，足够了。

具体思路

显然，在同一个同余系里，最后面那次覆盖的颜色是答案。那么我们把$m$次操作，每$n$个分一块（除不尽的先不管）。显然，最后一块的操作可以把前面几块的操作全部都覆盖掉。所以最后一块是唯一有用的一块。

$m$除以$n$，可以画出这样的图：

last指针表示最后一块有用的区间前面一个位置，那么最后一块有用的染色操作就是$i=last+1,last+2\cdots last+n$的时候。

容易计算出 last 指针为：$n(\lfloor\dfrac{m}{n}\rfloor-1)$

最后$m\mod n$个特判掉。

代码

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
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
#include <bits/stdc++.h>
using namespace std;
namespace Flandre_Scarlet
{
    #define N 1666666
    #define F(i,l,r) for(int i=l;i<=r;++i)
    #define D(i,r,l) for(int i=r;i>=l;--i)
    #define Fs(i,l,r,c) for(int i=l;i<=r;c)
    #define Ds(i,r,l,c) for(int i=r;i>=l;c)
    #define MEM(x,a) memset(x,a,sizeof(x))
    #define FK(x) MEM(x,0)
    #define Tra(i,u) for(int i=G.Start(u),__v=G.To(i);~i;i=G.Next(i),__v=G.To(i))
    #define p_b push_back
    #define sz(a) ((int)a.size())
    #define iter(a,p) (a.begin()+p)
    void R1(int &x)
    {
        x=0;char c=getchar();int f=1;
        while(c<'0' or c>'9') f=(c=='-')?-1:1,c=getchar();
        while(c>='0' and c<='9') x=(x<<1)+(x<<3)+(c^48),c=getchar();
        x=(f==1)?x:-x;
    }
    void Rd(int cnt,...)
    {
        va_list args;
        va_start(args,cnt);
        F(i,1,cnt) 
        {
            int* x=va_arg(args,int*);R1(*x);
        }
        va_end(args);
    }
    class SegmentTree //线段树，区间覆盖，单点求值
    {
    public:
        struct node
        {
            int l,r,c,s;
        }tree[N<<2];
        #define ls index<<1
        #define rs index<<1|1

        #define L tree[index].l
        #define R tree[index].r
        #define S tree[index].s
        #define C tree[index].c
 
        #define lL tree[ls].l
        #define lR tree[ls].r
        #define lS tree[ls].s
        #define lC tree[ls].c

        #define rL tree[rs].l
        #define rR tree[rs].r
        #define rS tree[rs].s
        #define rC tree[rs].c
        void Build(int l,int r,int index=1)
        {
            L=l,R=r;
            if (l==r) {S=C=0;return;}
            int mid=(l+r)>>1;
            Build(l,mid,ls); Build(mid+1,r,rs);
        }
        void ChangeOne(int x,int index=1)
        {
            C=S=x;
        }
        void PushDown(int index=1) 
        {
            if (C)
            {
                ChangeOne(C,ls); ChangeOne(C,rs);
                C=0;
            }
        }
        void Change(int l,int r,int x,int index=1)
        //l到r覆盖上x
        {
            if (l>R or L>r) return;
            if (l<=L and R<=r) return ChangeOne(x,index);
            PushDown(index);
            Change(l,r,x,ls); Change(l,r,x,rs);
        }
        int Query(int pos,int index=1)
        //查询第pos个位置的值
        {
            if (pos<L or R<pos) return 0;
            if (L==R) return S;
            PushDown(index);
            return Query(pos,ls)+Query(pos,rs);
        }
    }T;

    int n,m,p,q;
    void Input()
    {
        Rd(4,&n,&m,&p,&q);
    }
    void Soviet()
    {
        #define ll(i) ((i*p+q)%n+1)
        #define rr(i) ((i*q+p)%n+1)
        T.Build(1,n);
        if (m<n) //m<n直接特判
        {
            F(i,1,m) 
            {
                int l=ll(i),r=rr(i); if (l>r) swap(l,r);
                //记得判断l>r的情况
                T.Change(l,r,i);
            }
            F(i,1,n) printf("%d\n",T.Query(i));
        }
        else
        {
            int last=(m/n-1)*n;
            F(i,1,n) //找到最后一块有用的区间
            {
                int l=ll(i),r=rr(i); if (l>r) swap(l,r);
                T.Change(l,r,++last);
            }
            F(i,last+1,m) //最后m%n个也判掉
            {
                int l=ll(i),r=rr(i); if (l>r) swap(l,r);
                T.Change(l,r,i);
            }
            F(i,1,n) printf("%d\n",T.Query(i));
        }
    }

    #define Flan void
    Flan IsMyWife()
    {
        Input();
        Soviet();
    }
}
int main()
{
    Flandre_Scarlet::IsMyWife();
    getchar();getchar();
    return 0;
}
w