Petya, Petya, Petr, and Palindromes (Codeforces 1808D)
Tags: Others, two pointers

Petya and his friend, the robot Petya++, have a common friend — the cyborg Petr#. Sometimes Petr# comes to the friends for a cup of tea and tells them interesting problems.Today, Petr# told them the following problem.A palindrome is a sequence that reads the same from left to right as from right to left. For example, $$$[38, 12, 8, 12, 38]$$$, $$$[1]$$$, and $$$[3, 8, 8, 3]$$$ are palindromes.Let's call the palindromicity of a sequence $$$a_1, a_2, \dots, a_n$$$ the minimum count of elements that need to be replaced to make this sequence a palindrome. For example, the palindromicity of the sequence $$$[38, 12, 8, 38, 38]$$$ is $$$1$$$ since it is sufficient to replace the number $$$38$$$ at the fourth position with the number $$$12$$$. And the palindromicity of the sequence $$$[3, 3, 5, 5, 5]$$$ is two since you can replace the first two threes with fives, and the resulting sequence $$$[5, 5, 5, 5, 5]$$$ is a palindrome.Given a sequence $$$a$$$ of length $$$n$$$, and an odd integer $$$k$$$, you need to find the sum of palindromicity of all subarrays of length $$$k$$$, i. e., the sum of the palindromicity values for the sequences $$$a_i, a_{i+1}, \dots, a_{i+k-1}$$$ for all $$$i$$$ from $$$1$$$ to $$$n-k+1$$$.The students quickly solved the problem. Can you do it too?  

Input: The first line of the input contains two integers $$$n$$$ and $$$k$$$ ($$$1 \le n \le 2 \cdot 10^5$$$, $$$1 \le k \le n$$$, $$$k$$$ is odd) — the length of the sequence and the length of subarrays for which it is necessary to determine whether they are palindromes.The second line of the input contains $$$n$$$ integers $$$a_1, a_2, \ldots, a_n$$$ ($$$1 \le a_i \le 2 \cdot 10^5$$$) — the sequence itself.

Output: Output a single integer — the total palindromicity of all subarrays of length $$$k$$$.

Note: In the first example, the palindromicity of the subarray $$$[1, 2, 8, 2, 5]$$$ is $$$1$$$, the palindromicity of the string $$$[2, 8, 2, 5, 2]$$$ is also $$$1$$$, the palindromicity of the string $$$[8, 2, 5, 2, 8]$$$ is $$$0$$$, and the palindromicity of the string $$$[2, 5, 2, 8, 6]$$$ is $$$2$$$. The total palindromicity is $$$1+1+0+2 = 4$$$.In the second example, the only substring of length $$$9$$$ coincides with the entire string, and its palindromicity is $$$0$$$, so the answer is also $$$0$$$.

Sample Inputs:
8 5
1 2 8 2 5 2 8 6

9 9
1 2 3 4 5 4 3 2 1

Sample Outputs:
4

0

Solution (Python):
from heapq import heapify, heappop, heappush
from itertools import cycle
from math import sqrt, ceil
import os
import sys
from collections import defaultdict, deque
from io import BytesIO, IOBase
import sys
from array import array
from math import gcd
from random import randint
from collections import Counter
from functools import lru_cache
from collections import deque

