fork download 
  1. #include <cstdlib>
  2. #include <cmath>
  3. #include <iostream>
  4. #include <fstream>
  5. #include <algorithm>
  6. #include <cstdio>
  7.  
  8. #define rep(i, l, r) for(int i = l; i <= r; i++)
  9. #define down(i, l, r) for(int i = l; i >= r; i--)
  10. #define MS 234567
  11. #define MAX 1037471823
  12.  
  13. using namespace std;
  14.  
  15. int n, m, x, y, h[MS], l[MS], r[MS], ph[MS], k[MS], s[MS];
  16. bool rev[MS];
  17.  
  18. inline void Down(int x) 
  19. { if (rev[x]) { int k; k = l[x], l[x] = r[x], r[x] = k, rev[x]^=1, rev[l[x]]^=1, rev[r[x]]^=1; }  }
  20.  
  21. inline void Cal(int x) { if (!x) return; s[x] = s[l[x]] + s[r[x]] + 1; }
  22.  
  23. inline void Splay(int x)
  24. {
  25. 	if (!x) return; Down(x); int o=h[x];
  26. 	while (o)
  27. 	{
  28. 		if (rev[o]) { Down(o); Down(x); } if (!h[o]) ph[x] = ph[o], ph[o] = 0;
  29. 		if (l[o]==x) { l[h[o]]==o?l[h[o]]=x:r[h[o]]=x; h[x]=h[o]; l[o]=r[x]; h[r[x]]=o; h[o]=x; r[x]=o; Cal(o); }
  30. 		else { l[h[o]]==o?l[h[o]]=x:r[h[o]]=x; h[x]=h[o]; r[o]=l[x]; h[l[x]]=o; h[o]=x; l[x]=o; Cal(o); }
  31. 		o=h[x];
  32. 	}
  33. 	Cal(x);
  34. }
  35.  
  36. inline void Acc(int x)
  37. {
  38. 	int y; for(y = 0; x; y = x, x = ph[x])
  39. 		{ Splay(x); ph[r[x]]=x, h[r[x]]=0, r[x]=y; if (y) h[y]=x, ph[y]=0; Cal(x); }
  40. }
  41.  
  42. inline void Evert(int x) { Acc(x); Splay(x); rev[x]^=1; }
  43.  
  44. inline void Link(int x, int y) { Evert(x); Splay(x); ph[x] = y; }
  45.  
  46. inline void Cut(int x, int y) { Evert(x); Acc(y); Splay(y); l[y] = h[x] = 0; Cal(y); }
  47.  
  48. inline void Query(int x, int y) { Evert(x); Acc(y); Splay(y); printf("%d\n", s[y]-1); }
  49.  
  50. int main()
  51. {
  52. 	scanf("%d", &n);
  53. 	rep(i, 1, n) { scanf("%d", &x); if (i+x<=n) k[i] = i+x; else k[i] = n+1; Link(i, k[i]); }
  54. 	scanf("%d", &m);
  55. 	rep(i, 1, m)
  56. 	{
  57. 		scanf("%d", &x);
  58. 		if (x == 1) { scanf("%d", &x); x++; Query(n+1, x); }
  59. 		else 
  60. 		{ 
  61. 			scanf("%d%d", &x, &y); x++; Cut(x, k[x]); 
  62. 			if (x+y<=n) k[x] = x+y; else k[x] = n+1; Link(x, k[x]); 
  63. 		}
  64. 	}
  65. 	return 0;
  66. }
Success #stdin #stdout 0s 9072KB
comments (?)
stdin 
Standard input is empty
stdout 
Standard output is empty
https://ideone.com/82HiF3
BZOJ 2002 LCT
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!