fork download
copy 
  1. package main
  2.  
  3. import (
  4. 	"bufio"
  5. 	"fmt"
  6. 	"os"
  7. )
  8.  
  9. type Node struct {
  10. 	l, r   *Node
  11. 	pr     uint32
  12. 	sz     int64
  13. 	isLeaf bool
  14. 	L, R   int
  15. }
  16.  
  17. var base []byte
  18. var rng uint32 = 123456789
  19.  
  20. func nextRand() uint32 {
  21. 	rng ^= rng << 13
  22. 	rng ^= rng >> 17
  23. 	rng ^= rng << 5
  24. 	return rng
  25. }
  26.  
  27. func sz(t *Node) int64 {
  28. 	if t == nil {
  29. 		return 0
  30. 	}
  31. 	return t.sz
  32. }
  33.  
  34. func pull(t *Node) {
  35. 	if t == nil {
  36. 		return
  37. 	}
  38. 	if t.isLeaf {
  39. 		t.sz = int64(t.R-t.L+1)
  40. 	} else {
  41. 		t.sz = sz(t.l) + sz(t.r)
  42. 	}
  43. }
  44.  
  45. func newLeaf(L, R int) *Node {
  46. 	n := &Node{pr: nextRand(), isLeaf: true, L: L, R: R}
  47. 	pull(n)
  48. 	return n
  49. }
  50.  
  51. func clone(t *Node) *Node {
  52. 	if t == nil {
  53. 		return nil
  54. 	}
  55. 	n := *t
  56. 	return &n
  57. }
  58.  
  59. func split(t *Node, k int64) (a, b *Node) {
  60. 	if t == nil {
  61. 		return nil, nil
  62. 	}
  63. 	if k <= 0 {
  64. 		return nil, t
  65. 	}
  66. 	if k >= sz(t) {
  67. 		return t, nil
  68. 	}
  69. 	if t.isLeaf {
  70. 		lenLeaf := int64(t.R - t.L + 1)
  71. 		if k >= lenLeaf {
  72. 			return t, nil
  73. 		}
  74. 		leftL := t.L
  75. 		leftR := t.L + int(k) - 1
  76. 		rightL := leftR + 1
  77. 		rightR := t.R
  78. 		return newLeaf(leftL, leftR), newLeaf(rightL, rightR)
  79. 	}
  80.  
  81. 	t2 := clone(t)
  82. 	if sz(t2.l) >= k {
  83. 		la, lb := split(t2.l, k)
  84. 		t2.l = lb
  85. 		pull(t2)
  86. 		return la, t2
  87. 	}
  88. 	ra, rb := split(t2.r, k-sz(t2.l))
  89. 	t2.r = ra
  90. 	pull(t2)
  91. 	return t2, rb
  92. }
  93.  
  94. func merge(a, b *Node) *Node {
  95. 	if a == nil {
  96. 		return b
  97. 	}
  98. 	if b == nil {
  99. 		return a
  100. 	}
  101. 	if a.pr < b.pr {
  102. 		a2 := clone(a)
  103. 		a2.r = merge(a2.r, b)
  104. 		pull(a2)
  105. 		return a2
  106. 	}
  107. 	b2 := clone(b)
  108. 	b2.l = merge(a, b2.l)
  109. 	pull(b2)
  110. 	return b2
  111. }
  112.  
  113. func kth(t *Node, k int64) byte {
  114. 	for {
  115. 		if t.isLeaf {
  116. 			return base[t.L+int(k)]
  117. 		}
  118. 		ls := sz(t.l)
  119. 		if k < ls {
  120. 			t = t.l
  121. 		} else {
  122. 			k -= ls
  123. 			t = t.r
  124. 		}
  125. 	}
  126. }
  127.  
  128. func main() {
  129. 	in := bufio.NewReader(os.Stdin)
  130. 	out := bufio.NewWriter(os.Stdout)
  131. 	defer out.Flush()
  132.  
  133. 	var n, q int
  134. 	fmt.Fscan(in, &n, &q)
  135.  
  136. 	var s string
  137. 	fmt.Fscan(in, &s)
  138. 	base = []byte(s)
  139.  
  140. 	root := newLeaf(0, n-1)
  141.  
  142. 	for ; q > 0; q-- {
  143. 		var tp int
  144. 		fmt.Fscan(in, &tp)
  145. 		if tp == 1 {
  146. 			var l, r int64
  147. 			fmt.Fscan(in, &l, &r)
  148.  
  149. 			if l > 0 {
  150. 				l--
  151. 			}
  152. 			if r > 0 {
  153. 				r--
  154. 			}
  155. 			if l < 0 {
  156. 				l = 0
  157. 			}
  158. 			if r >= sz(root) {
  159. 				r = sz(root) - 1
  160. 			}
  161. 			if r < l {
  162. 				continue
  163. 			}
  164.  
  165. 			A, B := split(root, l)
  166. 			M, C := split(B, r-l+1)
  167. 			root = merge(A, merge(M, merge(M, C)))
  168. 		} else {
  169. 			var i int64
  170. 			fmt.Fscan(in, &i)
  171.  
  172. 			if i > 0 {
  173. 				i--
  174. 			}
  175. 			if i < 0 {
  176. 				i = 0
  177. 			}
  178. 			if i >= sz(root) {
  179. 				i = sz(root) - 1
  180. 			}
  181.  
  182. 			fmt.Fprintln(out, string([]byte{kth(root, i)}))
  183. 		}
  184. 	}
  185. }
  186.  
Success #stdin #stdout 0s 5320KB
comments (?)
stdin
copy 
3 9
abc
2 1
2 2
2 3
1 2 3
2 1
2 2
2 3
2 4
2 5
stdout
copy 
a
b
c
b
c
c
c
c
https://ideone.com/E26xVa
language:
Go (go 1.12.1)
created:
1 day 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!