Palindromic subsets

palindromic_subsets.py

MOD = 10 ** 9 + 7
LEFT, RIGHT = range(2)


def modpow(x, y, mod):
    elems = []
    while y:
        elems.append(y % 2)
        y >>= 1
    el = len(elems)
    x_pows = [x for _ in xrange(el)]
    for i in xrange(1, el):
        x_pows[i] = (x_pows[i - 1] * x_pows[i - 1]) % mod

    ret = 1
    for i in xrange(el):
        if elems[i] == 1:
            ret = (ret * elems[i] * x_pows[i]) % mod
    return ret


def palindromes(counts, mod):
    counts = [c for c in counts if c != 0]
    lc = len(counts)
    evens = [modpow(2, count - 1, mod) for count in counts]

    ret = 1
    for even in evens:
        ret = (ret * even) % mod

    # We need to substract 1 for the empty palindrome
    ret = (ret * (len(counts) + 1) - 1) % mod
    return ret


class Node(object):
    def __init__(self, fr, to, val, left = None, right = None, parent = None):
        self.fr = fr
        self.to = to
        self.val = val
        self.left = left
        self.right = right
        self.parent = parent
        self._left_fix = False
        self._right_fix = False

    @property
    def right_val(self):
        if self.right is not None:
            return self.right.val
        else:
            return 0

    @property
    def left_val(self):
        if self.left is not None:
            return self.left.val
        else:
            return 0

    @property
    def left_child(self):
        parent = self.parent
        if parent is not None:
            return parent.left == self
        return False

    def __str__(self):
        return "fr: %s to: %s val: %s" % (
            self.fr, self.to, self.val)

    __repr__ = __str__


def build(string):
    n = len(string)
    ret = []
    for i in xrange(26):
        curr = [Node(j, j, 1 if string[j] == i else 0) for j in xrange(n)]
        while len(curr) > 1:
            nxt, lc = [], len(curr)
            for j in xrange(0, lc if lc % 2 == 0 else lc - 1, 2):
                nxt.append(Node(curr[j].fr, curr[j + 1].to, curr[j].val + curr[j + 1].val, left=curr[j], right=curr[j + 1]))
                curr[j].parent = nxt[-1]
                curr[j + 1].parent = nxt[-1]
            if lc % 2 == 1:
                nxt.append(curr[-1])
            curr = nxt
        ret.append(curr[0])

    return ret


def is_in(fr1, to1, fr2, to2):
    return fr2 <= fr1 and to1 <= to2


def intersect(fr1, to1, fr2, to2):
    return max(fr1, fr2) <= min(to1, to2)


def _need_fix(node, prev):
    while node is not None:
        if node.left == prev:
            if node._left_fix:
                return
            node._left_fix = True
        else:
            if node._right_fix:
                return
            node._right_fix = True
        prev = node
        node = node.parent


def _fix(node):
    while node is not None and not node._left_fix and not node._right_fix:
        node.val = node.left_val + node.right_val
        parent = node.parent
        if parent is not None:
            if node == parent.left:
                parent._left_fix = False
            else:
                parent._right_fix = False
        node = parent


def shift(counts, fr, to, t):
    if t == 0:
        return counts
    prev = [(i - t) % 26 for i in xrange(26)]
    if counts[0].fr == fr and counts[0].to == to:  # the whole range
        return [counts[(i - t) % 26] for i in xrange(26)]
    coll = [[] for _ in xrange(26)]
    parents = [[] for _ in xrange(26)]
    for i in xrange(26):
        stack = [(counts[i], -1)]
        while stack:
            curr, kind = stack.pop()
            if curr.to < fr or to < curr.fr:
                coll[i].append(curr)
                _need_fix(curr.parent, curr)
                parents[i].append((curr.parent, kind))
                continue
            if is_in(curr.fr, curr.to, fr, to):
                continue
            left, right = curr.left, curr.right
            if left is not None and not is_in(left.fr, left.to, fr, to):
                stack.append((left, LEFT))
            if right is not None and not is_in(right.fr, right.to, fr, to):
                stack.append((right, RIGHT))

    for i in xrange(26):
        pi = prev[i]
        for j, el in enumerate(coll[i]):
            parent, kind = parents[pi][j]
            el.parent = parent
            if kind == LEFT:
                el.parent.left = el
                el.parent._left_fix = False
            else:
                el.parent.right = el
                el.parent._right_fix = False
            _fix(el.parent)

    return [counts[(i - t) % 26] for i in xrange(26)]


def query(counts, fr, to):
    ret = [0] * 26
    for i in xrange(26):
        stack, acc = [counts[i]], 0
        while stack:
            curr = stack.pop()
            if is_in(curr.fr, curr.to, fr, to):
                acc += curr.val
                continue

            left, right = curr.left, curr.right

            if left is not None and intersect(left.fr, left.to, fr, to):
                stack.append(left)
            if right is not None and intersect(right.fr, right.to, fr, to):
                stack.append(right)
        ret[i] = acc

    return ret


def rev(ch):
    return ord(ch) - 97


n, q = map(int, raw_input().strip().split())
string = raw_input().strip()
string = [rev(ch) for ch in string]

counts = build(string)

for _ in xrange(q):
    curr = map(int, raw_input().strip().split())
    if curr[0] == 1:
        counts = shift(counts, *curr[1:])
    else:
        ccounts = query(counts, *curr[1:])
        print palindromes(ccounts, MOD)