Problem:
 Score: 400 points    Problem Statement  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.      Constraints   N is an integer between 1 and 500 (inclusive).  M is an integer between 1 and 200 \ 000 (inclusive).  Q is an integer between 1 and 100 \ 000 (inclusive).  1 \leq L_i \leq R_i \leq N  (1 \leq i \leq M)  1 \leq p_i \leq q_i \leq N  (1 \leq i \leq Q)         Input  Input is given from Standard Input in the following format:  N  M  Q  L_1  R_1  L_2  R_2  :  L_M  R_M  p_1  q_1  p_2  q_2  :  p_Q  q_Q       Output  Print Q lines. The i -th line should contain the number of the trains that runs strictly within the section from City p_i to City q_i .        Sample Input 1 2 3 1
1 1
1 2
2 2
1 2      Sample Output 1 3  As all the trains runs within the section from City 1 to City 2 , the answer to the only query is 3 .       Sample Input 2 10 3 2
1 5
2 8
7 10
1 7
3 10      Sample Output 2 1
1  The first query is on the section from City 1 to 7 . There is only one train that runs strictly within that section: Train 1 .
The second query is on the section from City 3 to 10 . There is only one train that runs strictly within that section: Train 3 .       Sample Input 3 10 10 10
1 6
2 9
4 5
4 7
4 7
5 8
6 6
6 7
7 9
10 10
1 8
1 9
1 10
2 8
2 9
2 10
3 8
3 9
3 10
1 10      Sample Output 3 7
9
10
6
8
9
6
7
8
10

Solution (Python):
class BIT:
    def __init__(self, n):
        self.n = n
        self.bit = [0]*(self.n+1) 

    def init(self, init_val):
        for i, v in enumerate(init_val):
            self.add(i, v)

    def add(self, i, x):
        
        i += 1 
        while i <= self.n:
            self.bit[i] += x
            i += (i & -i)

    def sum(self, i, j):
        
        
        return self._sum(j) - self._sum(i)

    def _sum(self, i):
        
        
        res = 0
        while i > 0:
            res += self.bit[i]
            i -= i & (-i)
        return res

import sys
import io, os

input = io.BytesIO(os.read(0,os.fstat(0).st_size)).readline

n, m, Q = map(int, input().split())
X = []
A = []
for i in range(m):
    l, r = map(int, input().split())
    l, r = l-1, r-1
    A.append(l)
    A.append(r)
    X.append((l, r, 0, i))
for i in range(Q):
    p, q = map(int, input().split())
    p, q = p-1, q-1
    A.append(p)
    A.append(q)
    X.append((p, q, 1, i))
X.sort(key=lambda x: (x[1], x[2]))

A = list(set(A))
A.sort()
d = {}
for i, a in enumerate(A):
    d[a] = i

bit = BIT(550)
ans = [-1]*Q
for l, r, t, i in X:
    l, r = d[l], d[r]
    if t == 0:
        bit.add(l, 1)
    else:
        ans[i] = bit.sum(l, r+1)
print(*ans, sep='\n')

Solution (Python):
class BIT:
    def __init__(self, n):
        self.n = n
        self.bit = [0]*(self.n+1) 

    def init(self, init_val):
        for i, v in enumerate(init_val):
            self.add(i, v)

    def add(self, i, x):
        
        i += 1 
        while i <= self.n:
            self.bit[i] += x
            i += (i & -i)

    def sum(self, i, j):
        
        
        return self._sum(j) - self._sum(i)

    def _sum(self, i):
        
        
        res = 0
        while i > 0:
            res += self.bit[i]
            i -= i & (-i)
        return res

import sys
import io, os

input = io.BytesIO(os.read(0,os.fstat(0).st_size)).readline

n, m, Q = map(int, input().split())
X = []
A = []
for i in range(m):
    l, r = map(int, input().split())
    l, r = l-1, r-1
    A.append(l)
    A.append(r)
    X.append((l, r, 0, i))
for i in range(Q):
    p, q = map(int, input().split())
    p, q = p-1, q-1
    A.append(p)
    A.append(q)
    X.append((p, q, 1, i))
X.sort(key=lambda x: (x[1], x[2]))

A = list(set(A))
A.sort()
d = {}
for i, a in enumerate(A):
    d[a] = i

bit = BIT(550)
ans = [-1]*Q
for l, r, t, i in X:
    l, r = d[l], d[r]
    if t == 0:
        bit.add(l, 1)
    else:
        ans[i] = bit.sum(l, r+1)
print(*ans, sep='\n')

