Circular RMQ (Codeforces 52C)
Tags: Others, data structures

You are given circular array a0, a1, ..., an - 1. There are two types of operations with it:   inc(lf, rg, v) — this operation increases each element on the segment [lf, rg] (inclusively) by v;  rmq(lf, rg) — this operation returns minimal value on the segment [lf, rg] (inclusively). Assume segments to be circular, so if n = 5 and lf = 3, rg = 1, it means the index sequence: 3, 4, 0, 1.Write program to process given sequence of operations.

Input: The first line contains integer n (1 ≤ n ≤ 200000). The next line contains initial state of the array: a0, a1, ..., an - 1 ( - 106 ≤ ai ≤ 106), ai are integer. The third line contains integer m (0 ≤ m ≤ 200000), m — the number of operartons. Next m lines contain one operation each. If line contains two integer lf, rg (0 ≤ lf, rg ≤ n - 1) it means rmq operation, it contains three integers lf, rg, v (0 ≤ lf, rg ≤ n - 1; - 106 ≤ v ≤ 106) — inc operation.

Output: For each rmq operation write result for it. Please, do not use %lld specificator to read or write 64-bit integers in C++. It is preffered to use cout (also you may use %I64d).


Sample Inputs:
4
1 2 3 4
4
3 0
3 0 -1
0 1
2 1

Sample Outputs:
1
0
0

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

class LazySegmentTree:

    def __init__(self, data, default=inf, func=min):
        """"""
        self._default = default
        self._func = func
        self._len = len(data)
        self._size = _size = 1 << (self._len - 1).bit_length()
        self._lazy = [0] * (2 * _size)
        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 __len__(self):
        return self._len

    def _push(self, idx):
        """"""
        (q, self._lazy[idx]) = (self._lazy[idx], 0)
        self._lazy[2 * idx] += q
        self._lazy[2 * idx + 1] += q
        self.data[2 * idx] += q
        self.data[2 * idx + 1] += q

    def _update(self, idx):
        """"""
        for i in reversed(range(1, idx.bit_length())):
            self._push(idx >> i)

    def _build(self, idx):
        """"""
        idx >>= 1
        while idx:
            self.data[idx] = self._func(self.data[2 * idx], self.data[2 * idx + 1]) + self._lazy[idx]
            idx >>= 1

    def add(self, start, stop, value):
        """"""
        start = start_copy = start + self._size
        stop = stop_copy = stop + self._size
        while start < stop:
            if start & 1:
                self._lazy[start] += value
                self.data[start] += value
                start += 1
            if stop & 1:
                stop -= 1
                self._lazy[stop] += value
                self.data[stop] += value
            start >>= 1
            stop >>= 1
        self._build(start_copy)
        self._build(stop_copy - 1)

    def query(self, start, stop, default=inf):
        """"""
        start += self._size
        stop += self._size
        self._update(start)
        self._update(stop - 1)
        res = 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 'LazySegmentTree({0})'.format(self.data)
n = int(input())
a = [int(i) for i in input().split()]
q = int(input())
st = LazySegmentTree(a)
for i in range(q):
    qi = [int(i) for i in input().split()]
    if len(qi) == 3:
        if qi[0] > qi[1]:
            st.add(qi[0], n, qi[2])
            st.add(0, qi[1] + 1, qi[2])
        else:
            st.add(qi[0], qi[1] + 1, qi[2])
    else:
        if qi[0] > qi[1]:
            ans = min(st.query(qi[0], n), st.query(0, qi[1] + 1))
        else:
            ans = st.query(qi[0], qi[1] + 1)
        print(ans)

Solution (Python):
import os, sys
from io import IOBase, BytesIO
py2 = round(0.5)
if py2:
    from future_builtins import ascii, filter, hex, map, oct, zip
    range = xrange
BUFSIZE = 8192

class FastIO(BytesIO):
    newlines = 0

    def __init__(self, file):
        self._file = file
        self._fd = file.fileno()
        self.writable = 'x' in file.mode or 'w' in file.mode
        self.write = super(FastIO, self).write if self.writable else None

    def _fill(self):
        s = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
        self.seek((self.tell(), self.seek(0, 2), super(FastIO, self).write(s))[0])
        return s

    def read(self):
        while self._fill():
            pass
        return super(FastIO, self).read()

    def readline(self):
        while self.newlines == 0:
            s = self._fill()
            self.newlines = s.count(b'\n') + (not s)
        self.newlines -= 1
        return super(FastIO, self).readline()

    def flush(self):
        if self.writable:
            os.write(self._fd, self.getvalue())
            (self.truncate(0), self.seek(0))

class IOWrapper(IOBase):

    def __init__(self, file):
        self.buffer = FastIO(file)
        self.flush = self.buffer.flush
        self.writable = self.buffer.writable
        if py2:
            self.write = self.buffer.write
            self.read = self.buffer.read
            self.readline = self.buffer.readline
        else:
            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')
