1 #include <cstdio>
 2 #include <iostream>
 3 #include <cstdlib>
 4 #include <algorithm>
 5 #include <cstring>
 6 #include <cmath>
 7 using namespace std;
 8 const int N = 300010;
 9 struct SPLAY {
10     SPLAY* ch[2];
11     SPLAY* pre;
12     int size;
13     SPLAY() {
14         ch[0] = ch[1] = pre = NULL;
15         size = 0;
16     }
17     void update() {
18         size = 1;
19         if(ch[0]!=NULL) size += ch[0]->size;
20         if(ch[1]!=NULL) size += ch[1]->size;
21     }
22 }*dian[N],dizhi[N];
23 bool is_root(SPLAY* x) {
24     if(x->pre==NULL) return true;
25     if((x->pre->ch[0]==NULL || x->pre->ch[0]!=x) && (x->pre->ch[1]==NULL || x->pre->ch[1]!=x)) return true;
26     return false;
27 }
28 inline void rotate(SPLAY* x,int d) {
29     SPLAY* y = x->pre;
30     y->ch[!d] = x->ch[d];
31     if(x->ch[d]!=NULL) x->ch[d]->pre = y;
32     x->pre = y->pre;
33     if(!is_root(y)) {
34         if(y==y->pre->ch[d]) y->pre->ch[d] = x;
35         else y->pre->ch[!d] = x;
36     }
37     x->ch[d] = y;y->pre = x;
38     y->update() ; x->update();
39 }
40 inline void splay(SPLAY* x) {
41     while(!is_root(x)) {
42         SPLAY* y = x->pre;
43         if(x==y->ch[0]) {
44             if(!is_root(y) && y->pre->ch[0]==y) rotate(y,1);
45             rotate(x,1);
46         } else {
47             if(!is_root(y) && y->pre->ch[1]==y) rotate(y,0);
48             rotate(x,0);
49         }
50     }
51 }
52 int n,m,t;
53 inline void access(SPLAY* x) {
54     for(splay(x),x->ch[1] = NULL ; x->pre!=NULL ; splay(x),x->ch[1] = NULL) {
55         splay(x->pre);
56         x->pre->ch[1] = x;
57     }
58 }
59 inline int query(int x) {
60     access(dian[x]);
61     splay(dian[x]);
62     return dian[x]->ch[0]->size;
63 }
64 int fa[N];
65 inline void modify(int x,int y) {
66     int to = x+y>n?n+1:x+y;
67     access(dian[fa[x]]);
68     splay(dian[x]);
69     dian[x]->pre = dian[to];
70     fa[x] = to;
71 }
72 int main() {
73     scanf("%d",&n);
74     for(int i = 1 ; i <= n+1 ; ++i) dian[i] = &dizhi[++t];
75     for(int i = 1 ; i <= n ; ++i) {
76         int x;
77         scanf("%d",&x);
78         if(i+x>n) dian[i]->pre = dian[n+1],fa[i] = n + 1;
79         else dian[i]->pre = dian[i+x],fa[i] = i + x;
80     }
81     scanf("%d",&m);
82     for(int i = 1 ; i <= m ; ++i) {
83         int k,x,y;
84         scanf("%d",&k);
85         if(k==1) {
86             scanf("%d",&x);
87             x++;
88             printf("%d\n",query(x));
89         } else {
90             scanf("%d%d",&x,&y);
91             x++;
92             modify(x,y);
93         }
94     }
95 } 

View Code

优质内容筛选与推荐>>
1、第3章 Linux常用命令（6）_关机重启命令
2、任务03——简单程序测试及 GitHub Issues 的使用
3、算法笔记_078:蓝桥杯练习 最大最小公倍数（Java）
4、js中返回上一页失效的解决办法
5、UIView 的图层关系