Three Religions (Codeforces 1149B)
Tags: Implement, strings

During the archaeological research in the Middle East you found the traces of three ancient religions: First religion, Second religion and Third religion. You compiled the information on the evolution of each of these beliefs, and you now wonder if the followers of each religion could coexist in peace.The Word of Universe is a long word containing the lowercase English characters only. At each moment of time, each of the religion beliefs could be described by a word consisting of lowercase English characters.The three religions can coexist in peace if their descriptions form disjoint subsequences of the Word of Universe. More formally, one can paint some of the characters of the Word of Universe in three colors: $$$1$$$, $$$2$$$, $$$3$$$, so that each character is painted in at most one color, and the description of the $$$i$$$-th religion can be constructed from the Word of Universe by removing all characters that aren't painted in color $$$i$$$.The religions however evolve. In the beginning, each religion description is empty. Every once in a while, either a character is appended to the end of the description of a single religion, or the last character is dropped from the description. After each change, determine if the religions could coexist in peace.

Input: The first line of the input contains two integers $$$n, q$$$ ($$$1 \leq n \leq 100\,000$$$, $$$1 \leq q \leq 1000$$$) — the length of the Word of Universe and the number of religion evolutions, respectively. The following line contains the Word of Universe — a string of length $$$n$$$ consisting of lowercase English characters.Each of the following line describes a single evolution and is in one of the following formats:   + $$$i$$$ $$$c$$$ ($$$i \in \{1, 2, 3\}$$$, $$$c \in \{\mathtt{a}, \mathtt{b}, \dots, \mathtt{z}\}$$$: append the character $$$c$$$ to the end of $$$i$$$-th religion description.  - $$$i$$$ ($$$i \in \{1, 2, 3\}$$$) – remove the last character from the $$$i$$$-th religion description. You can assume that the pattern is non-empty. You can assume that no religion will have description longer than $$$250$$$ characters.

Output: Write $$$q$$$ lines. The $$$i$$$-th of them should be YES if the religions could coexist in peace after the $$$i$$$-th evolution, or NO otherwise.You can print each character in any case (either upper or lower).

Note: In the first example, after the 6th evolution the religion descriptions are: ad, bc, and ab. The following figure shows how these descriptions form three disjoint subsequences of the Word of Universe:  

Sample Inputs:
6 8
abdabc
+ 1 a
+ 1 d
+ 2 b
+ 2 c
+ 3 a
+ 3 b
+ 1 c
- 2

6 8
abbaab
+ 1 a
+ 2 a
+ 3 a
+ 1 b
+ 2 b
+ 3 b
- 1
+ 2 z

Sample Outputs:
YES
YES
YES
YES
YES
YES
NO
YES

YES
YES
YES
YES
YES
NO
YES
NO

Solution (Python):
import sys, os, io
input = io.BytesIO(os.read(0, os.fstat(0).st_size)).readline

def f(u, v):
    return u * (n + 1) + v

def g(u, v, w):
    return u * l23 + v * l3 + w

def bfs(s0, G):
    (q, k) = ([s0], 0)
    while len(q) ^ k:
        i = q[k]
        for (j, _) in G[i]:
            q.append(j)
        k += 1
    return q
(n, q) = map(int, input().split())
s = list(input().rstrip())
l = 26 * (n + 1)
inf = pow(10, 9) + 1
nx = [inf] * l
for i in range(n):
    nx[f(s[i] - 97, i)] = i + 1
for i in range(26):
    for j in range((i + 1) * (n + 1) - 2, i * (n + 1) - 1, -1):
        nx[j] = min(nx[j], nx[j + 1])
(G1, G2, G3) = ([[-1] * 26], [[-1] * 26], [[-1] * 26])
(p1, p2, p3) = ([-1], [-1], [-1])
(u, v, w) = (0, 0, 0)
e = []
for i in range(q):
    t = list(input().rstrip().decode().split())
    if t[0] == '+':
        c = ord(t[2]) - 97
        if t[1] == '1':
            if G1[u][c] == -1:
                G1[u][c] = len(G1)
                G1.append([-1] * 26)
                p1.append(u)
            u = G1[u][c]
        elif t[1] == '2':
            if G2[v][c] == -1:
                G2[v][c] = len(G2)
                G2.append([-1] * 26)
                p2.append(v)
            v = G2[v][c]
        else:
            if G3[w][c] == -1:
                G3[w][c] = len(G3)
                G3.append([-1] * 26)
                p3.append(w)
            w = G3[w][c]
    elif t[1] == '1':
        u = p1[u]
    elif t[1] == '2':
        v = p2[v]
    else:
        w = p3[w]
    e.append((u, v, w))
(l1, l2, l3) = (len(G1), len(G2), len(G3))
l23 = l2 * l3
(H1, H2, H3) = ([], [], [])
for i in range(l1):
    (G1i, u) = (G1[i], [])
    for j in range(26):
        if G1i[j] ^ -1:
            u.append((G1i[j], j))
    H1.append(u)
for i in range(l2):
    (G2i, u) = (G2[i], [])
    for j in range(26):
        if G2i[j] ^ -1:
            u.append((G2i[j], j))
    H2.append(u)
for i in range(l3):
    (G3i, u) = (G3[i], [])
    for j in range(26):
        if G3i[j] ^ -1:
            u.append((G3i[j], j))
    H3.append(u)
(p1, p2, p3) = (bfs(0, H1), bfs(0, H2), bfs(0, H3))
m = l1 * l2 * l3
dp = [inf] * m
dp[0] = 0
for u in p1:
    for v in p2:
        for w in p3:
            i = g(u, v, w)
            dpi = dp[i]
            if dpi == inf:
                continue
            for (nu, j) in H1[u]:
                k = g(nu, v, w)
                dp[k] = min(dp[k], nx[f(j, dpi)])
            for (nv, j) in H2[v]:
                k = g(u, nv, w)
                dp[k] = min(dp[k], nx[f(j, dpi)])
            for (nw, j) in H3[w]:
                k = g(u, v, nw)
                dp[k] = min(dp[k], nx[f(j, dpi)])
ans = []
for (u, v, w) in e:
    ans0 = 'YES' if dp[g(u, v, w)] ^ inf else 'NO'
    ans.append(ans0)
sys.stdout.write('\n'.join(ans))

Solution (Python):
import sys
input = iter(sys.stdin.buffer.read().decode().splitlines()).__next__
(n, q) = map(int, input().split())
s = '!' + input()
nxt = [[n + 1] * (n + 2) for _ in range(26)]
for i in range(n - 1, -1, -1):
    c = ord(s[i + 1]) - 97
    for j in range(26):
        nxt[j][i] = nxt[j][i + 1]
    nxt[c][i] = i + 1
w = [[-1], [-1], [-1]]
idx = lambda i, j, k: i * 65536 + j * 256 + k
dp = [0] * (256 * 256 * 256)

def calc(fix=None):
    r = list(map(range, (len(w[0]), len(w[1]), len(w[2]))))
    if fix is not None:
        r[fix] = range(len(w[fix]) - 1, len(w[fix]))
    for i in r[0]:
        for j in r[1]:
            for k in r[2]:
                dp[idx(i, j, k)] = min(nxt[w[0][i]][dp[idx(i - 1, j, k)]] if i else n + 1, nxt[w[1][j]][dp[idx(i, j - 1, k)]] if j else n + 1, nxt[w[2][k]][dp[idx(i, j, k - 1)]] if k else n + 1)
                if i == j == k == 0:
                    dp[idx(i, j, k)] = 0
out = []
for _ in range(q):
    (t, *r) = input().split()
    if t == '+':
        (i, c) = (int(r[0]) - 1, ord(r[1]) - 97)
        w[i].append(c)
        calc(i)
    else:
        i = int(r[0]) - 1
        w[i].pop()
    req = dp[idx(len(w[0]) - 1, len(w[1]) - 1, len(w[2]) - 1)]
    out.append('YES' if req <= n else 'NO')
print(*out, sep='\n')

Solution (Python):
import random, sys, os, math, gc
from collections import Counter, defaultdict, deque
from functools import lru_cache, reduce, cmp_to_key
from itertools import accumulate, combinations, permutations, product
from heapq import nsmallest, nlargest, heapify, heappop, heappush
from io import BytesIO, IOBase
from copy import deepcopy
from bisect import bisect_left, bisect_right
from math import factorial, gcd
from operator import mul, xor
from types import GeneratorType
BUFSIZE = 8192
MOD = 10 ** 9 + 7
MODD = 998244353
INF = float('inf')
D4 = [(1, 0), (0, 1), (-1, 0), (0, -1)]
D8 = [(1, 0), (1, 1), (0, 1), (-1, 1), (-1, 0), (-1, -1), (0, -1), (1, -1)]

def solve():
    (n, q) = LII()
    s = I()
    nxt = [[n] * 26 for _ in range(n + 2)]
    for i in range(n - 1, -1, -1):
        for j in range(26):
            nxt[i][j] = nxt[i + 1][j]
        nxt[i][ord(s[i]) - 97] = i
    dp = [[[n] * 255 for _ in range(255)] for _ in range(255)]
    dp[0][0][0] = -1
    (s1, s2, s3) = ([], [], [])
    out = []
    for _ in range(q):
        T = LI()
        if T[0] == '+':
            c = ord(T[2]) - 97
            if T[1] == '1':
                s1.append(c)
                i = len(s1)
                for j in range(len(s2) + 1):
                    for k in range(len(s3) + 1):
                        dp[i][j][k] = n
                        if i:
                            dp[i][j][k] = min(dp[i][j][k], nxt[dp[i - 1][j][k] + 1][s1[i - 1]])
                        if j:
                            dp[i][j][k] = min(dp[i][j][k], nxt[dp[i][j - 1][k] + 1][s2[j - 1]])
                        if k:
                            dp[i][j][k] = min(dp[i][j][k], nxt[dp[i][j][k - 1] + 1][s3[k - 1]])
            if T[1] == '2':
                s2.append(c)
                for i in range(len(s1) + 1):
                    j = len(s2)
                    for k in range(len(s3) + 1):
                        dp[i][j][k] = n
                        if i:
                            dp[i][j][k] = min(dp[i][j][k], nxt[dp[i - 1][j][k] + 1][s1[i - 1]])
                        if j:
                            dp[i][j][k] = min(dp[i][j][k], nxt[dp[i][j - 1][k] + 1][s2[j - 1]])
                        if k:
                            dp[i][j][k] = min(dp[i][j][k], nxt[dp[i][j][k - 1] + 1][s3[k - 1]])
            if T[1] == '3':
                s3.append(c)
                for i in range(len(s1) + 1):
                    for j in range(len(s2) + 1):
                        k = len(s3)
                        dp[i][j][k] = n
                        if i:
                            dp[i][j][k] = min(dp[i][j][k], nxt[dp[i - 1][j][k] + 1][s1[i - 1]])
                        if j:
                            dp[i][j][k] = min(dp[i][j][k], nxt[dp[i][j - 1][k] + 1][s2[j - 1]])
                        if k:
                            dp[i][j][k] = min(dp[i][j][k], nxt[dp[i][j][k - 1] + 1][s3[k - 1]])
        else:
            if T[1] == '1':
                s1.pop()
            if T[1] == '2':
                s2.pop()
            if T[1] == '3':
                s3.pop()
        if dp[len(s1)][len(s2)][len(s3)] < n:
            out.append('YES')
        else:
            out.append('NO')
    print(*out, sep='\n')

def main():
    t = 1
    for _ in range(t):
        solve()

def bootstrap(f, stack=[]):

    def wrappedfunc(*args, **kwargs):
        if stack:
            return f(*args, **kwargs)
        else:
            to = f(*args, **kwargs)
            while True:
                if type(to) is GeneratorType:
                    stack.append(to)
                    to = next(to)
                else:
                    stack.pop()
                    if not stack:
                        break
                    to = stack[-1].send(to)
            return to
    return wrappedfunc

def bitcnt(n):
    c = (n & 6148914691236517205) + (n >> 1 & 6148914691236517205)
    c = (c & 3689348814741910323) + (c >> 2 & 3689348814741910323)
    c = (c & 1085102592571150095) + (c >> 4 & 1085102592571150095)
    c = (c & 71777214294589695) + (c >> 8 & 71777214294589695)
    c = (c & 281470681808895) + (c >> 16 & 281470681808895)
    c = (c & 4294967295) + (c >> 32 & 4294967295)
    return c

def lcm(x, y):
    return x * y // gcd(x, y)

def lowbit(x):
    return x & -x

def perm(n, r):
    return factorial(n) // factorial(n - r) if n >= r else 0

def comb(n, r):
    return factorial(n) // (factorial(r) * factorial(n - r)) if n >= r else 0

def probabilityMod(x, y, mod):
    return x * pow(y, mod - 2, mod) % mod

class SortedList:

    def __init__(self, iterable=[], _load=200):
        """"""
        values = sorted(iterable)
        self._len = _len = len(values)
        self._load = _load
        self._lists = _lists = [values[i:i + _load] for i in range(0, _len, _load)]
        self._list_lens = [len(_list) for _list in _lists]
        self._mins = [_list[0] for _list in _lists]
        self._fen_tree = []
        self._rebuild = True

    def _fen_build(self):
        """"""
        self._fen_tree[:] = self._list_lens
        _fen_tree = self._fen_tree
        for i in range(len(_fen_tree)):
            if i | i + 1 < len(_fen_tree):
                _fen_tree[i | i + 1] += _fen_tree[i]
        self._rebuild = False

    def _fen_update(self, index, value):
        """"""
        if not self._rebuild:
            _fen_tree = self._fen_tree
            while index < len(_fen_tree):
                _fen_tree[index] += value
                index |= index + 1

    def _fen_query(self, end):
        """"""
        if self._rebuild:
            self._fen_build()
        _fen_tree = self._fen_tree
        x = 0
        while end:
            x += _fen_tree[end - 1]
            end &= end - 1
        return x

    def _fen_findkth(self, k):
        """"""
        _list_lens = self._list_lens
        if k < _list_lens[0]:
            return (0, k)
        if k >= self._len - _list_lens[-1]:
            return (len(_list_lens) - 1, k + _list_lens[-1] - self._len)
        if self._rebuild:
            self._fen_build()
        _fen_tree = self._fen_tree
        idx = -1
        for d in reversed(range(len(_fen_tree).bit_length())):
            right_idx = idx + (1 << d)
            if right_idx < len(_fen_tree) and k >= _fen_tree[right_idx]:
                idx = right_idx
                k -= _fen_tree[idx]
        return (idx + 1, k)

    def _delete(self, pos, idx):
        """"""
        _lists = self._lists
        _mins = self._mins
        _list_lens = self._list_lens
        self._len -= 1
        self._fen_update(pos, -1)
        del _lists[pos][idx]
        _list_lens[pos] -= 1
        if _list_lens[pos]:
            _mins[pos] = _lists[pos][0]
        else:
            del _lists[pos]
            del _list_lens[pos]
            del _mins[pos]
            self._rebuild = True

    def _loc_left(self, value):
        """"""
        if not self._len:
            return (0, 0)
        _lists = self._lists
        _mins = self._mins
        (lo, pos) = (-1, len(_lists) - 1)
        while lo + 1 < pos:
            mi = lo + pos >> 1
            if value <= _mins[mi]:
                pos = mi
            else:
                lo = mi
        if pos and value <= _lists[pos - 1][-1]:
            pos -= 1
        _list = _lists[pos]
        (lo, idx) = (-1, len(_list))
        while lo + 1 < idx:
            mi = lo + idx >> 1
            if value <= _list[mi]:
                idx = mi
            else:
                lo = mi
        return (pos, idx)

    def _loc_right(self, value):
        """"""
        if not self._len:
            return (0, 0)
        _lists = self._lists
        _mins = self._mins
        (pos, hi) = (0, len(_lists))
        while pos + 1 < hi:
            mi = pos + hi >> 1
            if value < _mins[mi]:
                hi = mi
            else:
                pos = mi
        _list = _lists[pos]
        (lo, idx) = (-1, len(_list))
        while lo + 1 < idx:
            mi = lo + idx >> 1
            if value < _list[mi]:
                idx = mi
            else:
                lo = mi
        return (pos, idx)

    def add(self, value):
        """"""
        _load = self._load
        _lists = self._lists
        _mins = self._mins
        _list_lens = self._list_lens
        self._len += 1
        if _lists:
            (pos, idx) = self._loc_right(value)
            self._fen_update(pos, 1)
            _list = _lists[pos]
            _list.insert(idx, value)
            _list_lens[pos] += 1
            _mins[pos] = _list[0]
            if _load + _load < len(_list):
                _lists.insert(pos + 1, _list[_load:])
                _list_lens.insert(pos + 1, len(_list) - _load)
                _mins.insert(pos + 1, _list[_load])
                _list_lens[pos] = _load
                del _list[_load:]
                self._rebuild = True
        else:
            _lists.append([value])
            _mins.append(value)
            _list_lens.append(1)
            self._rebuild = True

    def discard(self, value):
        """"""
        _lists = self._lists
        if _lists:
            (pos, idx) = self._loc_right(value)
            if idx and _lists[pos][idx - 1] == value:
                self._delete(pos, idx - 1)

    def remove(self, value):
        """"""
        _len = self._len
        self.discard(value)
        if _len == self._len:
            raise ValueError('{0!r} not in list'.format(value))

    def pop(self, index=-1):
        """"""
        (pos, idx) = self._fen_findkth(self._len + index if index < 0 else index)
        value = self._lists[pos][idx]
        self._delete(pos, idx)
        return value

    def bisect_left(self, value):
        """"""
        (pos, idx) = self._loc_left(value)
        return self._fen_query(pos) + idx

    def bisect_right(self, value):
        """"""
        (pos, idx) = self._loc_right(value)
        return self._fen_query(pos) + idx

    def count(self, value):
        """"""
        return self.bisect_right(value) - self.bisect_left(value)

    def __len__(self):
        """"""
        return self._len

    def __getitem__(self, index):
        """"""
        (pos, idx) = self._fen_findkth(self._len + index if index < 0 else index)
        return self._lists[pos][idx]

    def __delitem__(self, index):
        """"""
        (pos, idx) = self._fen_findkth(self._len + index if index < 0 else index)
        self._delete(pos, idx)

    def __contains__(self, value):
        """"""
        _lists = self._lists
        if _lists:
            (pos, idx) = self._loc_left(value)
            return idx < len(_lists[pos]) and _lists[pos][idx] == value
        return False

    def __iter__(self):
        """"""
        return (value for _list in self._lists for value in _list)

    def __reversed__(self):
        """"""
        return (value for _list in reversed(self._lists) for value in reversed(_list))

    def __repr__(self):
        """"""
        return 'SortedList({0})'.format(list(self))

class FastIO(IOBase):
    newlines = 0

    def __init__(self, file):
        self._fd = file.fileno()
        self.buffer = BytesIO()
        self.writable = 'x' in file.mode or 'r' not in file.mode
        self.write = self.buffer.write if self.writable else None

    def read(self):
        while True:
            b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
            if not b:
                break
            ptr = self.buffer.tell()
            (self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
        self.newlines = 0
        return self.buffer.read()

    def readline(self):
        while self.newlines == 0:
            b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
            self.newlines = b.count(b'\n') + (not b)
            ptr = self.buffer.tell()
            (self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
        self.newlines -= 1
        return self.buffer.readline()

    def flush(self):
        if self.writable:
            os.write(self._fd, self.buffer.getvalue())
            (self.buffer.truncate(0), self.buffer.seek(0))

class IOWrapper(IOBase):

    def __init__(self, file):
        self.buffer = FastIO(file)
        self.flush = self.buffer.flush
        self.writable = self.buffer.writable
        self.write = lambda s: self.buffer.write(s.encode('ascii'))
        self.read = lambda : self.buffer.read().decode('ascii')
        self.readline = lambda : self.buffer.readline().decode('ascii')
sys.stdin = IOWrapper(sys.stdin)
input = lambda : sys.stdin.readline().rstrip('\r\n')

def I():
    return input()

def II():
    return int(input())

def MI():
    return map(int, input().split())

def LI():
    return list(input().split())

def LII():
    return list(map(int, input().split()))

def GMI():
    return map(lambda x: int(x) - 1, input().split())

def LGMI():
    return list(map(lambda x: int(x) - 1, input().split()))

def getGraph(n, m, directed=False):
    d = [[] for _ in range(n)]
    for _ in range(m):
        (u, v) = LGMI()
        d[u].append(v)
        if not directed:
            d[v].append(u)
    return d

def getWeightedGraph(n, m, directed=False):
    d = [[] for _ in range(n)]
    for _ in range(m):
        (u, v, w) = LII()
        u -= 1
        v -= 1
        d[u].append((v, w))
        if not directed:
            d[v].append((u, w))
    return d
if __name__ == '__main__':
    main()