Header Ad

HackerEarth Benny and String problem solution

YASH PAL October 23, 2021
In this HackerEarth Benny and String problem solution, Benny loves strings! She also loves to play with strings and make different queries on them.

In this problem, Benny has a string s of length n consisting of lowercase Latin letters.

Let's define the next letter for every lowercase Latin letter. For letters from 'a' to 'y' next letter is next to one in the Latin alphabet, and for 'z' the next one is 'a'.

Let's call the rotation of letter is when we replace it with the next one.

You have to answer the following queries about the string s:
  1. ? l r c — where c is lowercase Latin letter, (1 <= l <= r <= n). You have to output the length of the largest sequence consisting of consecutive letters c in s[l,r], where s[l,r] — is the substring of string s starting with sl and ending with sr.
  2. + l r x — you have to rotate every letter in s[l,r] exactly x times, (1 <= l <= r <= n), (0 <= x <= 10^9).
  3. * i c — set si equal to c, where c is some Latin lowercase letter, (1 <= i <= n).
  4. - i x — set si equal to its value before processing the x-th query, (1 <= i <= n), (1 <= x <= j), where j is the index of current query. All queries are indexed starting with 1.


HackerEarth Benny and String problem solution


HackerEarth Benny and String problem solution.

#include <iostream>
#include <stdio.h>
#include <algorithm>
#include <cmath>
#include <cstring>
#include <vector>
#include <iomanip>
#include <set>
#include <map>
  
using namespace std;
  
#define pb push_back
#define mp make_pair
#define F first
#define S second

const int N = 200500;

int n, q;
char c[N];
char s[N];
char type[N];
int l[N], r[N], x[N], id[N];
vector<int> ids[N];
map<int, char> have[N];

struct TreeNode {
    int answer[26];
    int sz;
    int pref_char, suff_char;
    int pref_len, suff_len;
    int to_push;
    TreeNode () {
        for (int i = 0; i < 26; i++) {
            answer[i] = 0;
        }
        sz = pref_char = suff_char = pref_len = suff_len = to_push = 0;
    }
} tree[4 * N];

TreeNode combine(TreeNode a, TreeNode b) {
    if (a.sz == 0) {
        return b;
    }
    if (b.sz == 0) {
        return a;
    }
    TreeNode c;
    c.to_push = 0;
    c.sz = a.sz + b.sz;
    for (int i = 0; i < 26; i++) {
        c.answer[i] = max(a.answer[i], b.answer[i]);
    }
    c.pref_char = a.pref_char;
    c.suff_char = b.suff_char;
    c.pref_len = a.pref_len;
    c.suff_len = b.suff_len;
    if (a.suff_char == b.pref_char) {
        c.answer[a.suff_char] = max(c.answer[a.suff_char], a.suff_len + b.pref_len);
    }
    if (a.pref_len == a.sz && a.pref_char == b.pref_char) {
        c.pref_len += b.pref_len;
        c.answer[a.pref_char] = max(c.answer[a.pref_char], a.pref_len + b.pref_len);
    }
    if (b.suff_len == b.sz && a.suff_char == b.pref_char) {
        c.suff_len += a.suff_len;
        c.answer[b.suff_char] = max(c.answer[b.suff_char], a.suff_len + b.suff_len);
    }
    return c;
}

void add(int &x, int y) {
    x += y;
    x %= 26;
}

int tmp_array[26];

void make_push(int ver, int l, int r) {
    if (tree[ver].to_push == 0) {
        return;
    }
    add(tree[ver + ver].to_push, tree[ver].to_push);
    add(tree[ver + ver + 1].to_push, tree[ver].to_push);
    add(tree[ver + ver].pref_char, tree[ver].to_push);
    add(tree[ver + ver].suff_char, tree[ver].to_push);
    add(tree[ver + ver + 1].pref_char, tree[ver].to_push);
    add(tree[ver + ver + 1].suff_char, tree[ver].to_push);
    for (int i = 0; i < 26; i++) {
        tmp_array[(i + tree[ver].to_push) % 26] = tree[ver + ver].answer[i];
    }
    for (int i = 0; i < 26; i++) {
        tree[ver + ver].answer[i] = tmp_array[i];
    }
    for (int i = 0; i < 26; i++) {
        tmp_array[(i + tree[ver].to_push) % 26] = tree[ver + ver + 1].answer[i];
    }
    for (int i = 0; i < 26; i++) {
        tree[ver + ver + 1].answer[i] = tmp_array[i];
    }
    tree[ver].to_push = 0;
}

void build(int ver, int l, int r) {
    if (l == r) {
        tree[ver].answer[s[l] - 'a'] = 1;
        tree[ver].pref_char = tree[ver].suff_char = s[l] - 'a';
        tree[ver].pref_len = tree[ver].suff_len = 1;
        tree[ver].to_push = 0;
        tree[ver].sz = 1;
        return;
    }
    int mid = (l + r) >> 1;
    build(ver + ver, l, mid);
    build(ver + ver + 1, mid + 1, r);
    tree[ver] = combine(tree[ver + ver], tree[ver + ver + 1]);
}

