Advertisement
Guest User

Untitled

a guest
May 20th, 2018
128
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
text 3.98 KB | None | 0 0
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3. template <typename T>
  4. class SparseTable {
  5. public:
  6. vector<vector<int>> st;
  7. vector<T> values;
  8.  
  9. SparseTable(const vector<T> &a) {
  10. size = a.size();
  11. values = a;
  12. int k = 0;
  13. int p = 1;
  14. pows.resize(0);
  15. while (p <= a.size()) {
  16. pows.push_back(p);
  17. p *= 2;
  18. }
  19. pows.push_back(p);
  20. st.resize(a.size());
  21. for (int i = 0; i < a.size(); i++) {
  22. int j = 0;
  23. while (pows[j] < a.size() - i) {
  24. j++;
  25. }
  26. st[i].resize(j + 1);
  27. }
  28. rows.resize(st[0].size());
  29. rows.assign(rows.size(), 0);
  30. for (int i = 0; i < st.size(); i++) {
  31. for (int j = 0; j < st[i].size(); j++) {
  32. rows[j]++;
  33. }
  34. }
  35. for (int j = 0; j < st[0].size(); j++) {
  36. for (int i = 0; i < rows[j]; i++) {
  37. if (j == 0) {
  38. st[i][j] = i;
  39. }
  40. else {
  41. int t = min(j - 1, (int) st[i + pows[j - 1]].size() - 1);
  42. set<T> s;
  43. st[i][j] = (a[st[i][j - 1]] < a[st[i + pows[j - 1]][t]]) ? st[i][j - 1] : st[i + pows[j - 1]][t];
  44. }
  45. }
  46. }
  47. log2down.resize(a.size());
  48. for (int i = 0; i < a.size(); i++) {
  49. int j = 0;
  50. while (pows[j] <= i + 1) {
  51. j++;
  52. }
  53. log2down[i] = j - 1;
  54. }
  55. }
  56.  
  57. T getSMin(int l, int r) {
  58. int p = log2down[r - l];
  59. int ans;
  60. int i1 = st[l][p];
  61. int i2 = st[r - pows[p] + 1][p];
  62. ans = (values[i1] < values[i2]) ? i1 : i2;
  63. return ans;
  64. }
  65.  
  66. private:
  67. vector<int> pows;
  68. vector<int> log2down;
  69. vector<int> rows;
  70. int size;
  71.  
  72. };
  73.  
  74. class Tree {
  75. public:
  76. vector<int> depth;
  77. vector<vector<int>> g;
  78. vector<int> depth_dfs;
  79. vector<int> vrt_dfs;
  80. vector<int> ind_dfs;
  81. vector<int> values;
  82. int size;
  83. int countDeapth(int k) {
  84. if (depth[k] != -1)
  85. return depth[k];
  86. if (k == 0) {
  87. depth[k] = 0;
  88. return 0;
  89. }
  90. return depth[k] = countDeapth(values[k]) + 1;
  91. }
  92. void dfs(int v) {
  93. depth_dfs.push_back(depth[v]);
  94. vrt_dfs.push_back(v);
  95. if (ind_dfs[v] == -1) {
  96. ind_dfs[v] = vrt_dfs.size() - 1;
  97. }
  98. for (int i = 0; i < g[v].size(); i++) {
  99. dfs(g[v][i]);
  100. depth_dfs.push_back(depth[v]);
  101. vrt_dfs.push_back(v);
  102. }
  103. }
  104. Tree(vector<int> a) {
  105. size = a.size();
  106. depth.resize(size);
  107. depth.assign(size, -1);
  108. values = a;
  109. for (int i = 0; i < depth.size(); i++) {
  110. countDeapth(i);
  111. }
  112. g.resize(size);
  113. for (int i = 1; i < size; i++) {
  114. g[a[i]].push_back(i);
  115. }
  116. ind_dfs.resize(size);
  117. ind_dfs.assign(size, -1);
  118. depth_dfs.resize(0);
  119. vrt_dfs.resize(0);
  120. dfs(0);
  121. }
  122.  
  123. };
  124. int main() {
  125. int n, m;
  126. cin >> n >> m;
  127. vector<int> a(n);
  128. a[0] = 0;
  129. for (int i = 1; i < n; i++) {
  130. cin >> a[i];
  131. }
  132. Tree *t = new Tree(a);
  133. SparseTable<int> *st = new SparseTable<int>(t->depth_dfs);
  134. long long a1, a2;
  135. cin >> a1 >> a2;
  136. int x, y, z;
  137. cin >> x >> y >> z;
  138. int ans = 0;
  139. long long a0 = a1, b0 = a2;
  140. for (int i = 0; i < m; i++) {
  141. int i1 = t->ind_dfs[a1];
  142. int i2 = t->ind_dfs[a2];
  143. if (i1 > i2) {
  144. swap(i1, i2);
  145. }
  146. int ians = st->getSMin(i1, i2);
  147. long long d = t->vrt_dfs[ians];
  148. ans += d;
  149. a0 = (x * a0 + y * b0 + z) % n;
  150. b0 = (x * b0 + y * a0 + z) % n;
  151. a1 = (a0 + d) % n;
  152. a2 = b0;
  153. }
  154. cout << ans;
  155. delete t;
  156. delete st;
  157. return 0;
  158. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement