A Simple Task (Codeforces 558E)
Tags: Others, strings

This task is very simple. Given a string S of length n and q queries each query is on the format i j k which means sort the substring consisting of the characters from i to j in non-decreasing order if k = 1 or in non-increasing order if k = 0.Output the final string after applying the queries.

Input: The first line will contain two integers n, q (1 ≤ n ≤ 105, 0 ≤ q ≤ 50 000), the length of the string and the number of queries respectively. Next line contains a string S itself. It contains only lowercase English letters.Next q lines will contain three integers each i, j, k (1 ≤ i ≤ j ≤ n, ).

Output: Output one line, the string S after applying the queries.

Note: First sample test explanation:

Sample Inputs:
10 5
abacdabcda
7 10 0
5 8 1
1 4 0
3 6 0
7 10 1

10 1
agjucbvdfk
1 10 1

Sample Outputs:
cbcaaaabdd

abcdfgjkuv

Solution (Python):
import sys, os, io
input = io.BytesIO(os.read(0, os.fstat(0).st_size)).readline

def binary_trie():
    (G0, G1, cnt) = ([-1], [-1], [0])
    return (G0, G1, cnt)

def insert(x, l):
    j = 0
    for i in range(l, -1, -1):
        cnt[j] += 1
        if x & pow2[i]:
            if G1[j] == -1:
                G0.append(-1)
                G1.append(-1)
                cnt.append(0)
                G1[j] = len(cnt) - 1
            j = G1[j]
        else:
            if G0[j] == -1:
                G0.append(-1)
                G1.append(-1)
                cnt.append(0)
                G0[j] = len(cnt) - 1
            j = G0[j]
    cnt[j] += 1
    return

def erase(x, l):
    j = 0
    for i in range(l, -1, -1):
        cnt[j] -= 1
        if x & pow2[i]:
            j = G1[j]
        else:
            j = G0[j]
    cnt[j] -= 1
    return

def kth_min(k, l):
    j = 0
    ans = 0
    for i in range(l, -1, -1):
        if not G0[j] == -1 and cnt[G0[j]] >= k:
            j = G0[j]
        else:
            ans += pow2[i]
            if not G0[j] == -1:
                k -= cnt[G0[j]]
            j = G1[j]
    return ans

def count_min(k, l):
    j = 0
    ans = 0
    for i in range(l, -1, -1):
        if k & pow2[i]:
            if G0[j] ^ -1:
                ans += cnt[G0[j]]
            j = G1[j]
        else:
            j = G0[j]
    return ans
(n, q) = map(int, input().split())
s = list(input().rstrip())
s = [-1] + [i - 97 for i in s]
(G0, G1, cnt) = binary_trie()
l = 17
pow2 = [1]
for _ in range(l):
    pow2.append(2 * pow2[-1])
la = 0
u = [-1] * (n + 1)
v = [-1] * (n + 1)
for i in range(1, n + 1):
    if s[i] ^ s[la]:
        insert(i, l)
        la = i
        v[i] = s[i]
    u[la] = i
for _ in range(q):
    (i, j, k) = map(int, input().split())
    x = kth_min(count_min(i + 1, l), l)
    if x ^ i:
        insert(i, l)
        (u[x], u[i], v[i]) = (i - 1, u[x], v[x])
    y = kth_min(count_min(j + 1, l), l)
    if u[y] ^ j:
        insert(j + 1, l)
        (u[y], u[j + 1], v[j + 1]) = (j, u[y], v[y])
    z = count_min(i, l) + 1
    c = [0] * 26
    while z <= cnt[0]:
        x = kth_min(z, l)
        if x > j:
            break
        erase(x, l)
        c[v[x]] += u[x] - x + 1
        (u[x], v[x]) = (-1, -1)
    if k:
        (x, y, z) = (0, 26, 1)
    else:
        (x, y, z) = (25, -1, -1)
    for j in range(x, y, z):
        if not c[j]:
            continue
        insert(i, l)
        (u[i], v[i]) = (i + c[j] - 1, j)
        i += c[j]
i = 1
ans = []
while i <= n:
    ans.append(chr(v[i] + 97) * (u[i] - i + 1))
    i = u[i] + 1
sys.stdout.write(''.join(ans))

Solution (Python):
import sys, os, io
input = io.BytesIO(os.read(0, os.fstat(0).st_size)).readline

def binary_trie():
    (G0, G1, cnt) = ([-1], [-1], [0])
    return (G0, G1, cnt)

