Anya and the Mysterious String (Codeforces 1881G)
Tags: Others, binary search

Anya received a string $$$s$$$ of length $$$n$$$ brought from Rome. The string $$$s$$$ consists of lowercase Latin letters and at first glance does not raise any suspicions. An instruction was attached to the string.Start of the instruction.A palindrome is a string that reads the same from left to right and right to left. For example, the strings "anna", "aboba", "level" are palindromes, while the strings "gorilla", "banan", "off" are not.A substring $$$[l \ldots r]$$$ of string $$$s$$$ is a string $$$s_l s_{l+1} \ldots s_{r-1} s_r$$$. For example, the substring $$$[4 \ldots 6]$$$ of the string "generation" is the string "era".A string is called beautiful if it does not contain a substring of length at least two that is a palindrome. For example, the strings "fox", "abcdef", and "yioy" are beautiful, while the strings "xyxx", "yikjkitrb" are not.When an integer $$$x$$$ is added to the character $$$s_i$$$, it is replaced $$$x$$$ times with the next character in the alphabet, with "z" being replaced by "a".When an integer $$$x$$$ is added to the substring $$$[l, r]$$$ of string $$$s$$$, it becomes the string $$$s_1 s_2 \ldots s_{l-1} (s_l + x) (s_{l+1} + x) \ldots (s_{r-1} + x) (s_r + x) s_{r+1} \ldots s_n$$$. For example, when the substring $$$[2, 4]$$$ of the string "abazaba" is added with the number $$$6$$$, the resulting string is "ahgfaba".End of the instruction.After reading the instruction, Anya resigned herself to the fact that she has to answer $$$m$$$ queries. The queries can be of two types:  Add the number $$$x$$$ to the substring $$$[l \ldots r]$$$ of string $$$s$$$.  Determine whether the substring $$$[l \ldots r]$$$ of string $$$s$$$ is beautiful. 

Input: The first line contains an integer $$$t$$$ ($$$1 \le t \le 10^4$$$) - the number of test cases.The descriptions of the test cases follow.The first line of each test case contains two integers $$$n$$$ and $$$m$$$ ($$$1 \le n, m \le 2 \cdot 10^5$$$) - the length of the string $$$s$$$ and the number of queries.The second line of each test case contains the string $$$s$$$ of length $$$n$$$, consisting of lowercase Latin letters.The next $$$m$$$ lines contain the queries:  $$$1$$$ $$$l$$$ $$$r$$$ $$$x$$$ ($$$1 \le l \le r \le n$$$, $$$1 \le x \le 10^9$$$) - description of a query of the first type;  $$$2$$$ $$$l$$$ $$$r$$$ ($$$1 \le l \le r \le n$$$) - description of a query of the second type. It is guaranteed that the sum of $$$n$$$ and the sum of $$$m$$$ over all test cases do not exceed $$$2 \cdot 10^5$$$.

Output: For each query of the second type, output "YES" if the substring $$$[l \ldots r]$$$ of string $$$s$$$ is beautiful, otherwise output "NO".You can output "YES" and "NO" in any case (for example, the strings "yEs", "yes", "Yes", and "YES" will be recognized as positive answers).

Note: In the first test case of the first test, the following happens:  tedubcyyxopz: the string edub is beautiful;  tedubcyyxopz $$$\to$$$ tedwdeaaxopz;  tedwdeaaxopz: the string tedwdea is not beautiful as it contains the palindrome edwde;  tedwdeaaxopz $$$\to$$$ terkreaaxopz;  terkreaaxopz $$$\to$$$ terkreaaarsz;  terkreaaarsz $$$\to$$$ terkreaaaasz;  terkreaaaasz: the string kreaaaa is not beautiful as it contains the palindrome aaaa;  terkreaaaasz: the string asz is beautiful. 

Sample Inputs:
5
12 8
tedubcyyxopz
2 2 5
1 4 8 2
2 1 7
1 3 5 40
1 9 11 3
1 10 10 9
2 4 10
2 10 12
10 4
ubnxwwgzjt
2 4 10
2 10 10
1 6 10 8
2 7 7
11 3
hntcxfxyhtu
1 4 6 1
2 4 10
1 4 10 21
13 2
yxhlmzfhqctir
1 5 9 3
1 8 13 15
2 3
bp
1 1 2 15
1 1 2 18
1 2 2 1000000000

