Distance Learning Courses in MAC (Codeforces 1935E)
Tags: Greedy, bitmasks

The New Year has arrived in the Master's Assistance Center, which means it's time to introduce a new feature!Now students are given distance learning courses, with a total of $$$n$$$ courses available. For the $$$i$$$-th distance learning course, a student can receive a grade ranging from $$$x_i$$$ to $$$y_i$$$.However, not all courses may be available to each student. Specifically, the $$$j$$$-th student is only given courses with numbers from $$$l_j$$$ to $$$r_j$$$, meaning the distance learning courses with numbers $$$l_j, l_j + 1, \ldots, r_j$$$.The creators of the distance learning courses have decided to determine the final grade in a special way. Let the $$$j$$$-th student receive grades $$$c_{l_j}, c_{l_j + 1}, \ldots, c_{r_j}$$$ for their distance learning courses. Then their final grade will be equal to $$$c_{l_j}$$$ $$$|$$$ $$$c_{l_j + 1}$$$ $$$|$$$ $$$\ldots$$$ $$$|$$$ $$$c_{r_j}$$$, where $$$|$$$ denotes the bitwise OR operation.Since the chatbot for solving distance learning courses is broken, the students have asked for your help. For each of the $$$q$$$ students, tell them the maximum final grade they can achieve.

Input: Each test consists of multiple test cases. The first line contains a single integer $$$t$$$ ($$$1 \leq t \leq 2 \cdot 10^4$$$) — the number of test cases. The description of the test cases follows.The first line of each test case contains a single integer $$$n$$$ ($$$1 \le n \le 2 \cdot 10^5$$$) — the number of distance learning courses.Each of the following $$$n$$$ lines contains two integers $$$x_i$$$ and $$$y_i$$$ ($$$0 \le x_i \le y_i < 2^{30}$$$) — the minimum and maximum grade that can be received for the $$$i$$$-th course.The next line contains a single integer $$$q$$$ ($$$1 \le q \le 2\cdot10^5$$$) — the number of students.Each of the following $$$q$$$ lines contains two integers $$$l_j$$$ and $$$r_j$$$ ($$$1 \le l_j \le r_j \le n$$$) — the minimum and maximum course numbers accessible to the $$$j$$$-th student.It is guaranteed that the sum of $$$n$$$ over all test cases and the sum of $$$q$$$ over all test cases do not exceed $$$2\cdot10^5$$$.

Output: For each test case, output $$$q$$$ integers, where the $$$j$$$-th integer is the maximum final grade that the $$$j$$$-th student can achieve.

Note: In the first test case:  The maximum grade for the first student is $$$1$$$:   On the first distance learning course, he will receive a grade of $$$1$$$.  Therefore, the final grade is $$$1$$$.  The maximum grade for the second student is $$$5$$$:   On the first distance learning course, he will receive a grade of $$$1$$$.  On the second distance learning course, he will receive a grade of $$$4$$$.  Therefore, the final grade is $$$1$$$ $$$|$$$ $$$4$$$ $$$=$$$ $$$5$$$. The maximum grade for the third student is $$$4$$$:   On the second distance learning course, he will receive a grade of $$$4$$$.  Therefore, the final grade is $$$4$$$. In the second test case:  The maximum grade for the first student is $$$15$$$:   On the first distance learning course, he will receive a grade of $$$7$$$.  On the second distance learning course, he will receive a grade of $$$4$$$.  On the third distance learning course, he will receive a grade of $$$8$$$.  Therefore, the final grade is $$$7$$$ $$$|$$$ $$$4$$$ $$$|$$$ $$$8$$$ $$$=$$$ $$$15$$$.  The maximum grade for the second student is $$$11$$$:   On the third distance learning course, he will receive a grade of $$$9$$$.  On the fourth distance learning course, he will receive a grade of $$$2$$$.  Therefore, the final grade is $$$9$$$ $$$|$$$ $$$2$$$ $$$=$$$ $$$11$$$. 

Sample Inputs:
3
2
0 1
3 4
3
1 1
1 2
2 2
4
1 7
1 7
3 10
2 2
5
1 3
3 4
2 3
1 4
1 2
6
1 2
2 2
0 1
1 1
3 3
0 0
4
3 4
5 5
2 5
1 2

Sample Outputs:
1 5 4 
15 11 15 15 7 
1 3 3 3

Solution (Python):
from sys import stdin

class SegTree:

    def __init__(self, vals, val=0):
        assert len(vals) > 0
        self.n = 1 << (len(vals) - 1).bit_length()
        self.vals = [0] * self.n
        self.vals.extend(vals)
        self.vals.extend([0] * (2 * self.n - len(self.vals)))
        vals = self.vals
        for v in reversed(range(1, self.n)):
            vals[v] = vals[v << 1] | vals[v << 1 | 1]

    def range_or(self, l, r):
        n = self.n
        vals = self.vals
        res = 0
        l += n
        r += n
        while l < r:
            if r & 1:
                res |= vals[r - 1]
            if l & 1:
                res |= vals[l]
                l += 1
            r >>= 1
            l >>= 1
        return res