Solution (Python):
class BIT:
    def __init__(self, n):
        self.n = n
        self.bit = [0]*(self.n+1) 

    def init(self, init_val):
        for i, v in enumerate(init_val):
            self.add(i, v)

    def add(self, i, x):
        
        i += 1 
        while i <= self.n:
            self.bit[i] += x
            i += (i & -i)

    def sum(self, i, j):
        
        
        return self._sum(j) - self._sum(i)

    def _sum(self, i):
        
        
        res = 0
        while i > 0:
            res += self.bit[i]
            i -= i & (-i)
        return res

import sys
import io, os
input = sys.stdin.buffer.readline


n, m, Q = map(int, input().split())
X = []
for i in range(m):
    l, r = map(int, input().split())
    l, r = l-1, r-1
    X.append((l, r, 0, i))
for i in range(Q):
    p, q = map(int, input().split())
    p, q = p-1, q-1
    X.append((p, q, 1, i))
X.sort(key=lambda x: (x[1], x[2]))
bit = BIT(550)
ans = [-1]*Q
for l, r, t, i in X:
    if t == 0:
        bit.add(l, 1)
    else:
        ans[i] = bit.sum(l, r+1)
print(*ans, sep='\n')

Solution (Python):
import sys
import io, os

input = io.BytesIO(os.read(0,os.fstat(0).st_size)).readline

n, m, Q = map(int, input().split())
C = [[0]*n for _ in range(n)]
for i in range(m):
    l, r = map(int, input().split())
    l, r = l-1, r-1
    C[l][r] += 1

s = [[0]*(n+1) for _ in range(n+1)]
for i in range(n):
    for j in range(n):
        s[i+1][j+1] = s[i+1][j] + s[i][j+1] - s[i][j] + C[i][j]

for i in range(Q):
    p, q = map(int, input().split())
    p, q = p-1, q-1
    ans = s[q+1][q+1]-s[q+1][p]-s[p][q+1]+s[p][p]
    print(ans)

Solution (Python):
import sys
import io, os

input = io.BytesIO(os.read(0,os.fstat(0).st_size)).readline

n, m, Q = map(int, input().split())
C = [[0]*n for _ in range(n)]
for i in range(m):
    l, r = map(int, input().split())
    l, r = l-1, r-1
    C[l][r] += 1

s = [[0]*(n+1) for _ in range(n+1)]
for i in range(n):
    for j in range(n):
        s[i+1][j+1] = s[i+1][j] + s[i][j+1] - s[i][j] + C[i][j]

for i in range(Q):
    p, q = map(int, input().split())
    p, q = p-1, q-1
    ans = s[q+1][q+1]-s[q+1][p]-s[p][q+1]+s[p][p]
    print(ans)

Solution (Python):
from sys import stdin
input = stdin.buffer.readline

def main():
    n, m, q = map(int, input().split())

    
    cs = [[0] * (n+1) for _ in range(n+1)]

    for _ in range(m):
        l, r = map(int, input().split())
        cs[l][r] += 1

    for l in range(1, n+1):
        for r in range(1, n+1):
            cs[l][r] += cs[l][r-1]
        for r in range(1, n+1):
            cs[l][r] += cs[l-1][r]

    ans = [-1] * q
    for lap in range(q):
        l, r = map(int, input().split())
        ans[lap] = cs[n][r] - cs[l-1][r]

    for i in ans:
        print(i)

main()

Solution (Python):
from sys import stdin
input = stdin.buffer.readline

def main():
    n, m, q = map(int, input().split())

    
    cs = [[0] * (n+1) for _ in range(n+1)]

    for _ in range(m):
        l, r = map(int, input().split())
        cs[l][r] += 1

    for l in range(1, n+1):
        for r in range(1, n+1):
            cs[l][r] += cs[l][r-1]
        for r in range(1, n+1):
            cs[l][r] += cs[l-1][r]

    ans = [-1] * q
    for lap in range(q):
        l, r = map(int, input().split())
        ans[lap] = cs[n][r] - cs[l-1][r]

    for i in ans:
        print(i)

main()

Solution (Python):


class BinaryIndexedTree:
    
    
    def __init__(self, n):
        self.size = n
        self.data = [0] * (n+1)

    
    
    def cumulative_sum(self, i):
        ans = 0
        while i > 0:
            ans += self.data[i]
            i -= i & -i
        return ans

    
    
    def add(self, i, x):
        i += 1
        while i <= self.size:
            self.data[i] += x
            i += i & -i

from sys import stdin
input = stdin.buffer.readline