void update(int ver, int l, int r, int pl, int pr, int add) {
    if (pl > pr) {
        return;
    }
    if (l == pl && r == pr) {
        (tree[ver].to_push += add) %= 26;
        for (int i = 0; i < 26; i++) {
            tmp_array[(i + add) % 26] = tree[ver].answer[i];
        }
        for (int i = 0; i < 26; i++) {
            tree[ver].answer[i] = tmp_array[i];
        }
        (tree[ver].pref_char += add) %= 26;
        (tree[ver].suff_char += add) %= 26;
        return;
    }
    int mid = (l + r) >> 1;
    make_push(ver, l, r);
    update(ver + ver, l, mid, pl, min(pr, mid), add);
    update(ver + ver + 1, mid + 1, r, max(pl, mid + 1), pr, add);
    tree[ver] = combine(tree[ver + ver], tree[ver + ver + 1]);
}

char getCharacter(int ver, int l, int r, int pos) {
    if (l == r) {
        return (char)('a' + tree[ver].pref_char);
    }
    int mid = (l + r) >> 1;
    make_push(ver, l, r);
    char result = '$';
    if (pos <= mid) {
        result = getCharacter(ver + ver, l, mid, pos);
    } else {
        result = getCharacter(ver + ver + 1, mid + 1, r, pos);
    }
    tree[ver] = combine(tree[ver + ver], tree[ver + ver + 1]);
    return result;
}

void setValue(int ver, int l, int r, int pos, char value) {
    if (l == r) {
        tree[ver] = TreeNode();
        tree[ver].sz = 1;
        tree[ver].answer[value - 'a'] = 1;
        tree[ver].pref_char = tree[ver].suff_char = value - 'a';
        tree[ver].pref_len = tree[ver].suff_len = 1;
        tree[ver].to_push = 0;
        return;
    }
    int mid = (l + r) >> 1;
    make_push(ver, l, r);
    if (pos <= mid) {
        setValue(ver + ver, l, mid, pos, value);
    } else {
        setValue(ver + ver + 1, mid + 1, r, pos, value);
    }
    tree[ver] = combine(tree[ver + ver], tree[ver + ver + 1]);
}

TreeNode get(int ver, int l, int r, int pl, int pr) {
    if (pl > pr) {
        return TreeNode();
    }
    make_push(ver, l, r);
    if (l == pl && r == pr) {
        return tree[ver];
    }
    int mid = (l + r) >> 1;
    TreeNode result = get(ver + ver, l, mid, pl, min(pr, mid));
    result = combine(result, get(ver + ver + 1, mid + 1, r, max(pl, mid + 1), pr));
    tree[ver] = combine(tree[ver + ver], tree[ver + ver + 1]);
    return result;
}

int main() {
    scanf("%d%d\n", &n, &q);
    gets(s + 1);
    for (int i = 1; i <= q; i++) {
        scanf("%c", &type[i]);
        if (type[i] == '?') {
            scanf("%d%d %c", &l[i], &r[i], &c[i]);
        } else if (type[i] == '+') {
            scanf("%d%d%d", &l[i], &r[i], &x[i]);
        } else if (type[i] == '*') {
            scanf("%d %c", &id[i], &c[i]);
        } else if (type[i] == '-') {
            scanf("%d%d", &id[i], &x[i]);
            ids[x[i]].pb(id[i]);
        }
        if (i < q) {
            scanf("\n");
        }
    }
    build(1, 1, n);
    TreeNode for_queries;
    for (int i = 1; i <= q; i++) {
        for (int j = 0; j < (int)ids[i].size(); j++) {
            int index = ids[i][j];
            have[index][i] = getCharacter(1, 1, n, index);
        }
        if (type[i] == '?') {
            for_queries = get(1, 1, n, l[i], r[i]);
            printf("%d\n", for_queries.answer[c[i] - 'a']);
        } else if (type[i] == '+') {
            update(1, 1, n, l[i], r[i], x[i]);
        } else if (type[i] == '*') {
            setValue(1, 1, n, id[i], c[i]);
        } else if (type[i] == '-') {
            setValue(1, 1, n, id[i], have[id[i]][x[i]]);
        }
    }
    return 0;
}

Second solution

#include <cstdio>
#include <vector>
#include <cassert>
using namespace std;

int const T = 1 << 17;
int const ALPHA = 26;
int const N = 123456;

int nextchar() {
  int c = getchar();
  while (c <= 32) c = getchar();
  return c;  
}

struct node {
  int longest[ALPHA];
  int first, firstCount;
  int last, lastCount;
  int len;

  node() : first(0), firstCount(0), last(0), lastCount(0), len(0) {
    fill(longest, longest + ALPHA, 0);
  }
};