def solve():
    n = int(stdin.readline())
    bit_counts = [[0] * (n + 1) for deg in range(30)]
    base_vals = [0] * n
    for i in range(n):
        (x, y) = map(int, stdin.readline().split())
        if x == y:
            base_vals[i] = x
        else:
            deg = (x ^ y).bit_length()
            base_vals[i] = x >> deg << deg
            for d in range(deg):
                if y & 1 << d != 0:
                    bit_counts[d][i + 1] = 1
    for d in range(30):
        arr = bit_counts[d]
        for i in range(1, n + 1):
            arr[i] += arr[i - 1]
    or_tree = SegTree(base_vals)
    q = int(stdin.readline())
    result = []
    for i in range(q):
        (l, r) = (int(w) - 1 for w in stdin.readline().split())
        res = or_tree.range_or(l, r + 1)
        for d in reversed(range(30)):
            n_ones = (res >> d & 1) + bit_counts[d][r + 1] - bit_counts[d][l]
            if n_ones > 1:
                res |= (1 << d + 1) - 1
                break
            if n_ones == 1:
                res |= 1 << d
        result.append(res)
    print(*result)
n_tests = int(stdin.readline())
for test_id in range(n_tests):
    solve()

Solution (Python):
import sys
input = sys.stdin.readline
K = 30

class SegmentTree:
    NEUTRAL = 0

    def merge(self, a, b):
        return a | b

    def __init__(self, n):
        self.n = n
        self.tree = [self.NEUTRAL for _ in range(2 * n)]

    def update(self, position, value):
        i = self.n + position
        self.tree[i] = value
        while i > 1:
            self.tree[i >> 1] = self.merge(self.tree[i], self.tree[i ^ 1])
            i >>= 1

    def calculate(self, left, right):
        res = self.NEUTRAL
        (l, r) = (left + self.n, right + self.n)
        while l < r:
            if l & 1:
                res = self.merge(res, self.tree[l])
                l += 1
            if r & 1:
                r -= 1
                res = self.merge(res, self.tree[r])
            l >>= 1
            r >>= 1
        return res

def solve():
    n = int(input())
    cnt = [[0] * K for _ in range(n + 1)]
    st = SegmentTree(n)
    for i in range(n):
        (x, y) = map(int, input().split())
        pref = 0
        for j in range(K - 1, -1, -1):
            if x >> j & 1 != y >> j & 1:
                break
            if x >> j & 1:
                pref |= 1 << j
        st.update(i, pref)
        y ^= pref
        for j in range(K):
            if y >> j & 1:
                cnt[i + 1][j] += 1
    for i in range(n):
        for j in range(K):
            cnt[i + 1][j] += cnt[i][j]
    q = int(input())
    res = [0] * q
    for idx in range(q):
        (l, r) = map(int, input().split())
        l -= 1
        ans = st.calculate(l, r)
        for j in range(K - 1, -1, -1):
            c = cnt[r][j] - cnt[l][j]
            if c > 1:
                ans |= (1 << j + 1) - 1
                break
            elif c == 1:
                if ans >> j & 1:
                    ans |= (1 << j) - 1
                    break
                ans |= 1 << j
        res[idx] = ans
    return ' '.join(map(str, res))
T = int(input())
out = [solve() for _ in range(T)]
print('\n'.join(map(str, out)))

Solution (Python):
import os, sys
from io import BytesIO, IOBase
from typing import *
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')
BITS = 30
LOG = 14

def lcp(x, y):
    w = 0
    for i in reversed(range(BITS)):
        (vx, vy) = (x >> i & 1, y >> i & 1)
        if vx != vy:
            break
        w |= vx << i
    return w

def main():
    n = int(input())
    pcount = [[0] * BITS for _ in range(n)]
    st = [[0] * n for _ in range(LOG)]
    for i in range(n):
        (x, y) = map(int, input().split())
        w = lcp(x, y)
        st[0][i] = w
        y -= w
        for j in range(BITS):
            pcount[i][j] = 1 if y >> j & 1 else 0
            if i > 0:
                pcount[i][j] += pcount[i - 1][j]
    for i in range(1, LOG):
        j = 0
        while j + (1 << i - 1) < n:
            st[i][j] = st[i - 1][j] | st[i - 1][j + (1 << i - 1)]
            j += 1

    def query(l, r):
        res = 0
        for i in reversed(range(LOG)):
            if 1 << i <= r - l + 1:
                res |= st[i][l]
                l += 1 << i
        return res
    q = int(input())
    ans = [0] * q
    for i in range(q):
        (l, r) = map(int, input().split())
        l -= 1
        r -= 1
        ans[i] = query(l, r)
        for j in reversed(range(BITS)):
            s = ans[i] >> j & 1
            cnt = pcount[r][j] + s
            if l > 0:
                cnt -= pcount[l - 1][j]
            if cnt >= 1:
                ans[i] |= 1 << j
            if cnt > 1:
                ans[i] |= (1 << j) - 1
                break
    print(*ans)
if __name__ == '__main__':
    T = int(input())
    for _ in range(T):
        main()