def main():
    n, m, q = map(int, input().split())
    lr = [tuple(map(int, input().split())) for _ in range(m)]
    pq = [(0, 0, 0)] * q
    for ind in range(q):
        i, j = map(int, input().split())
        pq[ind] = (i, j, ind)

    lr.sort(key=lambda x: x[0])
    l = [i for i, j in lr]
    r = [j for i, j in lr]
    pq.sort(key=lambda x: x[0])

    BIT = BinaryIndexedTree(n+1)
    for i in r:
        BIT.add(i, 1)

    
    lr_ind = 0
    ans = [0] * q
    for left, right, pq_ind in pq:
        while lr_ind < m and l[lr_ind] < left:
            BIT.add(r[lr_ind], -1)
            lr_ind += 1

        ans[pq_ind] = BIT.cumulative_sum(right+1)

    for i in ans:
        print(i)

main()

Solution (Python):


class BinaryIndexedTree:
    
    
    def __init__(self, n):
        self.size = n
        self.data = [0] * (n+1)

    
    
    def cumulative_sum(self, i):
        ans = 0
        while i > 0:
            ans += self.data[i]
            i -= i & -i
        return ans

    
    
    def add(self, i, x):
        i += 1
        while i <= self.size:
            self.data[i] += x
            i += i & -i

from sys import stdin
input = stdin.buffer.readline

def main():
    n, m, q = map(int, input().split())
    lr = [tuple(map(int, input().split())) for _ in range(m)]
    pq = [(0, 0, 0)] * q
    for ind in range(q):
        i, j = map(int, input().split())
        pq[ind] = (i, j, ind)

    lr.sort(key=lambda x: x[0])
    l = [i for i, j in lr]
    r = [j for i, j in lr]
    pq.sort(key=lambda x: x[0])

    BIT = BinaryIndexedTree(n+1)
    for i in r:
        BIT.add(i, 1)

    
    lr_ind = 0
    ans = [0] * q
    for left, right, pq_ind in pq:
        while lr_ind < m and l[lr_ind] < left:
            BIT.add(r[lr_ind], -1)
            lr_ind += 1

        ans[pq_ind] = BIT.cumulative_sum(right+1)

    for i in ans:
        print(i)

main()

Solution (Python):
n,m,q=map(int,input().split())
a=[[0 for _ in range(n)] for _ in range(n)]

for i in range(m):
  x,y=map(int,input().split())
  a[x-1][y-1]+=1
  
for j in range(n):
  for k in range(1,n):
    a[j][k]=a[j][k]+a[j][k-1]
    
for l in range(q):
  ans=0
  L,R=map(int,input().split())
  for g in range(L-1,R):
    ans+=a[g][R-1]
  print(ans)

Solution (Python):



import sys 
from itertools import accumulate 
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines
N,M,Q = map(int,readline().split())
data = [[0]*(N+1) for _ in range(N+1)]

for _ in range(M):
    l,r = map(int,readline().split())
    data[l][r] += 1
    

for i in range(N+1):
    for j in range(N):
        data[i][j+1] += data[i][j]
        

for _ in range(Q):
    p,q = map(int,readline().split())
    ans = 0
    for i in range(p,q+1):
        ans += (data[i][q] - data[i][p-1])
    print(ans)

Solution (Python):
n,m,q = map(int, input().split())
lr=[list(map(int,input().split())) for i in range(m)]
pq=[list(map(int,input().split())) for i in range(q)]
arr = [[0 for _ in range(n+1)] for _ in range(n+1)]
for l,r in lr:
    arr[l][r]+=1
rui = [[0 for _ in range(n+1)] for _ in range(n+1)]

for i in range(1,n+1):
    for j in range(1,n+1):
        rui[i][j] = rui[i-1][j] + rui[i][j-1] - rui[i-1][j-1] + arr[i][j]

for p,q in pq:
    cnt = rui[q][q] - rui[p-1][q] - rui[q][p-1] + rui[p-1][p-1]
    print(cnt)

Solution (Python):
n,m,q = map(int, input().split())
lr=[list(map(int,input().split())) for i in range(m)]
pq=[list(map(int,input().split())) for i in range(q)]
arr = [[0 for _ in range(n)] for _ in range(n)]
for l,r in lr:
    arr[l-1][r-1]+=1
rui = [[0 for _ in range(n)] for _ in range(n)]

rui[0][0] = arr[0][0]

for i in range(1,n):
    rui[i][0] = rui[i-1][0] + arr[i][0]
for j in range(1,n):
    rui[0][j] = rui[0][j-1] + arr[0][j]

for i in range(1,n):
    for j in range(1,n):
        rui[i][j] = rui[i-1][j] + rui[i][j-1] - rui[i-1][j-1] + arr[i][j]

for p,q in pq:
    p-=1
    q-=1
    cnt = rui[q][q]
    if p!=0:
        cnt-=rui[p-1][q]
        cnt-=rui[q][p-1]
        cnt+=rui[p-1][p-1]

    print(cnt)

