Problem: In Takahashi Kingdom, there is a east-west railroad and N cities along it, numbered 1, 2, 3, ..., N from west to east. A company called _AtCoder Express_ possesses M trains, and the train i runs from City L_i to City R_i (it is possible that L_i = R_i). Takahashi the king is interested in the following Q matters:    * The number of the trains that runs **strictly within** the section from City p_i to City q_i, that is, the number of trains j such that p_i \leq L_j and R_j \leq q_i.  Although he is genius, this is too much data to process by himself. Find the answer for each of these Q queries to help him.

Submission attempts (in order):
# -*- coding: utf-8 -*-
import bisect
import heapq
import math
import random
import sys
from collections import Counter, defaultdict, deque
from decimal import ROUND_CEILING, ROUND_HALF_UP, Decimal
from functools import lru_cache, reduce
from itertools import combinations, combinations_with_replacement, product, permutations
from operator import add, mul, sub

sys.setrecursionlimit(10000)


def read_int():
    return int(input())


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


def read_float():
    return float(input())


def read_float_n():
    return list(map(float, input().split()))


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


def read_str_n():
    return list(map(str, input().split()))


def error_print(*args):
    print(*args, file=sys.stderr)


def mt(f):
    import time

    def wrap(*args, **kwargs):
        s = time.time()
        ret = f(*args, **kwargs)
        e = time.time()

        error_print(e - s, 'sec')
        return ret

    return wrap


class SegmentTree():
    # to par: (n-1) // 2
    # to chr: 2n+1, 2n+2
    def __init__(self, N):
        self.__N = 2**int(math.ceil(math.log2(N)))
        self.__table = [[] for _ in range(self.__N * 2 - 1)]

    def update(self, idx, x):
        i = self.__N - 1 + idx  
        self.__table[i].append(x)
        while i != 0:
            pi = (i - 1) // 2  # parent
            self.__table[pi].append(x)
            # if self.__table[i] < self.__table[pi]:
            #     self.__table[pi] = self.__table[i]
            # else:
            #     break
            i = pi

    def __query(self, a, b, k, l, r):
        if r <= a or b <= l:
            return []
        if a <= l and r <= b:
            return self.__table[k]

        vl = self.__query(a, b, 2 * k + 1, l, (l + r) // 2)
        vr = self.__query(a, b, 2 * k + 2, (l + r) // 2, r)

        return vl + vr

    def query(self, a, b):
        return self.__query(a, b, 0, 0, self.__N)

    def print(self):
        print(self.__table)


@mt
def slv(N, M, Q, LR, PQ):

    st = SegmentTree(N)
    for i, (l, r) in enumerate(LR):
        st.update(l, i)
        st.update(r, i)

    for p, q in PQ:
        l = st.query(p, q+1)
        n = len(l)
        m = len(set(l))
        print(n-m)


def main():
    N, M, Q = read_int_n()
    LR = [read_int_n() for _ in range(M)]
    PQ = [read_int_n() for _ in range(Q)]
    slv(N, M, Q, LR, PQ)


if __name__ == '__main__':
    main()


# -*- coding: utf-8 -*-
import bisect
import heapq
import math
import random
import sys
from collections import Counter, defaultdict, deque
from decimal import ROUND_CEILING, ROUND_HALF_UP, Decimal
from functools import lru_cache, reduce
from itertools import combinations, combinations_with_replacement, product, permutations
from operator import add, mul, sub

sys.setrecursionlimit(10000)


def read_int():
    return int(input())


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


def read_float():
    return float(input())


def read_float_n():
    return list(map(float, input().split()))


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


def read_str_n():
    return list(map(str, input().split()))


def error_print(*args):
    print(*args, file=sys.stderr)


def mt(f):
    import time

    def wrap(*args, **kwargs):
        s = time.time()
        ret = f(*args, **kwargs)
        e = time.time()

        error_print(e - s, 'sec')
        return ret

    return wrap


class RectangleSum():
    def __init__(self, N, M):
        self.N = N
        self.M = M
        self.s = [[0] * (M+1) for _ in range(N+1)]

    def add(self, i, j, v):
        self.s[i+1][j+1] += v

    def build(self):
        for i in range(self.N+1):
            for j in range(self.M):
                self.s[i][j+1] += self.s[i][j]

        for i in range(self.N):
            for j in range(self.M+1):
                self.s[i+1][j] += self.s[i][j]

    def sum(self, i, j, h, w):
        ret = self.s[i][j]
        ret += self.s[i+h][j+w]
        ret -= self.s[i+h][j]
        ret -= self.s[i][j+w]

        return ret


@mt
def slv(N, M, Q, LR, PQ):
    rs = RectangleSum(N+1, N+1)
    for l, r in LR:
        rs.add(l, r, 1)

    rs.build()

    for p, q in PQ:
        print(rs.sum(p, p, q-p+1, q-p+1))


def main():
    N, M, Q = read_int_n()
    LR = [read_int_n() for _ in range(M)]
    PQ = [read_int_n() for _ in range(Q)]
    slv(N, M, Q, LR, PQ)


if __name__ == '__main__':
    main()


Verdicts: Runtime Error

Accepted