题目背景
搞不懂为什么大家伙都叫 弹(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 ≤ 10000，对于100%的数据n ≤ 200000,m ≤ 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 ;
}
京公网安备 11010502036488号