Solution (Python):
n, m, q = map(int, input().split())
lr = [list(map(int, input().split())) for _ in range(m)]
pq = [list(map(int, input().split())) for _ in range(q)]

acc = [[0] * (n + 1) for _ in range(n + 1)]
for l, r in lr:
    acc[l][r] += 1
for i in range(n):
    for j in range(n):
        tmp = acc[i][j + 1] + acc[i + 1][j] - acc[i][j]
        acc[i + 1][j + 1] += tmp

for p, q in pq:
    p -= 1
    ans = acc[q][q] - acc[p][q] - acc[q][p] + acc[p][p]
    print(ans)

Solution (Python):
from copy import deepcopy

n, m, q = map(int, input().split())
lr = [list(map(int, input().split())) for _ in range(m)]
pq = [list(map(int, input().split())) for _ in range(q)]

cnt = [[0] * (n + 1) for _ in range(n + 1)]
for l, r in lr:
    cnt[l][r] += 1

acc = deepcopy(cnt)
for i in range(n):
    for j in range(n):
        tmp = acc[i][j + 1] + acc[i + 1][j] - acc[i][j]
        acc[i + 1][j + 1] += tmp

for p, q in pq:
    p -= 1
    ans = acc[q][q] - acc[p][q] - acc[q][p] + acc[p][p]
    print(ans)

Solution (Python):
from copy import deepcopy

n, m, q = map(int, input().split())
lr = [list(map(int, input().split())) for _ in range(m)]
pq = [list(map(int, input().split())) for _ in range(q)]

cnt = [[0] * (n + 1) for _ in range(n + 1)]
for l, r in lr:
    cnt[l][r] += 1

acc = deepcopy(cnt)
for i in range(n):
    for j in range(n):
        tmp = acc[i][j + 1] + acc[i + 1][j] - acc[i][j]
        acc[i + 1][j + 1] += tmp

for p, q in pq:
    p -= 1
    ans = acc[q][q] - acc[p][q] - acc[q][p] + acc[p][p]
    print(ans)

Solution (Python):
n, m, q = map(int, input().split())
lr = [list(map(int, input().split())) for _ in range(m)]
pq = [list(map(int, input().split())) for _ in range(q)]

cnt = [[0] * (n + 1) for _ in range(n + 1)]
for l, r in lr:
    cnt[l][r] += 1

acc = [[0] * (n + 1) for _ in range(n + 1)]
for i in range(n):
    for j in range(n):
        tmp = acc[i][j + 1] + acc[i + 1][j] - acc[i][j]
        acc[i + 1][j + 1] = tmp + cnt[i + 1][j + 1]

for p, q in pq:
    p -= 1
    ans = acc[q][q] - acc[p][q] - acc[q][p] + acc[p][p]
    print(ans)

Solution (Python):
from numpy import *
N,M,Q = map(int,input().split())
G = zeros((N,N),int)

for m in range(M):
  l,r = map(int,input().split())
  G[N-l][r-1]+=1
  
G = cumsum(cumsum(G,axis=0),axis=1)

for n in range(Q):
  p,q = map(int,input().split())
  print(G[N-p][q-1])

Solution (Python):
import itertools

n,m,q=map(int,input().split()) 

LR=[[0]*(n+1) for i in range(n+1)]

for i in range(m):
  l,r=map(int,input().split())
  LR[l][r]+=1

for i in range(n):
  LR[i]=list(itertools.accumulate(LR[i]))


for i in range(q):
  l,r=map(int,input().split())
  ans=0
  for j in range(l,r+1):
    ans+=LR[j][r]-LR[j][l-1]

  print(ans)

Solution (Python):
n, m, Q = map(int, input().split())
d = [[0 for i in range(n + 1)] for i in range(n + 1)]
for i in range(m):
    l, r = map(int, input().split())
    d[l][r] += 1
for i in range(n + 1):
    for j in range(n):
        d[i][j + 1] += d[i][j]
for i in range(n + 1):
    for j in range(n):
        d[n - 1 - j][i] += d[n - j][i]
for i in range(Q):
    p, q = map(int, input().split())
    print(d[p][q])

Solution (Python):
import bisect
N,M,Q=map(int,input().split())
LR = []
for _ in range(M):
    LR.append(list(map(int,input().split())))
LR.sort()
L = [x for x,_ in LR]
R = [x for _,x in LR]


ans = [[0]*510 for _ in range(510)]
for i in range(1,501):
    idx_L = bisect.bisect_left(L,i)
    arr=R[idx_L:]
    for ar in arr:
        ans[i][ar]+=1
    for j in range(1,501):
        ans[i][j]=ans[i][j-1]+ans[i][j]
    
for _ in range(Q):
    l,r = map(int,input().split())
    print(ans[l][r])

