首页 > 代码库 > BZOJ 4764: 弹飞大爷

BZOJ 4764: 弹飞大爷

4764: 弹飞大爷

Time Limit: 30 Sec  Memory Limit: 256 MB
Submit: 4  Solved: 4
[Submit][Status][Discuss]

Description

自从WC退役以来,大爷是越来越懒惰了。为了帮助他活动筋骨,也是受到了弹飞绵羊一题的启发,机房的小伙伴们
决定齐心合力构造一个下面这样的序列。这个序列共有N项,每项都代表了一个小伙伴的力量值,如果大爷落到了
第i个小伙伴的手里,那么第i个小伙伴会把大爷弹到第i+ai个小伙伴手里,其中ai就是第i个小伙伴的力量值,也
就是序列的第i项。然而,因为大爷太沉了,所以有些小伙伴不能撑到锻(you)炼(xi)结束,所以我们中途会替
换一些小伙伴,也就是改变序列的某些项。而且,因为大爷太沉了,所以有些小伙伴不能把大爷扔向前方,而是会
把大爷往反方向扔,也就是序列中的一些项会是负的(当然,也可能是零喽)。现在机智的大爷通过在空中的观察
,已经知道小伙伴们的所有活动——即初始序列、所有更改操作,他想请你算一算,如果他在某时刻落到了某个位
置,那么他会在几次弹起之后落到小伙伴序列之外(毕竟摔在地上还是蛮疼的)。

 

Input

第一行为两个整数N和M,代表序列长度和操作次数。
第二行为N个整数,代表初始的小伙伴序列。
接下来有M行,每行代表一个操作。
如果这一行的第一个数是1,代表该操作是一个询问操作,接下来一个数X,代表询问此时大爷从X处,经过几次弹
起会摔在地上。如果永远不会摔在地上,请输出-1。
如果这一行的第一个数是2,代表该操作是一个更改操作,接下来两个数X,Y,代表将序列的第X项改为Y。
N,M <= 200000  |Ai| < N
 

Output

对于每次询问操作,输出弹起次数或-1。
 

Sample Input

3 19
1 1 1
1 1
1 2
1 3
2 1 2
1 1
1 2
1 3
2 3 -1
1 1
1 2
1 3
2 2 233
1 1
1 2
1 3
2 2 -233
1 1
1 2
1 3

Sample Output



3
2
1
2
2
1
-1
-1
-1
3
1
2
3
1
2

HINT

 

Source

By YouSiki & GuoZZ

[Submit][Status][Discuss]

 

 

 

今天偶然看到了某童鞋的弹飞绵羊的分块做法,十分不爽,想法卡他,然后就有了这道题,反正我觉得原来的分块方法是绝望了。但是万万木有想到,这道题依然有非LCT做法,比如大爷的Split Treap做法等等。

 

作为此题的出题人之一,其实我只负责题面部分和代码,解法都是ZZ和LH想的,和我没有半毛钱关系。

 

考虑怎么继续沿用弹飞绵羊的LCT做法,发现可能产生环,很烦。但是可以通过把环上的一条断掉,使得其在LCT中仍然是一棵树,我们把这条被“隐藏”起来的边标记在该树的Root上。那么每次加入边的时候,现考虑一下是否会形成环,如果会,就按照上面的方法处理。然后还有断边操作,只需要考虑一下断掉这条边后,是否会使得Root上的隐藏边重新显现即可。

 

