欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页  >  IT编程

BZOJ 2002 弹飞绵羊(分块)

程序员文章站 2022-05-21 08:13:42
题目:弹飞绵羊 这道题,据说是lct裸题,但是lct那么高级的数据结构,我并不会,所以采取了学长讲过的分块做法,我们对序列分块,可以定义两个数组,其中一个表示从当前位置跳出当前块需要多少步,另一个数组表示从当前位置跳到下一块会落在哪个位置,然后新修改就暴力修改当前块,查询就直接暴力跑块外的结果。数组 ......

题目:弹飞绵羊

这道题,据说是lct裸题,但是lct那么高级的数据结构,我并不会,所以采取了学长讲过的分块做法,我们对序列分块,可以定义两个数组,其中一个表示从当前位置跳出当前块需要多少步,另一个数组表示从当前位置跳到下一块会落在哪个位置,然后新修改就暴力修改当前块,查询就直接暴力跑块外的结果。数组初始化可以考虑倒着跑,然后分情况讨论。这题被我们完美解决了。

 

下面上代码:

BZOJ 2002 弹飞绵羊(分块)
 1 #include<iostream>
 2 #include<cmath>
 3 #include<cstring>
 4 #include<algorithm>
 5 #include<cstdio>
 6 #define db double
 7 using namespace std;
 8 const int n=200005;
 9 int n,m,a[n],t1,t2,t3,siz,s,t,to[n],stp[n];
10 int query(int p){
11     int rt=0;while(~p){
12         rt+=stp[p];p=to[p];
13     } return rt;
14 } void update(int p,int da){
15     s=p/siz*siz;t=(p/siz+1)*siz-1;
16     a[p]=da;for(int i=p;i>=s;i--)
17     if(i+a[i]>=n) to[i]=-1,stp[i]=1;
18     else if(i+a[i]>t) to[i]=i+a[i],stp[i]=1;
19     else to[i]=to[i+a[i]],stp[i]=stp[i+a[i]]+1;
20 } int main(){
21     scanf("%d",&n);siz=(int)sqrt((db)n+0.5);
22     for(int i=0;i<n;i++) scanf("%d",&a[i]);
23     for(int i=n-1;~i;i--){
24         t=(i/siz+1)*siz-1;
25         if(i+a[i]>=n) to[i]=-1,stp[i]=1;
26         else if(i+a[i]>t) 
27         to[i]=i+a[i],stp[i]=1;
28         else to[i]=to[i+a[i]],
29         stp[i]=stp[i+a[i]]+1;
30     } scanf("%d",&m);
31     while(m--){
32         scanf("%d%d",&t1,&t2);
33         if(t1==1) printf("%d\n",query(t2));
34         else scanf("%d",&t3),update(t2,t3);
35     } return 0;
36 }
分块