范围[l,r]中可以置换为回文的子串数

给出一串s小写的英文字母,用|s| <= 10^5.有最多的q <= 10^5查询给出了一个范围[l, r],询问:字符串的多少个子串s[l...r]可以被置换形成回文.

现在,如果出现奇数次的字符数最多,则可以将字符串置换为回文1.我试图使用段树但似乎无法合并两个范围.我怎么处理它？

为了得到更好的答案,我们可以应用Mo的算法来获得一个O(n^(3/2) |alphabet|)时间算法.这对你来说可能足够快.核心是以下增量算法,用于计算整个字符串的回文可置换子串的数量(在Python 3中):

import collections


def ppcount(s):
    n = 0
    sigcount = collections.Counter()
    sig = 0
    for c in s:
        sigcount[sig] += 1
        sig ^= 1 << (ord(c) - ord('a'))
        n += sigcount[sig]
        for i in range(26):
            n += sigcount[sig ^ (1 << i)]
    return n

该变量sig跟踪到目前为止输入中哪些字母具有奇数频率.如果长度前缀的签名最多距离长度前缀的签名的汉明距离,则子串s[l:r](包括l,排除r)是回文可置换的.该地图跟踪有多少前缀具有特定签名.l1r-1sigcount

要应用Mo的算法,首先为上面的循环体写入逆操作(即,减去n,更新sig和减少sigcount).读入所有查询并按其排序(l // int(sqrt(n)), r).对于按排序顺序的每个查询,使用更新和反向更新操作来调整要考虑的字符串s[l:r+1],然后报告当前总计.

使用Python代码(首先是天真的版本,用于比较;继续滚动):

import collections
import math
import random


def odd(n):
    return bool(n & 1)


def ispp(s):
    return sum(odd(n) for n in collections.Counter(s).values()) <= 1


def naiveppcount(s):
    n = len(s)
    return sum(ispp(s[l:r + 1]) for l in range(n) for r in range(l, n))


def bit(c):
    return 1 << ((ord(c) - 1) & 31)


def neighbors(sig):
    yield sig
    for i in range(26):
        yield sig ^ (1 << i)


class PPCounter(object):
    def __init__(self):
        self.count = 0
        self._sigcount = collections.Counter({0: 1})
        self._leftsig = 0
        self._rightsig = 0

    def pushleft(self, c):
        self._leftsig ^= bit(c)
        for sig in neighbors(self._leftsig):
            self.count += self._sigcount[sig]
        self._sigcount[self._leftsig] += 1

    def popleft(self, c):
        self._sigcount[self._leftsig] -= 1
        for sig in neighbors(self._leftsig):
            self.count -= self._sigcount[sig]
        self._leftsig ^= bit(c)

    def pushright(self, c):
        self._rightsig ^= bit(c)
        for sig in neighbors(self._rightsig):
            self.count += self._sigcount[sig]
        self._sigcount[self._rightsig] += 1

    def popright(self, c):
        self._sigcount[self._rightsig] -= 1
        for sig in neighbors(self._rightsig):
            self.count -= self._sigcount[sig]
        self._rightsig ^= bit(c)


def ppcount(s, intervals):
    sqrtn = int(math.sqrt(len(s)))
    intervals = sorted(
        intervals, key=lambda interval: (interval[0] // sqrtn, interval[1]))
    l = 0
    r = -1
    ctr = PPCounter()
    for interval in intervals:
        il, ir = interval
        while l > il:
            l -= 1
            ctr.pushleft(s[l])
        while r < ir:
            r += 1
            ctr.pushright(s[r])
        while l < il:
            ctr.popleft(s[l])
            l += 1
        while r > ir:
            ctr.popright(s[r])
            r -= 1
        yield interval, ctr.count


def test():
    n = 100
    s = [random.choice('abcd') for i in range(n)]
    intervals = []
    for i in range(1000):
        l = random.randrange(n)
        r = random.randrange(n)
        intervals.append((min(l, r), max(l, r)))
    for (l, r), count in ppcount(s, intervals):
        assert count == naiveppcount(s[l:r + 1])


if __name__ == '__main__':
    test()