Solution (Python):
"""
区間ごとに前処理しておけばよい
"""

N,M,Q = map(int,input().split())
memo = [[0]*(N+1) for _ in range(N+1)]
for _ in range(M):
    l,r = map(int,input().split())
    for j in range(r,N+1):
        memo[l][j] += 1

for _ in range(Q):
    p,q = map(int,input().split())
    ans = 0
    for i in range(p,q+1):
        ans += memo[i][q]
    print(ans)

Solution (Python):
n,m,q=map(int,input().split())
a=[[0]*(n+1) for _ in range(n+1)]
for _ in range(m):
  l,r=map(int,input().split())
  a[l][r]+=1
for i in range(n+1):
  for j in range(n):
    a[i][j+1]+=a[i][j]
for i in range(n):
  for j in range(n+1):
    a[i+1][j]+=a[i][j]
for _ in range(q):
  q,p=map(int,input().split())
  print(a[p][p]-a[p][q-1]-a[q-1][p]+a[q-1][q-1])

Solution (Python):
"""ABC106D AtCoder Express2 diff:1306
"""

N, M, Q = map(int, input().split())
x = [[0]*(N+1) for _ in range(N+1)]
for _ in range(M):
    L, R = map(int, input().split())
    x[L][R] += 1
cum = [[0]*(N+1) for _ in range(N+1)]
for i in range(1, N+1):
    for j in range(1, N+1):
        cum[i][j] = cum[i-1][j] + cum[i][j-1] - cum[i-1][j-1] + x[i][j]

for _ in range(Q):
    p, q = map(int, input().split())
    ans = cum[q][q] - cum[p-1][q] - cum[q][p-1] + cum[p-1][p-1]
    print(ans)

Solution (Python):
import numpy as np
N, M, Q = map(int, input().split()) 
grid = np.zeros((N+1, N+1), dtype=np.int64)
query = []
for _ in range(M):
    L, R = map(int, input().split())
    grid[L, R] += 1
cum_grid = grid.cumsum(axis=0).cumsum(axis=1)

ans_list = []
for _ in range(Q):
    p, q = map(int, input().split())
    ans = cum_grid[q, q] - cum_grid[p-1, q] - cum_grid[q, p-1] + cum_grid[p-1, p-1]
    ans_list.append(ans)

for ans in ans_list:
    print(ans)

Solution (Python):


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


def read_ints():
    return list(map(int, input().strip().split(' ')))


def solve():
    N, M, Q = read_ints()
    dp = [ [0 for _ in range(N)] for _ in range(N) ]
    left = [0 for _ in range(N)]
    right = [0 for _ in range(N)]
    length_to_pairs = [[] for _ in range(N)]

    for _ in range(M):
        L, R = read_ints()
        L -= 1
        R -= 1
        length_to_pairs[R-L].append((L, R))
        if L == R:
            dp[L][L] += 1
            right[L] += 1
            left[L] += 1

    for l in range(1, N):
        for i in range(N-l):
            dp[i][i+l] += right[i]+left[i+l]
            if l > 1:
                dp[i][i+l] += dp[i+1][i+l-1]
        for L, R in length_to_pairs[l]:
            dp[L][R] += 1
            right[L] += 1
            left[R] += 1

    for _ in range(Q):
        q0, q1 = read_ints()
        print(dp[q0-1][q1-1])


if __name__ == '__main__':
    solve()

Solution (Python):
n, m, Q = map(int, input().split())
lr = [[0 for _ in range(n + 1)] for _ in range(n + 1)]
for _ in range(m):
    l, r = map(int, input().split())
    lr[l][r] += 1

rui = [[0 for _ in range(n + 1)] for _ in range(n + 1)]
for i in range(1, n + 1):
    for j in range(1, n + 1):
        rui[i][j] = lr[i][j] + rui[i - 1][j] + rui[i][j - 1] - rui[i - 1][j - 1]
    
for _ in range(Q):
    p, q = map(int, input().split())
    p -= 1
    ans = rui[q][q] - rui[p][q] - rui[q][p] + rui[p][p]
    print(ans)

Solution (Python):
N, M, Q = map(int, input().split())
C = [[0]*N for _ in range(N)]
for _ in range(M):
    L, R = map(int, input().split())
    C[L-1][R-1] += 1
S = [[0]*(N+1) for _ in range(N+1)]
for r in range(N):
    for l in reversed(range(N)):
        S[l][r] = S[l+1][r] + C[l][r]
D = [[0]*(N+1) for _ in range(N+1)]
for l in range(N):
    for r in range(N):
        D[l][r] = D[l][r-1] + S[l][r]
for _ in range(Q):
    p, q = map(int, input().split())
    print(D[p-1][q-1])

