Tag-Link-Cut-Tree

Icontofig 's Blog // 我们的征程是星辰大海!Away From OI,Come to ICPC(查看友链请点About Me)

 2018-12-26 10:24:28 |  0 Comments  |  Link-Cut-Tree

BZOJ2002[HNOI2010] 弹飞绵羊 (LCT)

BZOJ2002[HNOI2010] 弹飞绵羊 (LCT)

Description

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

Input

第一行包含一个整数n,表示地上有n个装置,装置的编号从0到n-1,接下来一行有n个正整数,依次为那n个装置的初始弹力系数。第三行有一个正整数m,接下来m行每行至少有两个数i、j,若i=1,你要输出从j出发被弹几次后被弹飞,若i=2则还会再输入一个正整数k,表示第j个弹力装置的系数被修改成k。对于20%的数据n,m<=10000,对于100%的数据n<=200000,m<=100000

Output

对于每个i=1的情况,你都要输出一个需要的步数,占一行。

Sample Input

4  
1 2 1 1  
3  
1 1  
2 1 1  
1 1

Sample Output

2
3

题目链接:https://www.lydsy.com/JudgeOnline/problem.php?id=2002

题解:

LCT基础板题,终于凑出了属于自己代码风格的一套LCT模板,以后终于不用百度别人的去改LCT了
只不过此题的link和cut操作可以叠在一起,由于题目性质,cut后的点一定是某个辅助树的根,所以不需要换根操作(evert),自然也就不用写pushdown。不过写上也没错,只是运行速度会稍慢一些。

代码(写了些多余的比如push_down):

#include <iostream>
#include <cstdio>
#include <cstring>
#include <cmath>
#include <algorithm>
#include <cstdlib>
using namespace std;
int get_num(){
    int num = 0;
    char ch;
    bool flag = false;
    
Title - Artist
0:00