Line (Codeforces 1722D)
Tags: Greedy, sortings

There are $$$n$$$ people in a horizontal line, each looking either to the left or the right. Each person counts the number of people in the direction they are looking. The value of the line is the sum of each person's count.For example, in the arrangement LRRLL, where L stands for a person looking left and R stands for a person looking right, the counts for each person are $$$[0, 3, 2, 3, 4]$$$, and the value is $$$0+3+2+3+4=12$$$.You are given the initial arrangement of people in the line. For each $$$k$$$ from $$$1$$$ to $$$n$$$, determine the maximum value of the line if you can change the direction of at most $$$k$$$ people.

Input: The input consists of multiple test cases. The first line contains an integer $$$t$$$ ($$$1 \leq t \leq 100$$$) — the number of test cases. The description of the test cases follows.The first line of each test case contains an integer $$$n$$$ ($$$1 \leq n \leq 2\cdot10^5$$$) — the length of the line.The following line contains a string consisting of $$$n$$$ characters, each of which is either L or R, representing a person facing left or right, respectively — the description of the line.It is guaranteed that the sum of $$$n$$$ over all test cases does not exceed $$$2\cdot10^5$$$.Please note that the answer for some test cases won't fit into 32-bit integer type, so you should use at least 64-bit integer type in your programming language (like long long for C++).

Output: For each test case, output $$$n$$$ space-separated non-negative integers — the maximum value of the line if you can change the direction of at most $$$k$$$ people for each $$$k$$$ from $$$1$$$ to $$$n$$$, inclusive.

Note: In the first test case:   $$$k=1$$$: change the direction of $$$1$$$ person to make the line RLR. The total value is $$$2+1+0=3$$$.  $$$k=2$$$: change the direction of $$$2$$$ people to make the line RLL. The total value is $$$2+1+2=5$$$.  $$$k=3$$$: change the direction of $$$2$$$ people to make the line RLL. The total value is $$$2+1+2=5$$$. Note that you have to change the direction of at most $$$k$$$ people. In the second test case, it is optimal to only change the direction of the first person for all $$$k$$$ from $$$1$$$ to $$$5$$$ (that is, make the line RRRLL).

Sample Inputs:
6
3
LLR
5
LRRLL
1
L
12
LRRRLLLRLLRL
10
LLLLLRRRRR
9
LRLRLRLRL

Sample Outputs:
3 5 5 
16 16 16 16 16 
0 
86 95 98 101 102 102 102 102 102 102 102 102 
29 38 45 52 57 62 65 68 69 70 
44 50 54 56 56 56 56 56 56