Solution (Python):
def cum2D(a, H, W):
    cum = [[0]*(W+1) for _ in range(H+1)]
    for i in range(H):
        for j in range(W):
            cum[i+1][j+1] = cum[i][j+1] + cum[i+1][j] - cum[i][j] + a[i+1][j+1]
    return cum
    
n, m, q = map(int, input().split())
trains = [tuple(map(int, input().split())) for _ in range(m)]  
a = [[0]*(n+1) for j in range(n+1)]
for k in range(m):
    start, stop = trains[k]
    a[start][stop] += 1
cum = cum2D(a, n, n)          

for _ in range(q):
    p, q = map(int, input().split())
    print(cum[n][q] - cum[p-1][q])

Solution (Python):
import sys
import math
import copy
from heapq import heappush, heappop, heapify
from functools import cmp_to_key
from bisect import bisect_left, bisect_right
from collections import defaultdict, deque, Counter



input = sys.stdin.readline
getS = lambda: input().strip()
getN = lambda: int(input())
getList = lambda: list(map(int, input().split()))
getZList = lambda: [int(x) - 1 for x in input().split()]

INF = float("inf")
MOD = 10**9 + 7
divide = lambda x: pow(x, MOD-2, MOD)

class BIT():
    
    def __init__(self, n):
        self.n = n
        self.BIT = [0] * (n + 2)

    
    def query(self, idx):
        res_sum = 0
        while idx > 0:
            res_sum += self.BIT[idx]
            idx -= idx & (-idx)
        return res_sum

    
    def update(self, idx, x):
        
        while idx <= self.n:
            
            self.BIT[idx] += x
            idx += idx & (-idx)
        return

    def show(self):
        print(self.BIT)


def solve():
    n,m,q = getList()
    bt = BIT(n+1)
    sya = [defaultdict(int) for i in range(n+1)]
    for i in range(m):
        a,b = getList()
        sya[a][b] += 1
        bt.update(b, 1)

    si = []
    for i in range(q):
        l, r = getList()
        si.append((l, r, i))

    si.sort()
    ans = [0 for i in range(q)]

    cur = 1
    for ss in si:
        l, r, id = ss
        while(l > cur):
            for kk, vv in sya[cur].items():
                bt.update(kk, -vv)
                n -= vv
            cur += 1
        ans[id] = bt.query(r)

    print(*ans, sep="\n")





def main():
    n = getN()
    for _ in range(n):
        solve()

    return
if __name__ == "__main__":
    
    solve()

Solution (Python):
N,M,Q=map(int,input().split())
x=[[0]*N for _ in range(N)]
c=x
for i in range(M):
  l,r=map(lambda x:int(x)-1,input().split())
  x[l][r]+=1
for i in range(N):
  for j in range(N):
    if j==0:
      c[i][j]=x[i][j]
    else:
      c[i][j]=c[i][j-1]+x[i][j]
for i in range(Q):
  p,q=map(lambda x:int(x)-1,input().split())
  count=0
  for i in range(p,q+1):
    if p!=0:
      count+=c[i][q]-c[i][p-1]
    else:
      count+=c[i][q]
  print(count)

Solution (Python):
def cin():  return list(map(int,input().split()))

N, M, Q = list(map(int,input().split()))
v = [[0 for _ in range(N)] for _ in range(N)]
p = [[0 for _ in range(2)] for _ in range(Q)]

for _ in range(M):
    a, b = cin()
    v[a - 1][b - 1] += 1;

for i in range(Q):
    a, b = cin()
    p[i][0] = a - 1;
    p[i][1] = b - 1;
    
def d2_add(a):
    w = len(a[0])
    h = len(a)
    da = [[0] * w for j in range(h)]
    da[0][0] = a[0][0]
    for i in range(1, w):
        da[0][i] = da[0][i - 1] + a[0][i]
    for i in range(1, h):
        cnt_w = 0
        for j in range(w):
            cnt_w += a[i][j]
            da[i][j] = da[i - 1][j] + cnt_w
    return da

def d2_calc(da, x1, y1, x2, y2):
    if x1 > x2 or y1 > y2:  return 0
    if x1 == 0 and y1 == 0:  return da[x2][y2]
    if x1 == 0:  return da[x2][y2] - da[x2][y1 - 1]
    if y1 == 0:  return da[x2][y2] - da[x1 - 1][y2]
    return da[x2][y2] - da[x1 - 1][y2] - da[x2][y1 - 1] + da[x1 - 1][y1 - 1]

ret = d2_add(v)
for i in range(Q):
    ans = d2_calc(ret, p[i][0], p[i][0], p[i][1], p[i][1])
    print(ans)

Solution (Python):
def cin():  return list(map(int,input().split()))