import sys

class ostream:

    def __lshift__(self, a):
        sys.stdout.write(str(a))
        return self
cout = ostream()
endl = '\n'
n = int(input())
a = list(map(int, input().split()))

class st:

    def __init__(self, size):
        N = 1
        h = 0
        while N < size:
            N <<= 1
            h += 1
        self.N = N
        self.h = h
        self.t = [float('inf')] * (2 * N)
        self.d = [0] * N

    def apply(self, p, value):
        self.t[p] += value
        if p < self.N:
            self.d[p] += value

    def build(self, p):
        t = self.t
        d = self.d
        while p > 1:
            p >>= 1
            t[p] = min(t[p << 1], t[p << 1 | 1]) + d[p]

    def rebuild(self):
        t = self.t
        for p in reversed(range(1, self.N)):
            t[p] = min(t[p << 1], t[p << 1 | 1])

    def push(self, p):
        d = self.d
        for s in range(self.h, 0, -1):
            i = p >> s
            if d[i] != 0:
                self.apply(i << 1, d[i])
                self.apply(i << 1 | 1, d[i])
                d[i] = 0

    def inc(self, l, r, value):
        if l >= r:
            return
        l += self.N
        r += self.N
        (l0, r0) = (l, r)
        while l < r:
            if l & 1:
                self.apply(l, value)
                l += 1
            if r & 1:
                r -= 1
                self.apply(r, value)
            l >>= 1
            r >>= 1
        self.build(l0)
        self.build(r0 - 1)

    def query(self, l, r):
        if l >= r:
            return float('inf')
        t = self.t
        l += self.N
        r += self.N
        self.push(l)
        self.push(r - 1)
        res = float('inf')
        while l < r:
            if l & 1:
                res = min(res, t[l])
                l += 1
            if r & 1:
                r -= 1
                res = min(t[r], res)
            l >>= 1
            r >>= 1
        return res
se = st(n)
N = se.N
for i in range(n):
    se.t[i + N] = a[i]
se.rebuild()
q = int(input())
for i in range(q):
    b = list(map(int, input().split()))
    if len(b) == 2:
        l = b[0]
        r = b[1]
        if l > r:
            print(min(se.query(l, n), se.query(0, r + 1)))
        else:
            print(se.query(l, r + 1))
    else:
        l = b[0]
        r = b[1]
        v = b[2]
        if l > r:
            se.inc(0, r + 1, v)
            se.inc(l, n, v)
        else:
            se.inc(l, r + 1, v)

Solution (Python):
import io, os
input = io.BytesIO(os.read(0, os.fstat(0).st_size)).readline
n = int(input())
a = list(map(int, input().split()))

class st:

    def __init__(self, size):
        N = 1
        h = 0
        while N < size:
            N <<= 1
            h += 1
        self.N = N
        self.h = h
        self.t = [float('inf')] * (2 * N)
        self.d = [0] * N

    def apply(self, p, value):
        self.t[p] += value
        if p < self.N:
            self.d[p] += value

    def build(self, p):
        t = self.t
        d = self.d
        while p > 1:
            p >>= 1
            t[p] = min(t[p << 1], t[p << 1 | 1]) + d[p]

    def rebuild(self):
        t = self.t
        for p in reversed(range(1, self.N)):
            t[p] = min(t[p << 1], t[p << 1 | 1])

    def push(self, p):
        d = self.d
        for s in range(self.h, 0, -1):
            i = p >> s
            if d[i] != 0:
                self.apply(i << 1, d[i])
                self.apply(i << 1 | 1, d[i])
                d[i] = 0

    def inc(self, l, r, value):
        if l >= r:
            return
        l += self.N
        r += self.N
        (l0, r0) = (l, r)
        while l < r:
            if l & 1:
                self.apply(l, value)
                l += 1
            if r & 1:
                r -= 1
                self.apply(r, value)
            l >>= 1
            r >>= 1
        self.build(l0)
        self.build(r0 - 1)

    def query(self, l, r):
        if l >= r:
            return float('inf')
        t = self.t
        l += self.N
        r += self.N
        self.push(l)
        self.push(r - 1)
        res = float('inf')
        while l < r:
            if l & 1:
                res = min(res, t[l])
                l += 1
            if r & 1:
                r -= 1
                res = min(t[r], res)
            l >>= 1
            r >>= 1
        return res
se = st(n)
N = se.N
for i in range(n):
    se.t[i + N] = a[i]
se.rebuild()
q = int(input())
for i in range(q):
    b = list(map(int, input().split()))
    if len(b) == 2:
        l = b[0]
        r = b[1]
        if l > r:
            print(min(se.query(l, n), se.query(0, r + 1)))
        else:
            print(se.query(l, r + 1))
    else:
        l = b[0]
        r = b[1]
        v = b[2]
        if l > r:
            se.inc(0, r + 1, v)
            se.inc(l, n, v)
        else:
            se.inc(l, r + 1, v)