def main():
    from heapq import heappush, heappop, heapify
    import bisect, math

    class SortedList:
        BUCKET_RATIO = 50
        REBUILD_RATIO = 170

        def __init__(self, buckets):
            buckets = list(buckets)
            buckets = sorted(buckets)
            self._build(buckets)

        def __iter__(self):
            for i in self.buckets:
                for j in i:
                    yield j

        def __reversed__(self):
            for i in reversed(self.buckets):
                for j in reversed(i):
                    yield j

        def __len__(self):
            return self.size

        def __contains__(self, x):
            if self.size == 0:
                return False
            bucket = self._find_bucket(x)
            i = bisect.bisect_left(bucket, x)
            return i != len(bucket) and bucket[i] == x

        def __getitem__(self, x):
            if x < 0:
                x += self.size
            if x < 0:
                raise IndexError
            for i in self.buckets:
                if x < len(i):
                    return i[x]
                x -= len(i)
            raise IndexError

        def _build(self, buckets=None):
            if buckets is None:
                buckets = list(self)
            self.size = len(buckets)
            bucket_size = int(math.ceil(math.sqrt(self.size / self.BUCKET_RATIO)))
            tmp = []
            for i in range(bucket_size):
                t = buckets[self.size * i // bucket_size:self.size * (i + 1) // bucket_size]
                tmp.append(t)
            self.buckets = tmp

        def _find_bucket(self, x):
            for i in self.buckets:
                if x <= i[-1]:
                    return i
            return i

        def add(self, x):
            if self.size == 0:
                self.buckets = [[x]]
                self.size = 1
                return True
            bucket = self._find_bucket(x)
            bisect.insort(bucket, x)
            self.size += 1
            if len(bucket) > len(self.buckets) * self.REBUILD_RATIO:
                self._build()
            return True

        def remove(self, x):
            if self.size == 0:
                return False
            bucket = self._find_bucket(x)
            i = bisect.bisect_left(bucket, x)
            if i == len(bucket) or bucket[i] != x:
                return False
            bucket.pop(i)
            self.size -= 1
            if len(bucket) == 0:
                self._build()
            return True

        def lt(self, x):
            for i in reversed(self.buckets):
                if i[0] < x:
                    return i[bisect.bisect_left(i, x) - 1]

        def le(self, x):
            for i in reversed(self.buckets):
                if i[0] <= x:
                    return i[bisect.bisect_right(i, x) - 1]

        def gt(self, x):
            for i in self.buckets:
                if i[-1] > x:
                    return i[bisect.bisect_right(i, x)]

        def ge(self, x):
            for i in self.buckets:
                if i[-1] >= x:
                    return i[bisect.bisect_left(i, x)]

        def index(self, x):
            ans = 0
            for i in self.buckets:
                if i[-1] >= x:
                    return ans + bisect.bisect_left(i, x)
                ans += len(i)
            return ans

        def index_right(self, x):
            ans = 0
            for i in self.buckets:
                if i[-1] > x:
                    return ans + bisect.bisect_right(i, x)
                ans += len(i)
            return ans

    class IntKeyDict(dict):
        from random import randrange
        rand = randrange(1 << 62)

        def __setitem__(self, k, v):
            super().__setitem__(k ^ self.rand, v)

        def __getitem__(self, k):
            return super().__getitem__(k ^ self.rand)

        def __contains__(self, k):
            return super().__contains__(k ^ self.rand)

        def __repr__(self):
            return str({k: v for (k, v) in self.items()})

        def get(self, k, default=None):
            return super().get(k ^ self.rand, default)

        def keys(self):
            return [k ^ self.rand for k in super().keys()]

        def items(self):
            return [(k ^ self.rand, v) for (k, v) in super().items()]
    from bisect import bisect_right, bisect_left
    from collections import defaultdict, deque
    from random import randint
    (n, k) = map(int, input().split())
    arr = list(map(int, input().split()))
    d = {}
    r = (k - 1) // 2
    ans = 0
    res = 0
    for (i, el) in enumerate(arr):
        if el not in d:
            d[el] = [deque(), deque()]
        while d[el][i % 2] and d[el][i % 2][0] <= i - k:
            d[el][i % 2].popleft()
        if i >= k - 1:
            res += k
        if not d[el][i % 2] or i <= r:
            d[el][i % 2].append(i)
        elif i < k - 1:
            extension = min(r, n - i) - k + i + 1
            extension = min(extension, n - i - 1)
            right = k - i - 1 + 2 * (extension - 1)
            left = k - i - 2
            index = bisect_right(d[el][i % 2], right)
            index1 = bisect_right(d[el][i % 2], left)
            ans += 2 * (index - index1)
            d[el][i % 2].append(i)
        else:
            right = n - i
            p = min(r, right)
            index = bisect_right(d[el][i % 2], i - 2 * r + p * 2 - 2)
            ans += 2 * index
            d[el][i % 2].append(i)
    print((res - ans - (n - 2 * r)) // 2)
BUFSIZE = 8192

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, sys.stdout) = (IOWrapper(sys.stdin), IOWrapper(sys.stdout))
input = lambda : sys.stdin.readline().rstrip('\r\n')
if __name__ == '__main__':
    main()

Solution (Python):
(n, k) = map(int, input().split())
k //= 2
l = list(map(int, input().split()))

def ans(l, q):
    n = len(l)
    a = [[-10] for i in range(2 * 10 ** 5 + 1)]
    c = set()
    for i in range(n):
        a[l[i]].append(i)
        c.add(l[i])
    for i in c:
        a[i].append(2 * n + 10)
    answer = 0
    for i in c:
        low = 0
        high = 0
        for z in range(1, len(a[i]) - 1):
            j = a[i][z]
            x = max(k - j - q[0], j + 1)
            y = min(j + k, 2 * n - 2 - k - j + q[1])
            if x <= y:
                while a[i][low] < x:
                    low += 1
                while a[i][low] >= x:
                    low -= 1
                while a[i][high] <= y:
                    high += 1
                while a[i][high] > y:
                    high -= 1
                answer += max(high - low, 0)
    return answer
print(k * (n - 2 * k) - ans(l[::2], [0, 1 - n % 2]) - ans(l[1::2], [1, n % 2]))

Solution (Python):
def solve(n, k, a):
    if k == 1:
        return 0
    ans = 0
    cnts = [0] * 200001
    total = 0
    r1 = r2 = k - 1
    right_indexes = set()
    for l in range(0, n, 2):
        if l in right_indexes:
            right_indexes.remove(l)
            cnts[a[l]] -= 1
            total -= 1
        if r2 < n:
            right_indexes.add(r2)
            cnts[a[r2]] += 1
            total += 1
        elif l < 2 * n - r2 and 2 * n - r2 in right_indexes:
            right_indexes.remove(2 * n - r2)
            cnts[a[2 * n - r2]] -= 1
            total -= 1
        r2 += 2
        if r1 > l:
            if r1 not in right_indexes:
                right_indexes.add(r1)
                cnts[a[r1]] += 1
                total += 1
            r1 -= 2
        ans += total - cnts[a[l]]
    cnts = [0] * 200001
    r1 = k - 2
    r2 = k
    right_indexes = set()
    for l in range(1, n, 2):
        if l in right_indexes:
            right_indexes.remove(l)
            cnts[a[l]] -= 1
            total -= 1
        if r2 < n:
            right_indexes.add(r2)
            cnts[a[r2]] += 1
            total += 1
        elif l < 2 * n - r2 and 2 * n - r2 in right_indexes:
            right_indexes.remove(2 * n - r2)
            cnts[a[2 * n - r2]] -= 1
            total -= 1
        r2 += 2
        if r1 > l:
            if r1 not in right_indexes:
                right_indexes.add(r1)
                cnts[a[r1]] += 1
                total += 1
            r1 -= 2
        ans += total - cnts[a[l]]
    return ans

def main():
    (n, k) = readIntArr()
    a = readIntArr()
    ans = solve(n, k, a)
    print(ans)
    return
import sys
input = sys.stdin.buffer.readline

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()