def insert(x, l):
    j = 0
    for i in range(l, -1, -1):
        cnt[j] += 1
        if x & pow2[i]:
            if G1[j] == -1:
                G0.append(-1)
                G1.append(-1)
                cnt.append(0)
                G1[j] = len(cnt) - 1
            j = G1[j]
        else:
            if G0[j] == -1:
                G0.append(-1)
                G1.append(-1)
                cnt.append(0)
                G0[j] = len(cnt) - 1
            j = G0[j]
    cnt[j] += 1
    return

def erase(x, l):
    j = 0
    for i in range(l, -1, -1):
        cnt[j] -= 1
        if x & pow2[i]:
            j = G1[j]
        else:
            j = G0[j]
    cnt[j] -= 1
    return

def kth_min(k, l):
    j = 0
    ans = 0
    for i in range(l, -1, -1):
        if not G0[j] == -1 and cnt[G0[j]] >= k:
            j = G0[j]
        else:
            ans += pow2[i]
            if not G0[j] == -1:
                k -= cnt[G0[j]]
            j = G1[j]
    return ans

def count_min(k, l):
    j = 0
    ans = 0
    for i in range(l, -1, -1):
        if k & pow2[i]:
            if G0[j] ^ -1:
                ans += cnt[G0[j]]
            j = G1[j]
        else:
            j = G0[j]
    return ans
(n, q) = map(int, input().split())
s = list(input().rstrip())
s = [-1] + [i - 97 for i in s]
(G0, G1, cnt) = binary_trie()
l = 17
pow2 = [1]
for _ in range(l):
    pow2.append(2 * pow2[-1])
la = 0
u = [-1] * (n + 1)
v = [-1] * (n + 1)
for i in range(1, n + 1):
    if s[i] ^ s[la]:
        insert(i, l)
        la = i
        v[i] = s[i]
    u[la] = i
for _ in range(q):
    (i, j, k) = map(int, input().split())
    x = kth_min(count_min(i + 1, l), l)
    if x ^ i:
        insert(i, l)
        (u[x], u[i], v[i]) = (i - 1, u[x], v[x])
    y = kth_min(count_min(j + 1, l), l)
    if u[y] ^ j:
        insert(j + 1, l)
        (u[y], u[j + 1], v[j + 1]) = (j, u[y], v[y])
    z = count_min(i, l) + 1
    c = [0] * 26
    while z <= cnt[0]:
        x = kth_min(z, l)
        if x > j:
            break
        erase(x, l)
        c[v[x]] += u[x] - x + 1
        (u[x], v[x]) = (-1, -1)
    if k:
        (x, y, z) = (0, 26, 1)
    else:
        (x, y, z) = (25, -1, -1)
    for j in range(x, y, z):
        if not c[j]:
            continue
        insert(i, l)
        (u[i], v[i]) = (i + c[j] - 1, j)
        i += c[j]
i = 1
ans = []
while i <= n:
    ans.append(chr(v[i] + 97) * (u[i] - i + 1))
    i = u[i] + 1
sys.stdout.write(''.join(ans))

Solution (Python):
import sys
import os
from operator import add
from io import BytesIO, IOBase

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')
BUFSIZE = 5096

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

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

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

def readInt():
    return int(input())

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

def readStr():
    return input().strip()