node createLetter(int c) {
  node ret;
  ret.longest[c] = 1;
  ret.first = ret.last = c;
  ret.len = ret.firstCount = ret.lastCount = 1;
  return ret;
}

node operator+(node const &a, node const &b) {
  if (a.len == 0) return b;
  if (b.len == 0) return a;
  node ret;
  for (int i = 0; i < ALPHA; i++) {
    ret.longest[i] = std::max(a.longest[i], b.longest[i]);
  }
  ret.len = a.len + b.len;
  ret.first = a.first;
  ret.firstCount = a.firstCount + (a.firstCount == a.len && b.first == a.first ? b.firstCount : 0);
  ret.last = b.last;
  ret.lastCount = b.lastCount + (b.lastCount == b.len && b.last == a.last ? a.lastCount : 0);
  if (a.last == b.first) {
    ret.longest[a.last] = std::max(ret.longest[a.last], a.lastCount + b.firstCount);
  }
  return ret;
}

node tr[2 * T + 5];
int add[2 * T + 5];
int qa[N], qb[N], qc[N], type[N];
vector<int> acc[N];

node processAdd(node const &v, int add) {
  node ret;
  for (int i = 0; i < ALPHA; i++) {
    ret.longest[(i + add) % ALPHA] = v.longest[i];
  }
  ret.first = (v.first + add) % ALPHA;
  ret.last = (v.last + add) % ALPHA;
  ret.len = v.len;
  ret.firstCount = v.firstCount;
  ret.lastCount = v.lastCount;
  return ret;
}

void relax(int v) {
  if (add[v] == 0) return;
  add[2 * v] += add[v];
  add[2 * v + 1] += add[v];
  tr[v] = processAdd(tr[v], add[v]);
  add[v] = 0;
}

node collect(int v, int l, int r, int left, int right) {
  if (r <= left || right <= l) return node();
  if (left <= l && r <= right) {
    return processAdd(tr[v], add[v]);
  }
  relax(v);
  int mid = (l + r) >> 1;
  return collect(v * 2, l, mid, left, right) + collect(v * 2 + 1, mid, r, left, right);
}

void makeAdd(int v, int l, int r, int left, int right, int delta) {
  if (r <= left || right <= l) return;
  if (left <= l && r <= right) {
    add[v] += delta;
    return;
  }
  relax(v);
  int mid = (l + r) >> 1;
  makeAdd(v * 2, l, mid, left, right, delta);
  makeAdd(v * 2 + 1, mid, r, left, right, delta);
  tr[v] = processAdd(tr[v * 2], add[v * 2]) + processAdd(tr[v * 2 + 1], add[v * 2 + 1]);
}

void setIt(int v, int l, int r, int x, int y) {
  if (l + 1 == r) {
    tr[v] = createLetter(y);
    add[v] = 0;
    return;
  }
  relax(v);
  int mid = (l + r) >> 1;
  if (x < mid) setIt(v * 2, l, mid, x, y); else setIt(v * 2 + 1, mid, r, x, y);
  tr[v] = processAdd(tr[v * 2], add[v * 2]) + processAdd(tr[v * 2 + 1], add[v * 2 + 1]);
}

int main() {
  int n, q;
  assert(scanf("%d%d", &n, &q) == 2);
  for (int i = 0; i < n; i++) {
    setIt(1, 0, T, i, nextchar() - 'a');
  }
  for (int i = 0; i < q; i++) {
    int c = getchar();
    while (c <= 32) c = getchar();
    type[i] = c;
    if (c == '?') {
      assert(scanf("%d%d", qa + i, qb + i) == 2);
      --qa[i];
      qc[i] = nextchar() - 'a';
    } else if (c == '+') {
      assert(scanf("%d%d%d", qa + i, qb + i, qc + i) == 3);
      --qa[i];
      qc[i] %= ALPHA;
    } else if (c == '*') {
      assert(scanf("%d", qa + i) == 1);
      --qa[i];
      qc[i] = nextchar() - 'a';
    } else {
      assert(scanf("%d%d", qa + i, qc + i) == 2);
      --qa[i];
      acc[qc[i] - 1].push_back(i);
    }
  }
  for (int i = 0; i < q; i++) {
    for (int x : acc[i]) {
      qc[x] = collect(1, 0, T, qa[x], qa[x] + 1).first;
    }
    if (type[i] == '?') {
      printf("%d\n", collect(1, 0, T, qa[i], qb[i]).longest[qc[i]]);
    } else if (type[i] == '+') {
      makeAdd(1, 0, T, qa[i], qb[i], qc[i]);
    } else {
      setIt(1, 0, T, qa[i], qc[i]);
    }
  }
}


Tags:
YASH PAL

Posted by: YASH PAL

Yash is a Full Stack web developer. he always will to help others. and this approach takes him to write this page.

Post a Comment

0 Comments