N, M, Q = list(map(int,input().split()))
v = [[0 for _ in range(N)] for _ in range(N)]
p = [[0 for _ in range(2)] for _ in range(Q)]

for _ in range(M):
    a, b = cin()
    v[a - 1][b - 1] += 1;

for i in range(Q):
    a, b = cin()
    p[i][0] = a - 1;
    p[i][1] = b - 1;
    
def d2_add(a):
    w = len(a[0])
    h = len(a)
    da = [[0] * w for j in range(h)]
    da[0][0] = a[0][0]
    for i in range(1, w):
        da[0][i] = da[0][i - 1] + a[0][i]
    for i in range(1, h):
        cnt_w = 0
        for j in range(w):
            cnt_w += a[i][j]
            da[i][j] = da[i - 1][j] + cnt_w
    return da

def d2_calc(da, p, q, x, y):
    if p > x or q > y:  return 0
    if p == 0 and q == 0:  return da[x][y]
    if p == 0:  return da[x][y] - da[x][q - 1]
    if q == 0:  return da[x][y] - da[p - 1][y]
    return da[x][y] - da[p - 1][y] - da[x][q - 1] + da[p - 1][q - 1]

ret = d2_add(v)
for i in range(Q):
    ans = d2_calc(ret, p[i][0], p[i][0], p[i][1], p[i][1])
    print(ans)

Solution (Python):
N, M, Q = list(map(int,input().split()))
L = []
R = []
for i in range(M):
    in1, in2 = map(int,input().split())
    L.append(in1 - 1)
    R.append(in2 - 1)
p = []
q = []
for i in range(Q):
    in1, in2 = map(int,input().split())
    p.append(in1 - 1)
    q.append(in2 - 1)
    
a = [[0 for _ in range(N)] for _ in range(N)]
for i in range(M):
    a[L[i]][R[i]] += 1
    
def d2_add(a):
    w = len(a[0])
    h = len(a)
    da = [[0] * w for j in range(h)]
    da[0][0] = a[0][0]
    for i in range(1, w):
        da[0][i] = da[0][i - 1] + a[0][i]
    for i in range(1, h):
        cnt_w = 0
        for j in range(w):
            cnt_w += a[i][j]
            da[i][j] = da[i - 1][j] + cnt_w
    return da

def d2_calc(da, p, q, x, y):
    if p > x or q > y:  return 0
    if p == 0 and q == 0:  return da[x][y]
    if p == 0:  return da[x][y] - da[x][q - 1]
    if q == 0:  return da[x][y] - da[p - 1][y]
    return da[x][y] - da[p - 1][y] - da[x][q - 1] + da[p - 1][q - 1]

ret = d2_add(a)
for i in range(Q):
    ans = d2_calc(ret, p[i], p[i], q[i], q[i])
    print(ans)

Solution (Python):
import sys
from itertools import accumulate

input = sys.stdin.readline


def main():
    N, M, Q = map(int, input().split())
    LR = [None] * M
    for i in range(M):
        LR[i] = tuple(map(int, input().split()))
    pq = [None] * Q
    for i in range(Q):
        pq[i] = tuple(map(int, input().split()))

    S = [[0] * (N + 1) for _ in range(N + 1)]
    for L, R in LR:
        S[L][R] += 1
    for i in range(N + 1):
        S[i] = list(accumulate(S[i]))

    ans = [0] * Q
    for i, (p, q) in enumerate(pq):
        for j in range(p, q + 1):
            ans[i] += S[j][q] - S[j][p - 1]

    print("\n".join(map(str, ans)))


if __name__ == "__main__":
    main()

Solution (Python):
import sys

import numba as nb
import numpy as np

input = sys.stdin.readline


@nb.njit("i8[:](i8,i8,i8,i8[:,:],i8[:,:])", cache=True)
def solve(N, M, Q, LR, pq):
    S = np.zeros(shape=(N + 1, N + 1), dtype=np.int64)
    for i in range(M):
        L, R = LR[i]
        S[L][R] += 1
    for i in range(N + 1):
        S[i] = np.cumsum(S[i])

    ans = np.zeros(shape=Q, dtype=np.int64)
    for i in range(Q):
        p, q = pq[i]
        for j in range(p, q + 1):
            ans[i] += S[j][q] - S[j][p - 1]

    return ans


def main():
    N, M, Q = map(int, input().split())
    LR = np.zeros(shape=(M, 2), dtype=np.int64)
    for i in range(M):
        LR[i] = input().split()
    pq = np.zeros(shape=(Q, 2), dtype=np.int64)
    for i in range(Q):
        pq[i] = input().split()

    ans = solve(N, M, Q, LR, pq)

    print("\n".join(map(str, ans)))


if __name__ == "__main__":
    main()

