我爱歌唱伴奏,日本熊本地震,8100
下面上代码:
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 }
如对本文有疑问,请在下面进行留言讨论,广大热心网友会与你互动!! 点击进行留言回复
如何在没有core文件的情况下用dmesg+addr2line定位段错误
用QT制作3D点云显示器——QtDataVisualization
网友评论