不爽的是,刚刚放到大视野上一个下午,std就被LincHpin和Claris踩了。开心的是,至少我数据应该没造错。

 

  1 #include <bits/stdc++.h>  2   3 const int mxn = 200005;  4   5 int tag[mxn];  6 int rev[mxn];  7 int siz[mxn];  8 int fat[mxn];  9 int son[mxn][2]; 10  11 inline bool isRoot(int t) 12 { 13     int f = fat[t]; 14      15     if (!f) 16         return true; 17      18     if (son[f][0] == t) 19         return false; 20     if (son[f][1] == t) 21         return false; 22      23     return true; 24 } 25  26 inline void update(int t) 27 { 28     siz[t] = 1; 29      30     if (son[t][0]) 31         siz[t] += siz[son[t][0]]; 32     if (son[t][1]) 33         siz[t] += siz[son[t][1]]; 34 } 35  36 inline void connect(int f, int t, int s) 37 { 38     if (t) 39         fat[t] = f; 40     if (f) 41         son[f][s] = t; 42 } 43  44 inline void rotate(int t) 45 { 46     int f = fat[t]; 47     int g = fat[f]; 48     int s = son[f][1] == t; 49      50     connect(f, son[t][!s], s); 51     connect(t, f, !s); 52      53     fat[t] = g; 54     if (g && son[g][0] == f) 55         son[g][0] = t; 56     if (g && son[g][1] == f) 57         son[g][1] = t; 58      59     update(f); 60     update(t); 61 } 62  63 inline void push(int t) 64 { 65     if (rev[t]) 66     { 67         rev[t] = 0; 68          69         if (son[t][0]) 70             rev[son[t][0]] ^= 1; 71         if (son[t][1]) 72             rev[son[t][1]] ^= 1; 73              74         std::swap(son[t][0], son[t][1]); 75     } 76 } 77  78 inline void pushdown(int t) 79 { 80     static int stk[mxn], tot; 81      82     stk[++tot] = t; 83      84     while (!isRoot(t)) 85         stk[++tot] = t = fat[t]; 86      87     while (tot)push(stk[tot--]); 88 } 89  90 inline void splay(int t) 91 { 92     pushdown(t); 93      94     while (!isRoot(t)) 95     { 96         int f = fat[t]; 97         int g = fat[f]; 98          99         if (isRoot(f))100             rotate(t);101         else102         {103             int a = f && son[f][1] == t;104             int b = g && son[g][1] == f;105             106             if (a == b)107                 rotate(f), rotate(t);108             else109                 rotate(t), rotate(t);110         }111     }112 }113 114 inline void access(int t)115 {116     int q = t;117     118     for (int p = 0; t; p = t, t = fat[t])119         splay(t), son[t][1] = p, update(t);120     121     splay(q);122 }123 124 inline void makeRoot(int t)125 {126     access(t), rev[t] ^= 1;127 }128 129 inline void link(int t, int f)130 {131     makeRoot(t), fat[t] = f;132 }133 134 inline void cut(int t)135 {136     access(t);137     fat[son[t][0]] = 0;138     son[t][0] = 0;139     update(t);140 }141 142 inline int find(int t)143 {144     access(t);145     146     int p = t;147     148     while (son[p][0])149         p = son[p][0];150     151     return p;152 }153 154 inline void Link(int t, int f)155 {156     if (t == f)157     {158         tag[t] = f;159         return;160     }161     162     if (find(t) != find(f))163         link(t, f);164     else165         makeRoot(t), tag[t] = f;166 }167 168 inline void change(int t, int f)169 {170     access(t);171     172     int p = find(t);173     174     if (!tag[p])175         cut(t), Link(t, f);176     else177     {178         if (t == p)179         {180             tag[p] = 0;181             Link(t, f);182         }183         else184         {185             int k = tag[p];186             187             cut(t), Link(t, f);188             189             if (find(k) != find(p))190                 link(p, k), tag[p] = 0;191         }192     }193 }194 195 int n, m, s[mxn];196 197 signed main(void)198 {199     scanf("%d%d", &n, &m);200     201     for (int i = 1; i <= n; ++i)202         scanf("%d", s + i);203     204     for (int i = 1; i <= n; ++i)205     {206         int t = i + s[i];207         208         if (t < 1)209             Link(i, n + 1);210         else if (t > n)211             Link(i, n + 1);212         else213             Link(i, t);214     }215     216     for (int i = 1; i <= m; ++i)217     {218         int opt; scanf("%d", &opt);219         220         if (opt == 1)221         {222             int t; scanf("%d", &t);223             224             int p = find(t);225             226             if (tag[p])227                 puts("-1");228             else229             {230                 makeRoot(n + 1), access(t);231                 printf("%d\n", siz[son[t][0]]);232             }233         }234         else235         {236             int a, b; scanf("%d%d", &a, &b);237             238             s[a] = b;239             240             int t = a + b;241             242             if (t < 1)243                 change(a, n + 1);244             else if (t > n)245                 change(a, n + 1);246             else247                 change(a, t);248         }249     }250 }

 

@Author: YouSiki

 

BZOJ 4764: 弹飞大爷