「HNOI 2010」弹飞绵羊

发表于 | | 阅读次数:
字数统计: 1.3k 字

Description

题目链接：BZOJ 2002

某天，Lostmonkey 发明了一种超级弹力装置，为了在他的绵羊朋友面前显摆，他邀请小绵羊一起玩个游戏。游戏一开始，Lostmonkey 在地上沿着一条直线摆上 $n$ 个装置，每个装置设定初始弹力系数 $k_i$，当绵羊达到第 $i$ 个装置时，它会往后弹 $k_i$ 步，达到第 $i+k_i$ 个装置，若不存在第 $i+k_i$ 个装置，则绵羊被弹飞。绵羊想知道当它从第 $i$ 个装置起步时，被弹几次后会被弹飞。为了使得游戏更有趣，Lostmonkey 可以修改某个弹力装置的弹力系数，任何时候弹力系数均为正整数。

数据范围：$1\le n\le 2\times 10^5$，$1\le m\le 10^5$

Solution

解法 1（LCT）

首先我们建立一个虚点 $n+1$，意味着绵羊到达这个点就被弹飞。

对于每个装置，如果 $i+k_i\le n$，那么我们连边 $(i,i+k_i)$，否则连边 $(i,n+1)$。

对于修改操作，显然我们需要断开原来的边 $(i,i+k_i)$ 或 $(i,n+1)$，连上新的边 $(i,i+k)$ 或 $(i,n+1)$。由于要动态连边和删边，我们可以很自然地想到 $\text{LCT}$。

接下来我们考虑询问操作。对于询问 $x$，我们要查询的就是 $x$ 到 $n+1$ 这条链上的边的数量。于是我们就可以用 $\text{LCT}$ 的 $\text{split}$ 操作，得到 $x$ 到 $n+1$ 这条链的 $\text{Splay}$。我们只要维护 $\text{Splay}$ 中的节点个数，那么答案就是 $size_{n+1}-1$ 了。

时间复杂度：$O(m\log n)$

解法 2（分块）

考虑 $\sqrt n$ 分块。我们维护每个点它在块内可以往后跳动的次数，记为 $cnt_i$；跳动后到达块内最远点的位置（如果直接跳出块，那么记录跳动一次到达的位置），记为 $pos_i$。

对于修改操作，我们对 $x$ 所在块的信息暴力重新计算，复杂度为 $O(\sqrt n)$。

对于查询操作，我们从 $x$ 往后暴力跳，因为每个块内经过的次数是 $O(1)$ 的，那么复杂度为 $O(\sqrt n)$。

时间复杂度：$O(m\sqrt n)$（由于常数问题，分块比 $\text{LCT}$ 跑的要快 QAQ）

Code

解法 1

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
 
#include <cstdio>
#include <algorithm>
#define ls(x) ch[x][0]
#define rs(x) ch[x][1]

const int N=2e5+5;
int n,m,k[N],fa[N],ch[N][2],sz[N],st[N];
bool rev[N];

bool get(int x) {
    return rs(fa[x])==x;
}
bool isroot(int x) {
    return ls(fa[x])!=x&&rs(fa[x])!=x;
}
void pushup(int x) {
    sz[x]=sz[ls(x)]+sz[rs(x)]+1;
}
void pushdown(int x) {
    if(rev[x]) {
        std::swap(ls(x),rs(x));
        rev[ls(x)]^=1,rev[rs(x)]^=1,rev[x]=0;
    }
}
void rotate(int x) {
    int y=fa[x],z=fa[y],k=get(x);
    !isroot(y)&&(ch[z][get(y)]=x),fa[x]=z;
    ch[y][k]=ch[x][k^1],fa[ch[x][k^1]]=y;
    ch[x][k^1]=y,fa[y]=x;
    pushup(y),pushup(x);
}
void splay(int x) {
    int u=x,tp=0;
    st[++tp]=u;
    while(!isroot(u)) st[++tp]=u=fa[u];
    while(tp) pushdown(st[tp--]);
    while(!isroot(x)) {
        int y=fa[x];
        if(!isroot(y)) rotate(get(x)==get(y)?y:x);
        rotate(x);
    }
}
void access(int x) {
    for(int y=0;x;x=fa[y=x]) splay(x),rs(x)=y,pushup(x);
}
void makeroot(int x) {
    access(x),splay(x),rev[x]^=1;
}
int findroot(int x) {
    access(x),splay(x);
    pushdown(x);
    while(ls(x)) pushdown(x=ls(x));
    return x;
}
void split(int x,int y) {
    makeroot(x),access(y),splay(y);
}
void link(int x,int y) {
    makeroot(x);
    if(findroot(y)!=x) fa[x]=y;
}
void cut(int x,int y) {
    makeroot(x);
    if(findroot(y)==x&&fa[x]==y&&!rs(x)) fa[x]=ls(y)=0,pushup(y);
}
int main() {
    scanf("%d",&n);
    for(int i=1;i<=n;++i) {
        scanf("%d",&k[i]);
        link(i,i+k[i]<=n?i+k[i]:n+1);
    }
    for(scanf("%d",&m);m--;) {
        int opt,x;
        scanf("%d%d",&opt,&x),++x;
        if(opt==1) {
            split(x,n+1);
            printf("%d\n",sz[n+1]-1);
        } else {
            int v;
            scanf("%d",&v);
            cut(x,x+k[x]<=n?x+k[x]:n+1);
            link(x,x+v<=n?x+v:n+1);
            k[x]=v;
        }
    }
    return 0;
}

解法 2

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
 
#include <cstdio>
#include <cmath>

const int N=2e5+5,M=500;
int n,m,len,num,bl[N],l[M],r[M],k[N],cnt[N],pos[N];

void build() {
    len=sqrt(n),num=(n-1)/len+1;
    for(int i=1;i<=n;++i) bl[i]=(i-1)/len+1;
    for(int i=1;i<=num;++i) l[i]=(i-1)*len+1,r[i]=i*len;
    r[num]=n;
}
void modify(int x,int y) {
    for(int i=y;i>=x;--i) {
        int j=i+k[i];
        if(j>r[bl[i]]) {
            cnt[i]=1,pos[i]=j;
        } else {
            cnt[i]=cnt[j]+1,pos[i]=pos[j];
        }
    }
}
int query(int x) {
    int ans=0;
    while(x<=n) ans+=cnt[x],x=pos[x];
    return ans;
}
int main() {
    scanf("%d",&n);
    for(int i=1;i<=n;++i) scanf("%d",&k[i]);
    build();
    modify(1,n);
    for(scanf("%d",&m);m--;) {
        int opt,x;
        scanf("%d%d",&opt,&x),++x;
        if(opt==1) {
            printf("%d\n",query(x));
        } else {
            int v;
            scanf("%d",&v);
            k[x]=v,modify(l[bl[x]],r[bl[x]]);
        }
    }
    return 0;
}
0%