Solution (Python):
def solve():
    n = int(input())
    s = input()
    score = 0
    imp = [0] * n
    for i in range(n // 2):
        if s[i] == 'L':
            score += i
            imp[i] = n - i - i - 1
        else:
            score += n - 1 - i
    for i in range(n // 2, n):
        if s[i] == 'L':
            score += i
        else:
            score += n - 1 - i
            imp[i] = i + i - n + 1
    imp.sort()
    imp.reverse()
    res = [score + imp[0]] * n
    for i in range(1, n):
        res[i] = res[i - 1] + imp[i]
    print(' '.join((str(x) for x in res)))
numc = int(input())
while numc > 0:
    numc -= 1
    solve()

Solution (Python):
import sys
from bisect import bisect_right, bisect_left
import os
import sys
from io import BytesIO, IOBase
from math import factorial, floor, sqrt, inf, ceil, gcd
from collections import defaultdict, deque, Counter
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')

def inp():
    return int(input())

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

def insr():
    s = input()
    return s[:len(s) - 1]

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

def insr2():
    s = input()
    return s.split(' ')

def make_divisors(n):
    divisors = []
    for i in range(1, int(n ** 0.5) + 1):
        if n % i == 0:
            divisors.append(i)
            if i != n // i and i != 1:
                divisors.append(n // i)
    return divisors

def dfs(graph, vertex):
    visited = set()
    tree = []
    deq = deque([vertex])
    while deq:
        vertex = deq.pop()
        if vertex not in visited:
            visited.add(vertex)
            deq.extend(graph[vertex])
            tree.append(vertex)
    return tree

def find_in_sorted_list(elem, sorted_list):
    """"""
    i = bisect_left(sorted_list, elem)
    if i != len(sorted_list) and sorted_list[i] == elem:
        return i
    return -1

class SegmentTree:

    def __init__(self, data, default=0, func=lambda a, b: a + b):
        """"""
        self._default = default
        self._func = func
        self._len = len(data)
        self._size = _size = 1 << (self._len - 1).bit_length()
        self.data = [default] * (2 * _size)
        self.data[_size:_size + self._len] = data
        for i in reversed(range(_size)):
            self.data[i] = func(self.data[i + i], self.data[i + i + 1])

    def __delitem__(self, idx):
        self[idx] = self._default

    def __getitem__(self, idx):
        return self.data[idx + self._size]

    def __setitem__(self, idx, value):
        idx += self._size
        self.data[idx] = value
        idx >>= 1
        while idx:
            self.data[idx] = self._func(self.data[2 * idx], self.data[2 * idx + 1])
            idx >>= 1

    def __len__(self):
        return self._len

    def query(self, start, stop):
        if start == stop:
            return self.__getitem__(start)
        start += self._size
        stop += self._size
        res = self._default
        while start < stop:
            if start & 1:
                res = self._func(res, self.data[start])
                start += 1
            if stop & 1:
                stop -= 1
                res = self._func(res, self.data[stop])
            start >>= 1
            stop >>= 1
        return res

    def __repr__(self):
        return 'SegmentTree({0})'.format(self.data)
zzz = inp()
for _ in range(zzz):

    def solve():
        n = inp()
        s = input().strip()
        gains = [0]
        cur = 0
        if n == 1:
            print(0)
            return
        for i in range(n):
            if i < n // 2:
                if s[i] == 'L':
                    gain = -i + n - i - 1
                    gains.append(gain)
                    cur += i
                else:
                    cur += n - i - 1
                    gains.append(0)
            elif i >= n // 2:
                if s[i] == 'R':
                    gain = i - n + i + 1
                    gains.append(gain)
                    cur += n - i - 1
                else:
                    gains.append(0)
                    cur += i
            else:
                gains.append(0)
                cur += n - i - 1
        gains.sort(reverse=True)
        pref = [0]
        for i in range(len(gains)):
            pref.append(pref[-1] + gains[i])
        pref = pref[1:]
        print(' '.join([str(cur + pref[i]) for i in range(len(pref) - 1)]))
        return
    solve()

Solution (Python):
from bisect import bisect_right
import math
from queue import PriorityQueue
from sys import stdin, stdout
import collections
(input, print) = (stdin.readline, stdout.write)

def str_input():
    s = input()
    return s[:len(s) - 1]

def char_list_input():
    s = input()
    return list(s[:len(s) - 1])

def list_input(type):
    return list(map(type, input().split()))

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

def main():
    t = int(input())
    for _ in range(t):
        n = int(input())
        s = str_input()
        val = 0
        for i in range(n):
            if s[i] == 'R':
                val += n - 1 - i
            else:
                val += i
        l = 0
        r = n - 1
        ans = []
        while l <= r:
            if s[l] != 'R':
                val += n - 1 - l - l
                ans.append(val)
            l += 1
            if l <= r and s[r] != 'L':
                val += r - (n - 1) + r
                ans.append(val)
            r -= 1
        while len(ans) != n:
            if len(ans) == 0:
                ans.append(val)
            else:
                ans.append(ans[-1])
        for i in ans:
            print(f'{i} ')
        print('\n')
if __name__ == '__main__':
    main()