Sample Outputs:
YES
NO
NO
YES
NO
YES
YES
YES

Solution (Python):
def main():
    t = int(input())
    allans = []
    for _ in range(t):
        (n, m) = readIntArr()
        s = input()
        rel = [0] * (n + 1)
        for i in range(1, n):
            rel[i] = (ord(s[i]) - ord(s[i - 1])) % 26

        def check2(i):
            if 0 <= i < n - 1 and rel[i + 1] == 0:
                return True
            return False

        def check3(i):
            if 0 <= i < n - 2 and (rel[i + 1] + rel[i + 2]) % 26 == 0:
                return True
            return False
        palindrome_ranges = SortedList()
        for i in range(n):
            if check2(i):
                palindrome_ranges.add((i, i + 1))
            if check3(i):
                palindrome_ranges.add((i, i + 2))
        ans = []
        for __ in range(m):
            arr = readIntArr()
            if arr[1] > arr[2]:
                (arr[1], arr[2]) = (arr[2], arr[1])
            if arr[0] == 1:
                (z, l, r, x) = arr
                x %= 26
                if x == 0:
                    continue
                l -= 1
                r -= 1
                if check2(l - 1):
                    palindrome_ranges.remove((l - 1, l))
                if check3(l - 1):
                    palindrome_ranges.remove((l - 1, l + 1))
                if check3(l - 2):
                    palindrome_ranges.remove((l - 2, l))
                if check2(r):
                    palindrome_ranges.remove((r, r + 1))
                if check3(r):
                    palindrome_ranges.remove((r, r + 2))
                if l != r and check3(r - 1):
                    palindrome_ranges.remove((r - 1, r + 1))
                rel[l] = (rel[l] + x) % 26
                rel[r + 1] = (rel[r + 1] - x) % 26
                if check2(l - 1):
                    palindrome_ranges.add((l - 1, l))
                if check3(l - 1):
                    palindrome_ranges.add((l - 1, l + 1))
                if check3(l - 2):
                    palindrome_ranges.add((l - 2, l))
                if check2(r):
                    palindrome_ranges.add((r, r + 1))
                if check3(r):
                    palindrome_ranges.add((r, r + 2))
                if l != r and check3(r - 1):
                    palindrome_ranges.add((r - 1, r + 1))
            else:
                (z, l, r) = arr
                l -= 1
                r -= 1
                anss = 'YES'
                i = palindrome_ranges.bisect_left((l, l + 1))
                if 0 <= i < len(palindrome_ranges):
                    (l2, r2) = palindrome_ranges[i]
                    if l <= l2 and r2 <= r:
                        anss = 'NO'
                ans.append(anss)
        allans.extend(ans)
    multiLineArrayPrint(allans)
    return
''

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 OrderedList(SortedList):

    def __init__(self, arg):
        super().__init__(arg)

    def rangeCountByValue(self, leftVal, rightVal):
        leftCummulative = self.bisect_left(leftVal)
        rightCummulative = self.bisect_left(rightVal + 1)
        return rightCummulative - leftCummulative
import sys
input = lambda : sys.stdin.readline().rstrip('\r\n')

def oneLineArrayPrint(arr):
    print(' '.join([str(x) for x in arr]))

def multiLineArrayPrint(arr):
    print('\n'.join([str(x) for x in arr]))

def multiLineArrayOfArraysPrint(arr):
    print('\n'.join([' '.join([str(x) for x in y]) for y in arr]))

def readIntArr():
    return [int(x) for x in input().split()]

def makeArr(defaultValFactory, dimensionArr):
    dv = defaultValFactory
    da = dimensionArr
    if len(da) == 1:
        return [dv() for _ in range(da[0])]
    else:
        return [makeArr(dv, da[1:]) for _ in range(da[0])]

def queryInteractive(a, b):
    print('? {} {}'.format(a, b))
    sys.stdout.flush()
    return int(input())

def answerInteractive(ans):
    print('! {}'.format(ans))
    sys.stdout.flush()
inf = float('inf')
from math import gcd, floor, ceil
import math
for _abc in range(1):
    main()

