Luogu4690 镜中的昆虫

Arahc 11.0
  2022-01-08 08:00 2022-01-08 08:00 创建   2023-03-15 14:17:58 2023-03-15 14:17:58 更新      2k 字  9 分钟  

题面

简化题意

维护一个序列：

  1. 将区间 [l,r][l,r] 染色。
  2. 查寻区间 [l,r][l,r] 有几种颜色。

n,m≤105n,m\leq 10^5，空间限制 64MB。

题解

考虑这个问题的弱化版 CF848C（可以转化为类似单点修改颜色，区间查询的问题）怎么做，设位置为 ii 的颜色上一次出现的位置为 preipre_i，查寻时转化为查寻 i∈[l,r],prei∈[0,l−1]i\in[l,r],pre_i\in[0,l-1] 的 ii 的数量。将 i,preii,pre_i 看作横纵坐标，就可以转化为数点问题。于是可以：用 n+mn+m 个 set 分别维护每个颜色出现的位置，方便查寻前驱后继。单次修改时：

  1. 这个位置原本的贡献，和它后继的贡献删除。
  2. 更新它的后继的贡献。
  3. 修改这个位置的颜色，更新新颜色带来的贡献和变化。

现在 单点修改 问题转化为了 区间修改。显然把 i,preii,pre_i 当成横纵坐标数点的思路仍然正确，考虑如何解决区间修改。发现本题的修改操作就是区间覆盖，可以用类似 ODT 的推平操作进行。

还是对于每个颜色维护一个 set，但是 set 内应该存区间，表示这一段区间内都是这个颜色，按左右端点排序无所谓，因为显然各个 set 的区间无交。单次修改时：

  1. 细节：左端点可能被一个区间完全包含，这时可以把这个区间裂成两个区间，右端点同理。使得要修改的范围内所有区间都严格被修改的范围 [l,r][l,r] 包含。
  2. 遍历 [l,r][l,r] 内的每一个区间，对于任意一个区间，修改它的后继对这个区间造成的的贡献，删除本区间对 prepre 造成的贡献，然后把这个区间删除。
  3. 把这个区间覆盖成新的颜色，更新新颜色带来的贡献和变化。

为什么这么做不会 T？考虑初始状态下有 nn 个区间，单次修改最坏产生三个区间（在一个区间内部覆盖），修改次数可以均摊地视为 O⁡(n)\operatorname{O}(n) 级别。

考虑查寻，发现一段区间内出了左端点其它所有点的 prei=i−1pre_i=i-1，因此只需要记录每个左端点产生的贡献。查询时，如果 ll 被一个区间包含，可以将 ll 直接拉到这个区间的左端点的位置再查寻，避免这个区间被查漏。

根据上述分析本题的做法已经完形，剩下的就是如何实现，我见过的（不一定写过）的有以下几种：

  1. 离线 cdq 查询。时间复杂度 nlog⁡nn\log n，空间线性。可过。
  2. 在线 KDTree 数点，时间复杂度 nnn\sqrt{n}，空间线性，不可过。参考我 LOJ 上代码。
  3. 分块，时空复杂度 nnn\sqrt n，不可过。
  4. 二维线段树等，时空复杂度 nlog⁡2nn\log^2 n，不可过。
  5. 树套树，时间复杂度 nlog⁡2nn\log^2n，空间复杂度 nlog⁡nn\log n，可过。

很多人认为树套树的空间复杂度是 nlog⁡2nn\log^2 n，事实上，考虑用树状数组套平衡树即可。因为树状数组的空间复杂度是单 log⁡\log，写平衡树的时候删除操作记个内存池回收即可。

本人用的树状数组套替罪羊，替罪羊树常数较小，推荐使用。

代码

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
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
#include<stdio.h>
#include<map>
#include<set>
#include<algorithm>
using namespace std;
const int max_n=100001;
inline int read(){
    int x=0;char c=getchar();
    while(c<'0' || c>'9') c=getchar();
    while(c>='0' && c<='9') x=(x<<1)+(x<<3)+(c^48),c=getchar();
    return x;
}
inline void write(int x){
    if(x>9) write(x/10);
    putchar(x%10^48);
}

int n,m,p,pre,nxt,col[max_n],R[max_n];

map<int,int> mp;
set<int> s[max_n*2];
set<int>::iterator it,kt;

inline int Pre(int x,int col){
    auto it=s[col].lower_bound(x);
    return R[*(--it)];
}
inline int Nxt(int x,int col){
    auto it=s[col].upper_bound(x);
    return *it;
}
inline set<int>::iterator In(int i,int col){
    return s[col].lower_bound(i);
}
int fre[max_n*9],tp;
struct SheepTree{
    int root[max_n],pb[max_n],tot,tmp;
    SheepTree(){tot=tmp=0;}
    const double alpha=0.75;
    struct dot{
        int ls,rs,sz,cnt,sd,sm,val;
    }a[max_n*9];
    #define ls(x) (a[x].ls)
    #define rs(x) (a[x].rs)

