洛谷P3203 弹飞绵羊

题目背景

搞不懂为什么大家伙都叫 弹(dan)飞绵羊

---

这道题我是用来点亮洛谷试炼场的分块模板的…

当然使用分块做的啊!

然后L_Y_T想了想,就右转题解了…

然后发现题解的代码可读性极差

于是就了解思路后自己打了一下

---

题目描述

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

输入输出格式

输入格式：

第一行包含一个整数n，表示地上有n个装置，装置的编号从0到n-1。

接下来一行有n个正整数，依次为那n个装置的初始弹力系数。

第三行有一个正整数m，

接下来m行每行至少有两个数i、j，若i=1，你要输出从j出发被弹几次后被弹飞，若i=2则还会再输入一个正整数k，表示第j个弹力装置的系数被修改成k。

输出格式：

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

输入输出样例

输入样例：

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

输出样例 :

2 3

说明

对于20%的数据n,m $\le$ 10000，对于100%的数据n $\le$ 200000,m $\le$ 100000

---

code:

#include <iostream> #include <stdio.h> #include <string.h> #include <math.h> #include <algorithm> #define maxn 210000 using namespace std ; int N , pos[maxn] , tag[maxn] , res[maxn] ; int n , m;int R[maxn] , L[maxn] ; int a[maxn] ; int read() ; void change(int x , int k) ; void update(int x , int y) ; int query(int x) ; int main() { n = read() ; N = sqrt(n) ; for(int i = 1 ; i <= n ; i ++) { pos[i] = (i-1)/N + 1; } for(int i = 1 ; i <= N ; i ++) { L[i] = (i-1)*N+1 ; R[i] = i*N ; } for(int i = 1 ; i <= n ; i ++) { a[i] = read() ; } update(1,n) ; m = read() ; for(int i = 1 ; i <= m ; i ++) { int x , y , z; x = read () , y = read()+1; if(x == 1) { cout << query(y) << endl ; }else { z = read() ; a[y] = z ; update(L[pos[y]],R[pos[y]]) ; } } return 0; } int query(int y) { int ans = tag[y] , x = res[y]; for (int i = pos[y] ; i <= m && x <= n ; i ++) ans += tag[x] , x = res[x] ; return ans ; } void update(int x ,int y) { for(int i = y ; i >= x ; i --) { if(i + a[i] > R[pos[i]]) { tag[i] = 1 ; res[i] = i + a[i] ; }else { tag[i] = tag[i+a[i]] + 1 ; res[i] = res[i+a[i]] ; } } } void change(int x , int k) { a[x] = k ; } int read() { int x = 0 ;int f = 1 ;char s = getchar() ; while(s>'9'||s<'0') {if(s=='-')f=-1;s=getchar();} while(s<='9'&&s>='0') {x=x*10+(s-'0');s=getchar();} return x*f ; }

---