Solution (Python):
def main():
    t = int(input())
    allans = []
    for _ in range(t):
        (n, m) = readIntArr()
        s = input()
        rel = [0] * (n + 1)
        for i in range(1, n):
            rel[i] = (ord(s[i]) - ord(s[i - 1])) % 26

        def check2(i):
            if 0 <= i < n - 1 and rel[i + 1] == 0:
                return True
            return False

        def check3(i):
            if 0 <= i < n - 2 and (rel[i + 1] + rel[i + 2]) % 26 == 0:
                return True
            return False
        palindrome_ranges = SortedList()
        for i in range(n):
            if check2(i):
                palindrome_ranges.add((i, i + 1))
            if check3(i):
                palindrome_ranges.add((i, i + 2))
        ans = []
        for __ in range(m):
            arr = readIntArr()
            if arr[0] == 1:
                (z, l, r, x) = arr
                l -= 1
                r -= 1
                if check2(l - 1):
                    if (l - 1, l) in palindrome_ranges:
                        palindrome_ranges.remove((l - 1, l))
                if check3(l - 1):
                    if (l - 1, l + 1) in palindrome_ranges:
                        palindrome_ranges.remove((l - 1, l + 1))
                if check3(l - 2):
                    if (l - 2, l) in palindrome_ranges:
                        palindrome_ranges.remove((l - 2, l))
                if check2(r):
                    if (r, r + 1) in palindrome_ranges:
                        palindrome_ranges.remove((r, r + 1))
                if check3(r):
                    if (r, r + 2) in palindrome_ranges:
                        palindrome_ranges.remove((r, r + 2))
                if check3(r - 1):
                    if (r - 1, r + 1) in palindrome_ranges:
                        palindrome_ranges.remove((r - 1, r + 1))
                rel[l] = (rel[l] + x) % 26
                rel[r + 1] = (rel[r + 1] - x) % 26
                if check2(l - 1):
                    if (l - 1, l) not in palindrome_ranges:
                        palindrome_ranges.add((l - 1, l))
                if check3(l - 1):
                    if (l - 1, l + 1) not in palindrome_ranges:
                        palindrome_ranges.add((l - 1, l + 1))
                if check3(l - 2):
                    if (l - 2, l) not in palindrome_ranges:
                        palindrome_ranges.add((l - 2, l))
                if check2(r):
                    if (r, r + 1) not in palindrome_ranges:
                        palindrome_ranges.add((r, r + 1))
                if check3(r):
                    if (r, r + 2) not in palindrome_ranges:
                        palindrome_ranges.add((r, r + 2))
                if check3(r - 1):
                    if (r - 1, r + 1) not in palindrome_ranges:
                        palindrome_ranges.add((r - 1, r + 1))
            else:
                (z, l, r) = arr
                l -= 1
                r -= 1
                anss = 'YES'
                i = palindrome_ranges.bisect_left((l, l + 1))
                if 0 <= i < len(palindrome_ranges):
                    (l2, r2) = palindrome_ranges[i]
                    if l <= l2 and r2 <= r:
                        anss = 'NO'
                ans.append(anss)
        allans.extend(ans)
    multiLineArrayPrint(allans)
    return
''

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 OrderedList(SortedList):

    def __init__(self, arg):
        super().__init__(arg)

    def rangeCountByValue(self, leftVal, rightVal):
        leftCummulative = self.bisect_left(leftVal)
        rightCummulative = self.bisect_left(rightVal + 1)
        return rightCummulative - leftCummulative
import sys
input = lambda : sys.stdin.readline().rstrip('\r\n')

def oneLineArrayPrint(arr):
    print(' '.join([str(x) for x in arr]))

def multiLineArrayPrint(arr):
    print('\n'.join([str(x) for x in arr]))

def multiLineArrayOfArraysPrint(arr):
    print('\n'.join([' '.join([str(x) for x in y]) for y in arr]))

def readIntArr():
    return [int(x) for x in input().split()]

def makeArr(defaultValFactory, dimensionArr):
    dv = defaultValFactory
    da = dimensionArr
    if len(da) == 1:
        return [dv() for _ in range(da[0])]
    else:
        return [makeArr(dv, da[1:]) for _ in range(da[0])]

def queryInteractive(a, b):
    print('? {} {}'.format(a, b))
    sys.stdout.flush()
    return int(input())

def answerInteractive(ans):
    print('! {}'.format(ans))
    sys.stdout.flush()
inf = float('inf')
from math import gcd, floor, ceil
import math
for _abc in range(1):
    main()

