fork download
copy 
  1. #include <cstring>
  2. #include <cmath>
  3. #include <algorithm>
  4. #include <cstdlib>
  5. #include <cstdio>
  6. #include <fstream>
  7. #include <iostream>
  8.  
  9. #define rep(i, l, r) for(int i = l; i <= r; i++)
  10. #define down(i, l, r) for(int i = l; i >= r; i--)
  11. #define MS 234567
  12. #define MAX 1037471823
  13. #define Q 1
  14.  
  15. using namespace std;
  16.  
  17. int s, n, m, k[MS], next[MS], c[MS], q, a, b;
  18.  
  19. void Build(int x)
  20. {
  21. 	int a;
  22. 	if (x == n-1)
  23. 	{
  24. 		int b = (s-1)%m+1; down(i, b, 1)
  25. 		{
  26. 			a = x*m+i;
  27. 			if (k[a]+a > x*m+b) next[a] = k[a]+a, c[a] = 1; else next[a] = next[k[a]+a], c[a] = c[k[a]+a]+1;
  28. 		}
  29. 		return;
  30. 	}
  31. 	down(i, m, 1)
  32. 	{
  33. 		a = x*m+i;
  34. 		if (k[a]+a > x*m+m) next[a] = k[a]+a, c[a] = 1; else next[a] = next[k[a]+a], c[a] = c[k[a]+a]+1;
  35. 	}
  36. }
  37.  
  38. int Jump(int x)
  39. {
  40. 	int ans = 0;
  41. 	while (x <= s) ans += c[x], x = next[x];
  42. 	return ans;
  43. }
  44.  
  45. int main()
  46. {
  47. 	scanf("%d", &s); rep(i, 1, s) scanf("%d", &k[i]);
  48. 	m = int(sqrt(s)); while (n*m < s) n++;
  49. 	rep(i, 0, n-1) Build(i);
  50. 	scanf("%d", &q);
  51. 	rep(i, 1, q)
  52. 	{
  53. 		scanf("%d", &a);
  54. 		if (a == 1)
  55. 		{
  56. 			scanf("%d", &a); a++;
  57. 			printf("%d\n", Jump(a));
  58. 		}
  59. 		else
  60. 		{
  61. 			scanf("%d%d", &a, &b); a++;
  62. 			k[a] = b;
  63. 			Build((a-1)/m);
  64. 		}
  65. 	}
  66. 	return 0;
  67. }
Success #stdin #stdout 0s 6092KB
comments (?)
stdin
copy 
4
1 2 1 1
3
1 1
2 1 1
1 1
stdout
copy 
2
3
https://ideone.com/DjIFvm
BZOJ 2002 静态块状链表
language:
C++ (gcc 8.3)
created:
9 years ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!