    inline int newnode(){
        int x;
        if(tp) x=fre[tp--];
        else x=++tot;
        ls(x)=rs(x)=a[x].sz=a[x].sm=a[x].sd=a[x].val=0;
        return x;
    }
    inline void resize(int &x){
        a[x].sz=a[ls(x)].sz+a[rs(x)].sz+(bool)(a[x].cnt);
        a[x].sd=a[ls(x)].sd+a[rs(x)].sd+1;
        a[x].sm=a[ls(x)].sm+a[rs(x)].sm+a[x].cnt;
    }
    inline bool regain(int &x){
        if(!a[x].sm) return 0;
        return (alpha*a[x].sd<=max(a[ls(x)].sd,a[rs(x)].sd) || alpha*a[x].sd>=a[x].sz);
    }
    inline void get(int x){
        if(ls(x)) get(ls(x));
        if(a[x].cnt) pb[++tmp]=x;
        else fre[++tp]=x;
        if(rs(x)) get(rs(x));
    }
    inline int build(int l,int r){
        if(l==r){
            ls(pb[l])=rs(pb[l])=0;
            resize(pb[l]);
            return pb[l];
        }
        int mid=(l+r)>>1,x=pb[mid];
        ls(x)=rs(x)=0;
        if(l<=mid-1) ls(x)=build(l,mid-1);
        if(r>=mid+1) rs(x)=build(mid+1,r);
        resize(x);
        return x;
    }
    inline void rebuild(int &x){
        tmp=0,get(x);
        if(tmp) x=build(1,tmp);
    }
    inline void pushup(int &x){
        resize(x);
        if(regain(x)) rebuild(x);
    }
    inline void insert(int &x,int val){
        if(!x){
            x=newnode(),
            a[x].val=val,a[x].cnt=1,
            resize(x);
            return;
        }
        if(val==a[x].val) ++a[x].cnt;
        else if(val<a[x].val) insert(ls(x),val);
        else insert(rs(x),val);
        pushup(x);
    }
    inline void delet(int &x,int val){
        if(a[x].val==val) --a[x].cnt;
        else if(val<a[x].val) delet(ls(x),val);
        else delet(rs(x),val);
        pushup(x);
    }
    inline int rank(int &x,int val){
        if(!x) return 0;
        if(val==a[x].val) return a[ls(x)].sm;
        else if(val<a[x].val) return rank(ls(x),val);
        return a[ls(x)].sm+a[x].cnt+rank(rs(x),val);
    }
}shp;

struct BIT{
    inline void insert(int x,int y){
        for(;x<=n;x+=x&-x)
            shp.insert(shp.root[x],y);
    }
    inline void delet(int x,int y){
        if(x>n) return;
        for(;x<=n;x+=x&-x)
            shp.delet(shp.root[x],y);
    }
    inline int ask(int x,int y){
        int res=0;
        for(;x;x-=x&-x)
            res+=shp.rank(shp.root[x],y);
        return res;
    }
}bit;

signed main(){
    // freopen("data.in","r",stdin),
    // freopen("data.out","w",stdout);
    n=read(),m=read(),mp[-1]=0,R[0]=0,R[n+1]=n+1;
    for(register int i=0;i<=n+m;++i)
        s[i].insert(0),s[i].insert(n+1);
    for(register int i=1,ls=1,lt=0;i<=n;++i){
        int x=read();
        if(!mp.count(x)) mp[x]=mp.size();
        x=mp[x];
        if(i>1 && x!=lt){
            s[0].insert(ls),col[ls]=lt,
            s[lt].insert(ls),R[ls]=i-1,
            bit.insert(ls,Pre(ls,lt));
            ls=i;
        }
        if(i==n){
            s[0].insert(ls),col[ls]=x,
            s[x].insert(ls),R[ls]=n,
            bit.insert(ls,Pre(ls,x));
        }
        lt=x;
    }
    while(m--){
        int op=read(),l=read(),r=read();
        if(op==1){
            int x=read();
            if(!mp.count(x)) mp[x]=mp.size();
            x=mp[x];
            it=s[0].lower_bound(l),--it,
            kt=In(*it,col[*it]);

            if(*kt<l && R[*kt]>=l){
                if(col[*it]==x)
                    l=*it;
                else{
                    int tp=R[*kt];
                    s[col[*it]].erase(kt),
                    s[col[*it]].insert(*it),R[*it]=l-1,
                    s[col[*it]].insert(l),R[l]=tp;
                    s[0].insert(l),col[l]=col[*it];
                    ++it;
                    bit.insert(l,l-1);
                }
            }
            for(auto jt=it;*it<=r;it=jt){
                jt=it,++jt,p=col[*it];
                if(R[*it]<l || *it<l) continue;
                if(R[*it]>r){
                    pre=Pre(*it,p),
                    bit.delet(*it,pre),
                    s[p].erase(In(*it,p)),
                    s[p].insert(r+1),R[r+1]=R[*it],
                    bit.insert(r+1,pre);
                    col[r+1]=p,
                    s[0].erase(it),s[0].insert(r+1);
                    break;
                }
                pre=Pre(*it,p),nxt=Nxt(*it,p);
                bit.delet(*it,pre),
                bit.delet(nxt,R[*it]);
                s[p].erase(In(*it,p)),
                s[0].erase(it);
                bit.insert(nxt,pre);
            }
            nxt=Nxt(r,x),pre=Pre(r,x);
            bit.delet(nxt,pre);
            s[0].insert(l),col[l]=x,
            s[x].insert(l),R[l]=r;
            bit.insert(l,pre),
            bit.insert(nxt,r);
        }
        else{
            it=s[0].lower_bound(l),--it;
            if(*it<l && R[*it]>=l)
                l=*it;
            write(bit.ask(r,l)-bit.ask(l-1,l)),putchar('\n');
        }
    }
    return 0;
}
  • 标题: Luogu4690 镜中的昆虫
  • 作者: Arahc
  • 创建于 : 2022-01-08 08:00:00
  • 更新于 : 2023-03-15 14:17:58
  • 链接: https://arahc.github.io/2022/01/08/【题解】Luogu4690-镜中的昆虫/
  • 版权声明: 本文章采用 CC BY-NC-SA 4.0 进行许可。
评论
目录
Luogu4690 镜中的昆虫
  1. 题面
  2. 题解
  3. 代码