Solution (Python):
class SegmentTree:

    def __init__(self, arr, combinerFunction, isCommutative=True):
        self.n = len(arr)

        def cmb(a, b):
            if a == None:
                return b
            if b == None:
                return a
            return combinerFunction(a, b)
        self.cmb = cmb
        self.sz = self.n if isCommutative else pow(2, (self.n - 1).bit_length())
        self.t = [None] * (2 * self.sz)
        for i in range(self.n):
            self.t[i + self.sz] = arr[i]
        for i in range(self.sz - 1, 0, -1):
            self.pull(i)

    def pull(self, p):
        self.t[p] = self.cmb(self.t[2 * p], self.t[2 * p + 1])

    def update(self, idx, val):
        idx += self.sz
        self.t[idx] = val
        idx //= 2
        while idx > 0:
            self.pull(idx)
            idx //= 2

    def query(self, l, r):
        l += self.sz
        r += self.sz + 1
        a = b = None
        while l < r:
            if l % 2 == 1:
                a = self.cmb(a, self.t[l])
                l += 1
            if r % 2 == 1:
                r -= 1
                b = self.cmb(self.t[r], b)
            l //= 2
            r //= 2
        return self.cmb(a, b)

def getMaxSegTree(arr):
    return SegmentTree(arr, lambda a, b: max(a, b), True)

def getMinSegTree(arr):
    return SegmentTree(arr, lambda a, b: min(a, b), True)

def getSumSegTree(arr):
    return SegmentTree(arr, lambda a, b: a + b, True)

def main():
    t = int(input())
    allans = []
    for _ in range(t):
        (n, m) = readIntArr()
        s = input()
        diff = [0] * (n + 1)
        for i in range(1, n):
            diff[i] = (ord(s[i]) - ord(s[i - 1])) % 26

        def check2(i):
            """"""
            return 0 <= i < n - 1 and diff[i + 1] == 0

        def check3(i):
            """"""
            return 0 <= i < n - 2 and (diff[i + 1] + diff[i + 2]) % 26 == 0
        segarr2 = [0] * n
        segarr3 = [0] * n
        for i in range(n):
            if check2(i):
                segarr2[i] = 1
            if check3(i):
                segarr3[i] = 1
        segtree2 = getMaxSegTree(segarr2)
        segtree3 = getMaxSegTree(segarr3)
        for __ in range(m):
            arr = readIntArr()
            if arr[0] == 1:
                (___, l, r, x) = arr
                l -= 1
                r -= 1
                diff[l] = (diff[l] + x) % 26
                diff[r + 1] = (diff[r + 1] - x) % 26
                check_indexes = []
                for i in range(l - 2, l):
                    if 0 <= i < n:
                        check_indexes.append(i)
                for i in range(r - 1, r + 1):
                    if 0 <= i < n:
                        check_indexes.append(i)
                for i in check_indexes:
                    if check2(i):
                        segtree2.update(i, 1)
                    else:
                        segtree2.update(i, 0)
                    if check3(i):
                        segtree3.update(i, 1)
                    else:
                        segtree3.update(i, 0)
            else:
                (___, l, r) = arr
                l -= 1
                r -= 1
                ans = 'YES'
                if r - 1 >= l:
                    if segtree2.query(l, r - 1) == 1:
                        ans = 'NO'
                if r - 2 >= 0:
                    if segtree3.query(l, r - 2) == 1:
                        ans = 'NO'
                allans.append(ans)
    multiLineArrayPrint(allans)
    return
import sys
input = lambda : sys.stdin.readline().rstrip('\r\n')

def oneLineArrayPrint(arr):
    print(' '.join([str(x) for x in arr]))

def multiLineArrayPrint(arr):
    print('\n'.join([str(x) for x in arr]))

def multiLineArrayOfArraysPrint(arr):
    print('\n'.join([' '.join([str(x) for x in y]) for y in arr]))

def readIntArr():
    return [int(x) for x in input().split()]

def makeArr(defaultValFactory, dimensionArr):
    dv = defaultValFactory
    da = dimensionArr
    if len(da) == 1:
        return [dv() for _ in range(da[0])]
    else:
        return [makeArr(dv, da[1:]) for _ in range(da[0])]

def queryInteractive(a, b):
    print('? {} {}'.format(a, b))
    sys.stdout.flush()
    return int(input())

def answerInteractive(ans):
    print('! {}'.format(ans))
    sys.stdout.flush()
inf = float('inf')
from math import gcd, floor, ceil
import math
for _abc in range(1):
    main()