Solution (Python):
n,m,q=map(int, input().split())

tab=[[0]*(n+1) for _ in range(n+1)]

for _ in range(m):
    l,r=map(int, input().split())
    tab[l][r]+=1

for i in range(1,n+1):
    for j in range(1,n):
        tab[i][j+1]+=tab[i][j]

for _ in range(q):
    p,q=map(int, input().split())
    ans=0
    for i in range(p,q+1):
        ans+=tab[i][q]-tab[i][p-1]
    print(ans)

Solution (Python):

def segfunc(x,y):
  return x+y

class SegmentTree(object):
    def __init__(self, A, dot, unit):
        n = 1 << (len(A) - 1).bit_length()
        tree = [unit] * (2 * n)
        for i, v in enumerate(A):
            tree[i + n] = v
        for i in range(n - 1, 0, -1):
            tree[i] = dot(tree[i << 1], tree[i << 1 | 1])
        self._n = n
        self._tree = tree
        self._dot = dot
        self._unit = unit

    def __getitem__(self, i):
        return self._tree[i + self._n]

    def update(self, i, v):
        i += self._n
        self._tree[i] = v
        while i != 1:
            i >>= 1
            self._tree[i] = self._dot(self._tree[i << 1], self._tree[i << 1 | 1])

    def add(self, i, v):
        self.update(i, self[i] + v)

    def sum(self, l, r): 
        l += self._n
        r += self._n
        l_val = r_val = self._unit
        while l < r:
            if l & 1:
                l_val = self._dot(l_val, self._tree[l])
                l += 1
            if r & 1:
                r -= 1
                r_val = self._dot(self._tree[r], r_val)
            l >>= 1
            r >>= 1
        return self._dot(l_val, r_val)


N,M,Q = map(int,input().split())
A = []
for i in range(M):
  a,b = map(int,input().split())
  A.append([a,b,-1]) 
for i in range(Q):
  a,b = map(int,input().split())
  A.append([a,b,i]) 
A.sort(key=lambda x : x[1]) 
MAX = 510
Range = [0 for _ in range(MAX)]
Tree = SegmentTree(Range,segfunc,0)

ans = [-1 for _ in range(Q)]
for i in range(M+Q):
  a,b,ID = A[i]
  if ID == -1:
    Tree.add(a,1)
  else:
    temp = Tree.sum(a,b+1) 
    ans[ID] = temp

print(*ans,sep="\n")

Solution (Python):



N,M,Q = map(int,input().split())

com = [[0] * 502 for i in range(502)]

for _ in range(M):
    L,R = map(int,input().split())
    com[L][R] += 1

for i in range(502):
    for j in range(1,502):
        com[i][j] += com[i][j-1]

for _ in range(Q):
    p,q = map(int,input().split())
    ans = 0
    for i in range(p,q+1):
        ans += com[i][q]
    print(ans)

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

N,M,Q = map(int,input().split())

com = [[0] * 502 for i in range(502)]

for _ in range(M):
    L,R = map(int,input().split())
    com[L][R] += 1

for i in range(502):
    for j in range(1,502):
        com[i][j] += com[i][j-1]

for _ in range(Q):
    p,q = map(int,input().split())
    ans = 0
    for i in range(p,q+1):
        ans += com[i][q]
    print(ans)

Solution (Python):
def main():
    n, m, q = map(int, input().split())
    trains = [[0 for _ in range(n + 1)] for _ in range(n + 1)]
    for _ in range(m):
        l, r = map(int, input().split())
        trains[l][r] += 1
    for i in range(n + 1):
        for j in range(1, n + 1):
            trains[i][j] += trains[i][j - 1]
    for _ in range(q):
        p, q = map(int, input().split())
        ans = 0
        for i in range(p, q + 1):
            ans += trains[i][q] - trains[i][p - 1]
        print(ans)


if __name__ == '__main__':
    main()

Solution (Python):
from collections import defaultdict
N, M, Q = map(int, input().split())
l2r = defaultdict(int)
l2acc = [[0]*(N+1) for _ in range(N)]
r2acc = [[0]*(N+1) for _ in range(N)]
for _ in range(M):
    l, r = map(int, input().split())
    l, r = l-1, r-1
    l2r[(l, r)] += 1
queries = []
for _ in range(Q):
    l, r = map(int, input().split())
    l, r = l-1, r-1
    queries.append((l, r))

for l in range(N):
    acc = 0
    for r in range(l, N):
        acc += l2r[(l, r)]
        l2acc[l][r] = acc

for r in range(N):
    acc = 0
    for l in range(r, -1, -1):
        acc += l2acc[l][r]
        r2acc[l][r] =acc

for l, r in queries:
    print(r2acc[l][r])