fork download 
  1. #include <iostream>
  2. #include <cstdio>
  3. using namespace std;
  4. #define REP_1(i, n) for (int i=1;i<=int(n);++i)
  5. #define REP_1_C(i, n) for (int n____=int(n),i=1;i<=n____;++i)
  6. #define DO(N) while (N--)
  7. #define DO_C(n) int n____ = n; while(n____--)
  8. template<class T> inline void RD(T &x){char c; for (c = getchar(); c < '0'; c = getchar()); x = c - '0'; for (c = getchar(); c >= '0'; c = getchar()) x = x * 10 + c - '0';}
  9. inline int RD(){ int x; RD(x); return x;}
  10. template<class T> inline T& _RD(T &x){ RD(x); return x;}
  11. template<class T0, class T1> inline void RD(T0 &x0, T1 &x1){RD(x0), RD(x1);}
  12. template<class T> inline void OT(const T &x){printf("%d\n", x);}
  13.  
  14. /* .................................................................................................................................. */
  15. const int N = 200001;
  16.  
  17. int l[N], r[N], p[N], sz[N]; bool rt[N] = {true};
  18. int n, ans;
  19.  
  20. #define lx l[x]
  21. #define rx r[x]
  22.  
  23. inline void Set(int l[], int y, int x){
  24.     l[y] = x, p[x] = y;
  25. }
  26.  
  27. inline void Rotate(int x){
  28.     int y = p[x], z = p[y];
  29.  
  30.     if (!rt[y]) Set(y == l[z] ? l : r, z, x);
  31.     else p[x] = z;
  32.  
  33.     if (x == l[y]){
  34.         Set(l, y, rx), Set(r, x, y);
  35.         sz[y] -= sz[x];
  36.     }
  37.     else {
  38.         Set(r, y, lx), Set(l, x, y);
  39.         sz[x] += sz[y];
  40.     }
  41.  
  42.     if (rt[y]) rt[y] = false, rt[x] = true;
  43. }
  44.  
  45. inline void Splay(int x){
  46.     while (!rt[x]) Rotate(x);
  47. }
  48.  
  49. void Access(int _x){
  50.     int x = _x, y = 0;
  51.     do{
  52.         Splay(x), rt[r[x]] = true, rt[r[x] = y] = false;
  53.         x = p[y = x];
  54.     } while (x);
  55.  
  56.     Splay(_x);
  57. }
  58.  
  59. void Link(int x, int y){
  60.     Access(x), rt[l[x]] = true, sz[x] = 1;
  61.     lx = p[lx] =  0, p[x] = y;
  62.     Access(x);
  63. }
  64.  
  65. void init(){
  66.     REP_1_C(i, _RD(n)) sz[i] = 1, rt[i] = true;
  67.     int k; REP_1(i, n){
  68.         RD(k); if (i + k <= n) p[i] = i + k;
  69.     }
  70. }
  71.  
  72.  
  73. int main(){
  74.     //freopen("in.txt", "r", stdin);
  75.     //freopen("out.txt", "w", stdout);
  76.     //ios::sync_with_stdio(false);
  77.  
  78.     init();
  79.  
  80.     int cmd, x, k;
  81.     DO_C(RD()){
  82.  
  83.         RD(cmd, x), ++x;
  84.         if (cmd == 1){
  85.             Access(x), OT(sz[x]);
  86.         }
  87.         else {
  88.             RD(k);
  89.             if (x + k <= n) Link(x, x+k);
  90.             else Link(x, 0);
  91.         }
  92.     }
  93. }
  94.  
Success #stdin #stdout 0s 6048KB
comments (?)
stdin 
4                              

1 2 1 1						   

3

1 1

2 1 1

1 1
stdout 
2
3
https://ideone.com/xjFsR
language:
C++ (gcc 8.3)
created:
14 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!