2002: [Hnoi2010]Bounce 弹飞绵羊

Time Limit: 10 Sec Memory Limit: 259 MB

Submit: 11202 Solved: 5698

[][][]

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

1 2 1 1

1 1

2 1 1

1 1

Sample Output

HINT

Source

题解：

　　有n 个装置，我们可以将它们分成 √n 块。

　　对于在一块内，如果i + ki > n （直接弹飞）next = -1（没有下个个了）, ans = 1（需要一步就被弹飞），

　　如果i +ki > 这个块的最后一个， next = i+ki （弹到下一个块）， ans = 1（我们认为弹到下一个块一步）

　　如果i + ki 在这个块内，那么next = next[i+ki] （在这个块内的 i 我要他能后跳到下一个块的位置）， ans = ans[i+ki] + 1（这个很好理解）。

　　对于询问的位置x，只会一个块一个块的跳，（因为有next[i] = next[i+ki] 直到有一个位置是跳出这一块）

　　对于修改我们只需要将这个块的修改一下（块个块之间是相对独立的），而不用修改n个。（将修改的位置到这个块的位置更新一下就可以了）。

1 #include 
      
        2 #include 
       
         3 #include 
        
          4 #include 
         
           5 #include 
          
            6 #include 
           
             7 #include 
            
              8 #include 
             
               9 #include 
              10 #include 
               
                11 #include 
                
                 12 using namespace std;13 typedef long long LL;14 #define ms(a, b) memset(a, b, sizeof(a))15 #define pb push_back16 #define mp make_pair17 const int INF = 0x7fffffff;18 const int inf = 0x3f3f3f3f;19 const LL mod = 2147493647;20 const int maxn = 200000+10;21 int next[maxn], k[maxn], ans[maxn];22 void init() {23 ms(k,0);24 }25 void solve() {26 int n, unit, m, op, wei;27 scanf("%d", &n);28 for(int i = 0;i
                 
                  =0;i--){31 int temp = i + k[i];32 if(temp >= n){33 next[i] = -1;ans[i] = 1;34 }35 else if(temp >= (i/unit+1)*unit ){36 next[i] = temp;37 ans[i] = 1;38 }39 else{40 next[i] = next[temp];41 ans[i] = ans[temp] + 1;42 }43 }44 scanf("%d", &m);45 while(m--){46 scanf("%d%d", &op, &wei);47 if(op==1){48 int Ans = 0;49 for(int i = wei;~i;i=next[i])50 Ans+=ans[i];51 printf("%d\n", Ans);52 }53 else{54 int k2;55 scanf("%d", &k2);56 k[wei] = k2;57 for(int i = wei;i>=wei/unit*unit;i--){58 int temp = i + k[i];59 if(temp >= n){60 next[i] = -1;ans[i] = 1;61 }62 else if(temp >= (i/unit+1)*unit){63 next[i] = temp;64 ans[i] = 1;65 }66 else{67 next[i] = next[temp];68 ans[i] = ans[temp] + 1;69 }70 }71 72 }73 }74 }75 int main() {76 #ifdef LOCAL77 freopen("input.txt", "r", stdin);78 // freopen("output.txt", "w", stdout);79 #endif80 init();81 solve();82 return 0;83 }

View Code

转载于:https://www.cnblogs.com/denghaiquan/p/7236867.html

你可能感兴趣的文章