rmq

Untitled

rmq
Apr 29th, 2015
224
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. #include <iostream>
  2. #include <fstream>
  3. #include <cstdlib>
  4. #include <algorithm>
  5. #include <set>
  6. #include <queue>
  7. #include <map>
  8. #include <unordered_map>
  9. #include <unordered_set>
  10. #include <cstdio>
  11. #include <cassert>
  12. #include <climits>
  13. #include <vector>
  14. #include <cstring>
  15.  
  16. using namespace std;
  17.  
  18. namespace IO {
  19.  
  20. /** Defines */
  21.  
  22. #define ENDLINE writeWord("\n")
  23. #define SPACE writeWord(" ")
  24.  
  25. /** Interface */
  26.  
  27. template <class T = int>
  28. inline T readInt(); // skip spaces, read signed int
  29. inline int readUInt(); // skip spaces, read unsigned int
  30. inline int readChar(); // skip spaces, read char
  31. inline void readWord( char *s ); // skip spaces, read word
  32.  
  33. template <class T>
  34. inline void writeInt( T x );
  35. inline void writeChar( int x ); // you may use putchar() instead of it
  36. inline void writeWord( const char *s );
  37. inline void flush();
  38.  
  39. /** Read */
  40.  
  41. static const int buf_size = 4096;
  42.  
  43. inline char getchar_fast() { // you may use getchar() instead of it
  44. static char buf[buf_size];
  45. static int len = 0, pos = 0;
  46. if (pos == len)
  47. pos = 0, len = fread(buf, 1, buf_size, stdin);
  48. if (pos == len)
  49. return -1;
  50. return buf[pos++];
  51. }
  52.  
  53. inline int readChar() {
  54. int c = getchar_fast();
  55. while ((c < 32 || c > 126) && c != -1)
  56. c = getchar_fast();
  57. return c;
  58. }
  59.  
  60. inline int readUInt() {
  61. int c = readChar(), x = 0;
  62. while ('0' <= c && c <= '9')
  63. x = x * 10 + c - '0', c = getchar_fast();
  64. return x;
  65. }
  66.  
  67. template <class T>
  68. inline T readInt() {
  69. int s = 1, c = readChar();
  70. T x = 0;
  71. if (c == '-')
  72. s = -1, c = getchar_fast();
  73. while ('0' <= c && c <= '9')
  74. x = x * 10 + c - '0', c = getchar_fast();
  75. return s == 1 ? x : -x;
  76. }
  77.  
  78. inline void readWord( char *s ) {
  79. int c = readChar();
  80. while (c >= 32 && c <= 126)
  81. *s++ = c, c = getchar_fast();
  82. *s = 0;
  83. }
  84.  
  85. /** Write */
  86.  
  87. static int write_pos = 0;
  88. static char write_buf[buf_size];
  89.  
  90. inline void writeChar( int x ) {
  91. if (write_pos == buf_size)
  92. fwrite(write_buf, 1, buf_size, stdout), write_pos = 0;
  93. write_buf[write_pos++] = x;
  94. }
  95.  
  96. inline void flush() {
  97. if (write_pos)
  98. fwrite(write_buf, 1, write_pos, stdout), write_pos = 0;
  99. }
  100.  
  101. template <class T>
  102. inline void writeInt( T x ) {
  103. if (x < 0)
  104. writeChar('-'), x = -x;
  105. char s[24];
  106. int n = 0;
  107. while (x || !n)
  108. s[n++] = '0' + x % 10, x /= 10;
  109. while (n--)
  110. writeChar(s[n]);
  111. }
  112.  
  113. inline void writeWord( const char *s ) {
  114. while (*s)
  115. writeChar(*s++);
  116. }
  117.  
  118. } //namespace IO
  119.  
  120. #define LP(i,s,f) for(sz_t i = s; i <= f; i++)
  121. #define FORN(i,n) for(sz_t i = 0; i < n; i++)
  122. #define BLP(i,s,f) for(sz_t i= s; i >= f; i--)
  123. #define PB push_back
  124. #define MP make_pair
  125. #define SZ(a) ((sz_t)(a.size()))
  126. #define ALL(c) c.begin(),c.end()
  127. #define FT first
  128. #define SD second
  129.  
  130. typedef long long hash_t;
  131. typedef int sz_t;
  132. const hash_t P = 31;
  133. const hash_t M = 1000000000 + 7;
  134. const sz_t INF = 1000000000 + 7;
  135.  
  136. hash_t MOD(hash_t val){
  137. if (val < 0){
  138. return val + M;
  139. } else {
  140. return val % M;
  141. }
  142. }
  143.  
  144. class HashStr
  145. {
  146. private:
  147. char *ptr;
  148. sz_t size;
  149. vector<hash_t> *h, *deg;
  150. public:
  151. HashStr(char *raw_ptr, sz_t raw_size) : ptr(raw_ptr), size(raw_size){
  152. h = new vector<hash_t>;
  153. deg = new vector<hash_t>;
  154. h->reserve(size + 1);
  155. deg->reserve(size + 1);
  156. (*h)[0] = 0;
  157. (*deg)[0] = 1;
  158. FORN(i, size){
  159. (*deg)[i + 1] = MOD((*deg)[i] * P);
  160. (*h)[i + 1] = MOD(MOD((*h)[i] * P) + (ptr[i] - 'a' + 1));
  161. }
  162. };
  163. ~HashStr(){
  164. delete h;
  165. delete deg;
  166. };
  167. hash_t GetHash(sz_t l, sz_t r){
  168. return MOD((*h)[r + 1] - MOD((*h)[l] * (*deg)[r - l + 1]));
  169. };
  170. };
  171.  
  172. class ZFuncStr
  173. {
  174. private:
  175. char *ptr;
  176. sz_t size;
  177. vector<sz_t>* z;
  178. public:
  179. ZFuncStr(char *raw_ptr, int raw_size) : ptr(raw_ptr), size(raw_size){
  180. z = new vector<sz_t>;
  181. z->assign(size, 0);
  182. sz_t l = 0, r = 0;
  183. (*z)[0] = 0;
  184. LP(i, 1, size - 1){
  185. if (i <= r){
  186. (*z)[i] = min(r - i + 1, (*z)[i - l]);
  187. }
  188. while(i + (*z)[i] < size && ptr[(*z)[i]] == ptr[i + (*z)[i]]){
  189. (*z)[i]++;
  190. }
  191. if (i + (*z)[i] - 1 > r){
  192. l = i;
  193. r = i + (*z)[i] - 1;
  194. }
  195. }
  196. };
  197. ~ZFuncStr(){
  198. delete z;
  199. };
  200. hash_t GetZFunc(int i){
  201. return (*z)[i];
  202. };
  203. };
  204.  
  205. struct Vertex{
  206. static const sz_t k = 26;
  207. sz_t go[k], cnt;
  208. bool isTerm;
  209. Vertex(){
  210. fill(go, go + k, -1);
  211. cnt = 0;
  212. isTerm = false;
  213. }
  214. };
  215.  
  216. vector<Vertex> bohr(1);
  217. const char e = 'a';
  218.  
  219. void addString(char *str, sz_t len){
  220. sz_t v = 0;
  221. FORN(i, len){
  222. bohr[v].cnt++;
  223. sz_t c = str[i] - e;
  224. if (bohr[v].go[c] == -1){
  225. bohr[v].go[c] = SZ(bohr);
  226. bohr.PB(Vertex());
  227. }
  228. v = bohr[v].go[c];
  229. }
  230. bohr[v].cnt++;
  231. bohr[v].isTerm = true;
  232. }
  233.  
  234. void writeKth(sz_t k){
  235. sz_t v = 0;
  236. while(k > 0){
  237. if (k == 1 && bohr[v].isTerm){
  238. k -= 1;
  239. }else {
  240. sz_t sk = sz_t(bohr[v].isTerm), i = -1;
  241. while(sk < k){
  242. i++;
  243. sz_t child = bohr[v].go[i];
  244. if (child != -1){
  245. sk += bohr[child].cnt;
  246. }
  247. }
  248. sk -= bohr[bohr[v].go[i]].cnt;
  249. IO::writeChar(char('a' + i));
  250. v = bohr[v].go[i];
  251. k -= sk;
  252. }
  253. }
  254. }
  255.  
  256. sz_t n, x, l;
  257. char s[100000];
  258.  
  259. int main(){
  260. #define filename "kthstr"
  261. assert(freopen(filename ".in", "r", stdin));
  262. assert(freopen(filename ".out", "w", stdout));
  263. n = IO::readInt();
  264. FORN(i, n){
  265. IO::readWord(s);
  266. if (s[0] >= '0' && s[0] <= '9'){
  267. x = atoi(s);
  268. writeKth(x);
  269. IO::ENDLINE;
  270. }else {
  271. l = strlen(s);
  272. addString(s, l);
  273. }
  274. }
  275. IO::flush();
  276. }
RAW Paste Data