- 1#include 2 using namespace std;
- 3#define fr first 4#define sc second 5#define cl clear 6#define BUG puts("here!!!") 7#define W(a) while (a--) 8#define pb(a) push_back(a) 9#define Rint(a) scanf("%d", &a) 10#define Rll(a) scanf("%lld", &a) 11#define Rs(a) scanf("%s", a) 12#define Cin(a) cin >> a 13#define FRead() freopen("in", "r", stdin) 14#define FWrite() freopen("out", "w", stdout) 15#define Rep(i, len) for (int i = 0; i < (len); i++) 16#define For(i, a, len) for (int i = (a); i < (len); i++) 17#define Cls(a) memset((a), 0, sizeof(a)) 18#define Clr(a, in) memset((a), ( in ), sizeof(a)) 19#define Full(a) memset((a), 0x7f7f7f, sizeof(a)) 20#define lrt rt << 1 21#define rrt rt << 1 | 1 22#define pi 3.14159265359 23#define RT
- return 24#define lowbit( in ) in &( - in) 25#define onenum( in ) __builtin_popcount( in ) 26 typedef long long LL;
- 27 typedef long double LD;
- 28 typedef unsigned long long ULL;
- 29 typedef pair < int,
- int > pii;
- 30 typedef pair < string,
- int > psi;
- 31 typedef pair pll;
- 32 typedef map < string,
- int > msi;
- 33 typedef vector < int > vi;
- 34 typedef vector vl;
- 35 typedef vector vvl;
- 36 typedef vector < bool > vb;
- 37 38 const int maxn = 200200;
- 39 int n,
- q,
- sz,
- cmd;
- 40 int st[maxn],
- to[maxn],
- k[maxn],
- be[maxn];
- 41 42 void update(int pos, int val) {
- 43 k[pos] = val;
- 44
- for (int i = pos; i >= be[pos] * sz; i--) {
- 45
- if (i + k[i] > n - 1) {
- 46 st[i] = 1;
- 47 to[i] = -1;
- 48
- }
- 49
- else {
- 50
- if (be[i] == be[i + k[i]]) {
- 51 st[i] = st[i + k[i]] + 1;
- 52 to[i] = to[i + k[i]];
- 53
- }
- 54
- else {
- 55 st[i] = 1;
- 56 to[i] = i + k[i];
- 57
- }
- 58
- }
- 59
- }
- 60
- }
- 61 62 int query(int pos) {
- 63 int ret = 0;
- 64
- while (pos != -1) {
- 65 ret += st[pos];
- 66 pos = to[pos];
- 67
- }
- 68
- return ret;
- 69
- }
- 70 71 signed main() {
- 72 // FRead();
- 73 int x,
- y;
- 74
- while (~Rint(n)) {
- 75 sz = sqrt(n);
- 76 Cls(st);
- Cls(to);
- 77 Rep(i, n) {
- 78 Rint(k[i]);
- 79 be[i] = i / sz;
- 80
- }
- 81
- for (int i = n - 1; i >= 0; i--) update(i, k[i]);
- 82 Rint(q);
- 83 W(q) {
- 84 Rint(cmd);
- 85
- if (cmd == 1) {
- 86 Rint(x);
- 87 printf("%d\n", query(x));
- 88
- }
- 89
- else {
- 90 Rint(x);
- Rint(y);
- 91 update(x, y);
- 92
- }
- 93
- }
- 94
- }
- 95 RT 0;
- 96
- }
来源: http://www.bubuko.com/infodetail-2118482.html