class LazySegTree:

    def _update(self, k):
        self.d[k] = self.op(self.d[2 * k], self.d[2 * k + 1])

    def _all_apply(self, k, f):
        self.d[k] = self.mapping(f, self.d[k], self.length[k])
        if k < self.size:
            self.lz[k] = self.composite(f, self.lz[k])

    def _push(self, k):
        self._all_apply(2 * k, self.lz[k])
        self._all_apply(2 * k + 1, self.lz[k])
        self.lz[k] = self.identity

    def mapping(self, a, x, l):
        if a == -1:
            return x
        if a == 0:
            return 0
        return l

    def composite(self, a, b):
        return a if a >= 0 else b

    def __init__(self, V, OP, E):
        self.n = len(V)
        self.log = (self.n - 1).bit_length()
        self.size = 1 << self.log
        self.d = [E for i in range(2 * self.size)]
        self.length = [0] * (2 * self.size)
        self.e = E
        self.op = OP
        self.identity = -1
        self.lz = [-1 for i in range(self.size)]
        for i in range(self.n):
            self.d[self.size + i] = V[i]
            self.length[self.size + i] = 1
        for i in range(self.size - 1, 0, -1):
            self._update(i)
            self.length[i] = self.length[2 * i] + self.length[2 * i + 1]

    def set(self, p, x):
        assert 0 <= p and p < self.n
        p += self.size
        for i in range(self.log, 0, -1):
            self._push(p >> i)
        self.d[p] = x
        for i in range(1, self.log + 1):
            self._update(p >> i)

    def get(self, p):
        assert 0 <= p and p < self.n
        p += self.size
        for i in range(self.log, 0, -1):
            self._push(p >> i)
        return self.d[p]

    def prod(self, l, r):
        assert 0 <= l and l <= r and (r <= self.n)
        if l == r:
            return self.e
        l += self.size
        r += self.size
        for i in range(self.log, 0, -1):
            if l >> i << i != l:
                self._push(l >> i)
            if r >> i << i != r:
                self._push(r >> i)
        (sml, smr) = (self.e, self.e)
        while l < r:
            if l & 1:
                sml = self.op(sml, self.d[l])
                l += 1
            if r & 1:
                r -= 1
                smr = self.op(self.d[r], smr)
            l >>= 1
            r >>= 1
        return self.op(sml, smr)

    def all_prod(self):
        return self.d[1]

    def apply_point(self, p, f):
        assert 0 <= p and p < self.n
        p += self.size
        for i in range(self.log, 0, -1):
            self._push(p >> i)
        self.d[p] = self.mapping(f, self.d[p], self.length[p])
        for i in range(1, self.log + 1):
            self._update(p >> i)

    def apply(self, l, r, f):
        assert 0 <= l and l <= r and (r <= self.n)
        if l == r:
            return
        l += self.size
        r += self.size
        for i in range(self.log, 0, -1):
            if l >> i << i != l:
                self._push(l >> i)
            if r >> i << i != r:
                self._push(r - 1 >> i)
        (l2, r2) = (l, r)
        while l < r:
            if l & 1:
                self._all_apply(l, f)
                l += 1
            if r & 1:
                r -= 1
                self._all_apply(r, f)
            l >>= 1
            r >>= 1
        (l, r) = (l2, r2)
        for i in range(1, self.log + 1):
            if l >> i << i != l:
                self._update(l >> i)
            if r >> i << i != r:
                self._update(r - 1 >> i)

    def max_right(self, l, g):
        assert 0 <= l and l <= self.n
        assert g(self.e)
        if l == self.n:
            return self.n
        l += self.size
        for i in range(self.log, 0, -1):
            self._push(l >> i)
        sm = self.e
        while 1:
            while i % 2 == 0:
                l >>= 1
            if not g(self.op(sm, self.d[l])):
                while l < self.size:
                    self._push(l)
                    l = 2 * l
                    if g(self.op(sm, self.d[l])):
                        sm = self.op(sm, self.d[l])
                        l += 1
                return l - self.size
            sm = self.op(sm, self.d[l])
            l += 1
            if l & -l == l:
                break
        return self.n

    def min_left(self, r, g):
        assert 0 <= r and r <= self.n
        assert g(self.e)
        if r == 0:
            return 0
        r += self.size
        for i in range(self.log, 0, -1):
            self._push(r - 1 >> i)
        sm = self.e
        while 1:
            r -= 1
            while r > 1 and r % 2:
                r >>= 1
            if not g(self.op(self.d[r], sm)):
                while r < self.size:
                    self._push(r)
                    r = 2 * r + 1
                    if g(self.op(self.d[r], sm)):
                        sm = self.op(self.d[r], sm)
                        r -= 1
                return r + 1 - self.size
            sm = self.op(self.d[r], sm)
            if r & -r == r:
                break
        return 0
(n, q) = readInts()
s = [ord(c) - ord('a') for c in readStr()]
seg = [LazySegTree([int(v == i) for v in s], add, 0) for i in range(26)]
for _ in range(q):
    (i, j, k) = readInts()
    freq = [seg[x].prod(i - 1, j) for x in range(26)]
    (f, b) = (i - 1, j - 1)
    for x in range(26):
        if freq[x]:
            seg[x].apply(i - 1, j, 0)
            if k:
                seg[x].apply(f, f + freq[x], 1)
                f += freq[x]
            else:
                seg[x].apply(b + 1 - freq[x], b + 1, 1)
                b -= freq[x]
ans = []
length = 1 << (n - 1).bit_length()
for j in range(26):
    for i in range(length):
        seg[j]._push(i)
for i in range(n):
    for j in range(26):
        if seg[j].d[length + i]:
            ans.append(chr(j + ord('a')))
            break
print(''.join(ans))