Advertisement
bibaboba12345

Untitled

Jan 8th, 2023
73
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
text 5.12 KB | None | 0 0
  1. #define _CRT_SECURE_NO_WARNINGS
  2. #include <iostream>
  3. #include <bitset>
  4. #include <vector>
  5. #include <algorithm>
  6. #include <map>
  7. #include <set>
  8. #include <cassert>
  9. #define int long long
  10. const int N = 2e5 + 7, A = 26, MOD = 1e9+7;
  11. using namespace std;
  12.  
  13. long long binpow(long long a, int step) {
  14. if (step == 0) {
  15. return 1;
  16. }
  17. long long h = binpow(a, step / 2);
  18. h = (h * h) % MOD;
  19. if (step & 1) {
  20. h = (h * a) % MOD;
  21. }
  22. return h;
  23. }
  24.  
  25. struct Node {
  26. int cnt[A];
  27. int push;
  28. Node() {
  29. for (int i = 0; i < A; i++) {
  30. cnt[i] = 0;
  31. }
  32. push = 0;
  33. }
  34. void move(int k) {
  35. k = k % A;
  36. int new_cnt[A];
  37. for (int i = 0; i < A; i++) {
  38. int prev = (i - k + A) % A;
  39. new_cnt[i] = cnt[prev];
  40. }
  41. swap(cnt, new_cnt);
  42. }
  43. };
  44.  
  45. Node merge(Node& a, Node& b) {
  46. Node x;
  47. for (int i = 0; i < A; i++) {
  48. x.cnt[i] = a.cnt[i] + b.cnt[i];
  49. }
  50. x.push = 0;
  51. return x;
  52. }
  53.  
  54. int global_cnt[A];
  55.  
  56.  
  57.  
  58. struct SegmentTree {
  59. vector<Node> tree;
  60. void build(string s) {
  61. int h = 1;
  62. while (h < s.size()) {
  63. h *= 2;
  64. }
  65. h *= 2;
  66. tree.resize(h);
  67. for (int i = h - 1; i >= 1; i--) {
  68. if (i - h / 2 >= 0) {
  69. tree[i] = Node();
  70. if (i - h/2 < s.size()) {
  71. tree[i].cnt[s[i - h/2] - 'a']++;
  72. }
  73. }
  74. else {
  75. tree[i] = merge(tree[i * 2], tree[i * 2 + 1]);
  76. }
  77. }
  78. }
  79. void recalc(int v) {
  80. v /= 2;
  81. while (v > 0) {
  82. tree[v] = merge(tree[v * 2], tree[v * 2 + 1]);
  83. v /= 2;
  84. }
  85. }
  86. void push(int v) {
  87. if (tree[v].push == 0 || v * 2 + 1 >= tree.size()) {
  88. return;
  89. }
  90. tree[v * 2].move(tree[v].push);
  91. tree[v * 2 + 1].move(tree[v].push);
  92. tree[v * 2].push += tree[v].push;
  93. tree[v * 2 + 1].push += tree[v].push;
  94. tree[v].push = 0;
  95. }
  96. void add(int v, int l, int r, int L, int R, int x) {
  97. push(v);
  98. if (L > r || R < l) {
  99. return;
  100. }
  101. push(v);
  102. if (L >= l && R <= r) {
  103. tree[v].move(x);
  104. tree[v].push += x;
  105. recalc(v);
  106. return;
  107. }
  108. push(v);
  109. add(v * 2, l, r, L, (L + R) / 2, x);
  110. push(v);
  111. add(v * 2 + 1, l, r, (L+R)/2+1, R, x);
  112. }
  113. void Add(int l, int r, int x) {
  114. add(1, l, r, 1, tree.size() / 2, x);
  115. }
  116. void get(int v, int l, int r, int L, int R) {
  117. push(v);
  118. if (L > r || R < l) {
  119. return;
  120. }
  121. push(v);
  122. if (L >= l && R <= r) {
  123. for (int i = 0; i < A; i++) {
  124. global_cnt[i] += tree[v].cnt[i];
  125. }
  126. push(v);
  127. return;
  128. }
  129. push(v);
  130. get(v * 2, l, r, L, (L + R) / 2);
  131. push(v);
  132. get(v * 2 + 1, l, r, (L + R) / 2 + 1, R);
  133. }
  134. void Get(int l, int r) {
  135. for (int i = 0; i < A; i++) {
  136. global_cnt[i] = 0;
  137. }
  138. get(1, l, r, 1, tree.size() / 2);
  139. }
  140. };
  141. SegmentTree ST;
  142.  
  143. int n, q;
  144. int bp[A];
  145. string s;
  146.  
  147. signed main()
  148. {
  149. #ifdef _DEBUG
  150. freopen("input.txt", "r", stdin);
  151. #else
  152. std::ios::sync_with_stdio(false);
  153. cin.tie(0);
  154. #endif
  155. cin >> n >> q;
  156. cin >> s;
  157. ST.build(s);
  158. for (int I = 0; I < q; I++) {
  159. int t;
  160. cin >> t;
  161. if (t == 1) {
  162. int l,r, k;
  163. cin >> l >> r >> k;
  164. l++;
  165. r++;
  166. ST.Add(l, r, k);
  167. }
  168. else {
  169. int l,r;
  170. cin >> l >> r;
  171. l++;
  172. r++;
  173. ST.Get(l, r);
  174. long long ans = 0;
  175. long long chet = 1;
  176. long long nechet = 0;
  177. for (int i = 0; i < A; i++) {
  178. if (global_cnt[i] != 0) {
  179. bp[i] = binpow(2, global_cnt[i] - 1); // чтобы 2 раза не считать потом
  180. chet *= bp[i];
  181. chet %= MOD;
  182. }
  183. }
  184. ans += chet - 1; // исключая пустую строку - всех взято по 0
  185. for (int i = 0; i < A; i++) {
  186. if (global_cnt[i] == 0) {
  187. continue;
  188. }
  189. long long except = 1;
  190. for (int j = 0; j < A; j++) {
  191. if (global_cnt[j] != 0 && j != i) {
  192. except *= bp[j];
  193. except %= MOD;
  194. }
  195. }
  196. long long t_ans = (except % MOD);
  197. if (global_cnt[i] >= 2) {
  198. t_ans *= binpow(2, global_cnt[i] - 1);
  199. t_ans %= MOD;
  200. }
  201. nechet += t_ans;
  202. nechet %= MOD;
  203. }
  204. ans += nechet;
  205. ans %= MOD;
  206. cout << ans << "\n";
  207. }
  208. }
  209. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement