Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #define _CRT_SECURE_NO_WARNINGS
- #include <iostream>
- #include <bitset>
- #include <vector>
- #include <algorithm>
- #include <map>
- #include <set>
- #include <cassert>
- #define int long long
- const int N = 2e5 + 7, A = 26, MOD = 1e9+7;
- using namespace std;
- long long binpow(long long a, int step) {
- if (step == 0) {
- return 1;
- }
- long long h = binpow(a, step / 2);
- h = (h * h) % MOD;
- if (step & 1) {
- h = (h * a) % MOD;
- }
- return h;
- }
- struct Node {
- int cnt[A];
- int push;
- Node() {
- for (int i = 0; i < A; i++) {
- cnt[i] = 0;
- }
- push = 0;
- }
- void move(int k) {
- k = k % A;
- int new_cnt[A];
- for (int i = 0; i < A; i++) {
- int prev = (i - k + A) % A;
- new_cnt[i] = cnt[prev];
- }
- swap(cnt, new_cnt);
- }
- };
- Node merge(Node& a, Node& b) {
- Node x;
- for (int i = 0; i < A; i++) {
- x.cnt[i] = a.cnt[i] + b.cnt[i];
- }
- x.push = 0;
- return x;
- }
- int global_cnt[A];
- struct SegmentTree {
- vector<Node> tree;
- void build(string s) {
- int h = 1;
- while (h < s.size()) {
- h *= 2;
- }
- h *= 2;
- tree.resize(h);
- for (int i = h - 1; i >= 1; i--) {
- if (i - h / 2 >= 0) {
- tree[i] = Node();
- if (i - h/2 < s.size()) {
- tree[i].cnt[s[i - h/2] - 'a']++;
- }
- }
- else {
- tree[i] = merge(tree[i * 2], tree[i * 2 + 1]);
- }
- }
- }
- void recalc(int v) {
- v /= 2;
- while (v > 0) {
- tree[v] = merge(tree[v * 2], tree[v * 2 + 1]);
- v /= 2;
- }
- }
- void push(int v) {
- if (tree[v].push == 0 || v * 2 + 1 >= tree.size()) {
- return;
- }
- tree[v * 2].move(tree[v].push);
- tree[v * 2 + 1].move(tree[v].push);
- tree[v * 2].push += tree[v].push;
- tree[v * 2 + 1].push += tree[v].push;
- tree[v].push = 0;
- }
- void add(int v, int l, int r, int L, int R, int x) {
- push(v);
- if (L > r || R < l) {
- return;
- }
- push(v);
- if (L >= l && R <= r) {
- tree[v].move(x);
- tree[v].push += x;
- recalc(v);
- return;
- }
- push(v);
- add(v * 2, l, r, L, (L + R) / 2, x);
- push(v);
- add(v * 2 + 1, l, r, (L+R)/2+1, R, x);
- }
- void Add(int l, int r, int x) {
- add(1, l, r, 1, tree.size() / 2, x);
- }
- void get(int v, int l, int r, int L, int R) {
- push(v);
- if (L > r || R < l) {
- return;
- }
- push(v);
- if (L >= l && R <= r) {
- for (int i = 0; i < A; i++) {
- global_cnt[i] += tree[v].cnt[i];
- }
- push(v);
- return;
- }
- push(v);
- get(v * 2, l, r, L, (L + R) / 2);
- push(v);
- get(v * 2 + 1, l, r, (L + R) / 2 + 1, R);
- }
- void Get(int l, int r) {
- for (int i = 0; i < A; i++) {
- global_cnt[i] = 0;
- }
- get(1, l, r, 1, tree.size() / 2);
- }
- };
- SegmentTree ST;
- int n, q;
- int bp[A];
- string s;
- signed main()
- {
- #ifdef _DEBUG
- freopen("input.txt", "r", stdin);
- #else
- std::ios::sync_with_stdio(false);
- cin.tie(0);
- #endif
- cin >> n >> q;
- cin >> s;
- ST.build(s);
- for (int I = 0; I < q; I++) {
- int t;
- cin >> t;
- if (t == 1) {
- int l,r, k;
- cin >> l >> r >> k;
- l++;
- r++;
- ST.Add(l, r, k);
- }
- else {
- int l,r;
- cin >> l >> r;
- l++;
- r++;
- ST.Get(l, r);
- long long ans = 0;
- long long chet = 1;
- long long nechet = 0;
- for (int i = 0; i < A; i++) {
- if (global_cnt[i] != 0) {
- bp[i] = binpow(2, global_cnt[i] - 1); // чтобы 2 раза не считать потом
- chet *= bp[i];
- chet %= MOD;
- }
- }
- ans += chet - 1; // исключая пустую строку - всех взято по 0
- for (int i = 0; i < A; i++) {
- if (global_cnt[i] == 0) {
- continue;
- }
- long long except = 1;
- for (int j = 0; j < A; j++) {
- if (global_cnt[j] != 0 && j != i) {
- except *= bp[j];
- except %= MOD;
- }
- }
- long long t_ans = (except % MOD);
- if (global_cnt[i] >= 2) {
- t_ans *= binpow(2, global_cnt[i] - 1);
- t_ans %= MOD;
- }
- nechet += t_ans;
- nechet %= MOD;
- }
- ans += nechet;
- ans %= MOD;
- cout << ans << "\n";
- }
- }
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement