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 Cumsum2d(object):
    def __init__(self, a):
        self.a = a
        self.h = len(a)
        self.w = len(a[0])
        self._cumsum = [[0 for _ in range(self.w + 1)] for _ in range(self.h + 1)]
        self._preprocess()

    def _preprocess(self):
        for i in range(1, self.h + 1):
            for j in range(1, self.w + 1):
                self._cumsum[i][j] = (
                    self.a[i - 1][j - 1]
                    + self._cumsum[i][j - 1]
                    + self._cumsum[i - 1][j]
                    - self._cumsum[i - 1][j - 1]
                )

    def query(self, h1, h2, w1, w2):
        return (
            self._cumsum[h2][w2]
            - self._cumsum[h1][w2]
            - self._cumsum[h2][w1]
            + self._cumsum[h1][w1]
        )


if __name__ == "__main__":
    N, M, Q = [int(x) for x in input().split(" ")]
    
    count = [[0 for _ in range(N + 1)] for _ in range(N + 1)]
    for _ in range(M):
        l, r = [int(x) for x in input().split(" ")]
        count[l][r] += 1

    cumsum = Cumsum2d(count)
    for _ in range(Q):
        p, q = [int(x) for x in input().split(" ")]
        print(cumsum.query(p, q + 1, p, q + 1))

Solution (Python):
from itertools import accumulate
from operator import add, mul
n,m,q=map(int,input().split())

a=[]
b=[]
for i in range(n):
    a.append([0]*(n))
    b.append([0]*(n))




'''
for i in range(m):
    l,r=map(int,input().split())
    
    
    for j in range(r-1,n):
        for k in range(l):
            a[j][k]+=1
'''
for i in range(m):
    l,r=map(int,input().split())
    
    a[l-1][r-1]+=1



for i in range(n):
    a[i]=list(accumulate(a[i]))



for i in range(n):
    for j in range(n-i-1):
        a[n-i-j-2][n-i-1]+=a[n-i-j-1][n-i-1]
        



'''
for l in range(n):
    for r in range(l,n):
        temp=a[r][l]
        for i in range(r,n):
            for j in range(0,l+1):
                b[i][j]+=temp
        
'''



for i in range(q):
    P,Q=map(int,input().split())
    print(a[(P-1)][(Q-1)])
'''
for i in range(que):
    p,q=MI()
    if p==1:
        ans=lis[q-1][q-1]
    else:
        ans=lis[q-1][q-1]-lis[p-2][q-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)]
li = [[0] * (n + 1) for i in range(n + 1)]
for i in lr:
    l, r = i[0], i[1]
    li[l][r] += 1
for i in range(1, n + 1):
    for j in range(1, n + 1):
        li[i][j] += li[i - 1][j] + li[i][j - 1] - li[i - 1][j - 1]
for i in pq:
    p, q = i[0], i[1]
    print(li[q][q] - li[p - 1][q] - li[q][p - 1] + li[p - 1][p - 1])

Solution (Python):
import sys
import numpy as np

read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline

in_n = lambda: int(readline())
in_nn = lambda: map(int, readline().split())
in_na = lambda: map(int, read().split())
in_s = lambda: readline().rstrip().decode('utf-8')


def count(tsum, l, r):

    return tsum[r][r] - tsum[l - 1][r] - tsum[r][l - 1] + tsum[l - 1][l - 1]


def main():
    N, M, Q = in_nn()
    t = in_na()
    t = list(zip(t, t))
    L = t[:M]
    p = t[M:]

    tsum = np.zeros((N + 1, N + 1), np.int32)
    for i in range(M):
        a, b = L[i]
        a, b = a, b
        tsum[a][b] += 1

    tsum = np.cumsum(tsum, axis=0)
    tsum = np.cumsum(tsum, axis=1)

    for i in range(Q):
        l, r = p[i]
        print(count(tsum, l, r))


if __name__ == '__main__':
    main()

Solution (Python):

n, m, q = map(int, input().split())
tmp = [[0] * 510 for _ in range(510)]
for _ in range(m):
    l, r = map(int, input().split())
    tmp[l][r] += 1
for i in range(1, 501):
    for j in range(1, 501):
        tmp[i][j] += tmp[i-1][j]
        tmp[i][j] += tmp[i][j-1]
        tmp[i][j] -= tmp[i-1][j-1]
for _ in range(q):
    ans = 0
    ll, rr = map(int, input().split())
    print(tmp[rr][rr]-tmp[rr][ll-1]-tmp[ll-1][rr]+tmp[ll-1][ll-1])

Solution (Python):
n, m, q = map(int, input().split())
tmp = [[0] * 510 for _ in range(510)]
for _ in range(m):
    l, r = map(int, input().split())
    tmp[l][r] += 1
for i in range(1, 501):
    for j in range(1, 501):
        tmp[i][j] += tmp[i-1][j]
        tmp[i][j] += tmp[i][j-1]
        tmp[i][j] -= tmp[i-1][j-1]
for _ in range(q):
    ans = 0
    ll, rr = map(int, input().split())
    print(tmp[rr][rr]-tmp[rr][ll-1]-tmp[ll-1][rr]+tmp[ll-1][ll-1])

Solution (Python):


import sys
input = sys.stdin.readline
sys.setrecursionlimit(10**7)
from collections import Counter, deque
from collections import defaultdict
from itertools import combinations, permutations, accumulate, groupby, product
from bisect import bisect_left,bisect_right
from heapq import heapify, heappop, heappush
from math import floor, ceil,pi,factorial
from operator import itemgetter
def I(): return int(input())
def MI(): return map(int, input().split())
def LI(): return list(map(int, input().split()))
def LI2(): return [int(input()) for i in range(n)]
def MXI(): return [[LI()]for i in range(n)]
def SI(): return input().rstrip()
def printns(x): print('\n'.join(x))
def printni(x): print('\n'.join(list(map(str,x))))
inf = 10**17
mod = 10**9 + 7

n,m,que=MI()
lis=[[0]*n for i in range(n)]
for i in range(m):
    l,r=MI()
    lis[l-1][r-1]+=1
for i in range(n):
    lis[i]=list(accumulate(lis[i]))
for i in range(n):
    for j in range(n-1):
        lis[j+1][i]+=lis[j][i]


for i in range(que):
    p,q=MI()
    if p==1:
        ans=lis[q-1][q-1]
    else:
        ans=lis[q-1][q-1]-lis[p-2][q-1]
    print(ans)

Solution (Python):


import sys
input = sys.stdin.readline
sys.setrecursionlimit(10**7)
from collections import Counter, deque
from collections import defaultdict
from itertools import combinations, permutations, accumulate, groupby, product
from bisect import bisect_left,bisect_right
from heapq import heapify, heappop, heappush
from math import floor, ceil,pi,factorial
from operator import itemgetter
def I(): return int(input())
def MI(): return map(int, input().split())
def LI(): return list(map(int, input().split()))
def LI2(): return [int(input()) for i in range(n)]
def MXI(): return [[LI()]for i in range(n)]
def SI(): return input().rstrip()
def printns(x): print('\n'.join(x))
def printni(x): print('\n'.join(list(map(str,x))))
inf = 10**17
mod = 10**9 + 7

n,m,que=MI()
lis=[[0]*n for i in range(n)]
for i in range(m):
    l,r=MI()
    lis[l-1][r-1]+=1
for i in range(n):
    lis[i]=list(accumulate(lis[i]))
for i in range(n):
    for j in range(n-1):
        lis[j+1][i]+=lis[j][i]


for i in range(que):
    p,q=MI()
    if p==1:
        ans=lis[q-1][q-1]
    else:
        ans=lis[q-1][q-1]-lis[p-2][q-1]
    print(ans)

Solution (Python):


import sys
input = sys.stdin.readline
sys.setrecursionlimit(10**7)
from collections import Counter, deque
from collections import defaultdict
from itertools import combinations, permutations, accumulate, groupby, product
from bisect import bisect_left,bisect_right
from heapq import heapify, heappop, heappush
from math import floor, ceil,pi,factorial
from operator import itemgetter
def I(): return int(input())
def MI(): return map(int, input().split())
def LI(): return list(map(int, input().split()))
def LI2(): return [int(input()) for i in range(n)]
def MXI(): return [[LI()]for i in range(n)]
def SI(): return input().rstrip()
def printns(x): print('\n'.join(x))
def printni(x): print('\n'.join(list(map(str,x))))
inf = 10**17
mod = 10**9 + 7

n,m,que=MI()
lis=[[0]*n for i in range(n)]
for i in range(m):
    l,r=MI()
    lis[l-1][r-1]+=1
for i in range(n):
    lis[i]=list(accumulate(lis[i]))

for i in range(que):
    p,q=MI()
    ans=0
    for i in range(p,q+1):
        if i==1:
            ans+=lis[i-1][q-1]
        else:
            ans+=lis[i-1][q-1]-lis[i-1][i-2]
    print(ans)

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

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

for i in range(N):
    for j in range(N):
        if i==0 and j==0:
            continue
        elif i==0:
            L[i][j]+=L[i][j-1]
        elif j==0:
            L[i][j]+=L[i-1][j]
        else:
            L[i][j]+=L[i-1][j]+L[i][j-1]-L[i-1][j-1]



for i in range(Q):
    p,q=map(int, input().split())
    p-=1
    q-=1
    if p==0:
        print(L[q][q])
    else:
        print(L[q][q]-L[p-1][q]-L[q][p-1]+L[p-1][p-1])

Solution (Python):


'''
N が小さいので、N^2 を考えると良いことが分かる。
'''

from collections import defaultdict

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

edges = [list(map(int, input().split())) for _ in range(M)]

data = defaultdict(int)                  

for i, j in edges:
    i -= 1
    j -= 1
    data[(i,j)] += 1

cum = [[0]*(N+1) for _ in range(N+1)]

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

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

Solution (Python):
N,M,Q=map(int,input().split())
L,R=0,0
X=[[0]*N for i in range(N)]
for i in range(M):
  L,R=map(int,input().split())
  X[L-1][R-1]+=1
Y=[[0]*(N+1) for i in range(N+1)]
for i in range(N):
  for j in range(N):
    Y[i+1][j+1]=X[i][j]+Y[i+1][j]+Y[i][j+1]-Y[i][j]
for i in range(Q):
  L,R=list(map(int,input().split()))
  print(Y[N][R]-Y[L-1][R])

Solution (Python):


N, M, Q = map(int, input().split())
G = [[0] * (N+1) for _ in range(N+1)]

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

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

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

Solution (Python):


N, M, Q = map(int, input().split())
G = [[0] * (N+1) for _ in range(N+1)]

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

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

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

Solution (Python):
N,M,Q = map(int,input().split())
l = [[0 for i in range(N)] for j in range(N)]
 
for _ in range(M):
    L,R = map(int,input().split())
    l[L-1][R-1] += 1
 
csum = [[0 for i in range(N+1)] for j in range(N+1)]
 
for i in range(1,N+1):
    for j in range(1,N+1):
        csum[i][j] = csum[i][j-1] + csum[i-1][j] - csum[i-1][j-1] + l[i-1][j-1]
 
for _ in range(Q):
    p,q = map(int,input().split())
    print(csum[q][q]-csum[q][p-1]-csum[p-1][q]+csum[p-1][p-1])

Solution (Python):
n, m, q = map(int, input().split())
lst = [[0 for j in range(n)] for i in range(n+1)]
for i in range(m):
    li, ri = map(int, input().split())
    ri -= 1
    lst[li][ri] += 1
query = []
for i in range(q):
    pi, qi = map(int, input().split())
    pi -= 1; qi -= 1
    query.append([pi, qi])

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

for pi, qi in query:
    ans = 0
    for i in range(pi, qi+1):
        ans += lst[qi+1][i] - lst[pi][i]
    print(ans)

Solution (Python):
N,M,Q = map(int,input().split())
l = [[0 for i in range(N)] for j in range(N)]

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

csum = [[0 for i in range(N+1)] for j in range(N+1)]

for i in range(1,N+1):
    for j in range(1,N+1):
        csum[i][j] = csum[i][j-1] + csum[i-1][j] - csum[i-1][j-1] + l[i-1][j-1]

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

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

N, M, Q = map(int, input().split())
A = [[0]*N for _ in range(N)]

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

acc = [[0]*(N+1) for _ in range(N+1)]

for i in range(N):
    for j in range(N):
        acc[i+1][j+1] = acc[i+1][j]+acc[i][j+1]-acc[i][j]+A[i][j]
    
for _ in range(Q):
    p, q = map(int, input().split())
    p -= 1
    q -= 1
    print(acc[q+1][q+1]-acc[q+1][p]-acc[p][q+1]+acc[p][p])

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

A = [[0]*n for i in range(n)]

for i in range(m):
    l, r = map(int, input().split())
    l, r = l-1, r-1
    A[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] + A[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[p][q+1] - s[q+1][p] + s[p][p]
    print(ans)

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

matrix = [[0]*(N+1) for _ in range(N+1)]
for _ in range(M):
    l,r = map(int, input().split())
    matrix[l][r] += 1
accmatrix = [[0]*(N+1) for _ in range(N+1)]
for l in range(1,N+1):
    accmatrix[l] = [x+y for x,y in zip(accmatrix[l-1],matrix[l])]
for l in range(1,N+1):
    lis = accmatrix[l]
    for r in range(1,N+1):
        lis[r] += lis[r-1]

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

Solution (Python):
import sys
sys.setrecursionlimit(10**8)
def ii(): return int(sys.stdin.readline())
def mi(): return map(int, sys.stdin.readline().split())
def li(): return list(map(int, sys.stdin.readline().split()))
def li2(N): return [list(map(int, sys.stdin.readline().split())) for _ in range(N)]
def dp2(ini, i, j): return [[ini]*i for _ in range(j)]



from itertools import accumulate 




class BIT:
    def __init__(self, n):
        self.n = n
        self.data = [0]*(n+1)
        self.el = [0]*(n+1)
    def sum(self, i):
        s = 0
        while i > 0:
            s += self.data[i]
            i -= i & -i
        return s
    def add(self, i, x):
        
        self.el[i] += x
        while i <= self.n:
            self.data[i] += x
            i += i & -i
    def get(self, i, j=None):
        if j is None:
            return self.el[i]
        return self.sum(j) - self.sum(i)

N, M, Q = mi()
bit = BIT(N)
lrpq = dp2(0, 3, M+Q)

for i in range(M):
    l, r = mi()
    lrpq[i][1] = l-1
    lrpq[i][2] = r-1

for i in range(M, M+Q):
    p, q = mi()
    lrpq[i][0] = i
    lrpq[i][1] = p-1
    lrpq[i][2] = q-1

lrpq = sorted(lrpq, key=lambda x:(x[2], x[0]))

ans = [0]*(Q)

for i in range(M+Q):
    if lrpq[i][0] == 0:
        
        bit.add(lrpq[i][1]+1, 1)
        
    else:
        bit.sum(lrpq[i][2])
        if lrpq[i][1] > 0:
            ans[lrpq[i][0]-M] = bit.sum(lrpq[i][2]+1) - bit.sum(lrpq[i][1])
        else:
            ans[lrpq[i][0]-M] = bit.sum(lrpq[i][2]+1)

for num in ans:
    print(num)

Solution (Python):
import sys
sys.setrecursionlimit(10**8)
def ii(): return int(sys.stdin.readline())
def mi(): return map(int, sys.stdin.readline().split())
def li(): return list(map(int, sys.stdin.readline().split()))
def li2(N): return [list(map(int, sys.stdin.readline().split())) for _ in range(N)]
def dp2(ini, i, j): return [[ini]*i for _ in range(j)]



from itertools import accumulate 




class BIT:
    def __init__(self, n):
        self.n = n
        self.data = [0]*(n+1)
        self.el = [0]*(n+1)
    def sum(self, i):
        s = 0
        while i > 0:
            s += self.data[i]
            i -= i & -i
        return s
    def add(self, i, x):
        
        self.el[i] += x
        while i <= self.n:
            self.data[i] += x
            i += i & -i
    def get(self, i, j=None):
        if j is None:
            return self.el[i]
        return self.sum(j) - self.sum(i)

N, M, Q = mi()
bit = BIT(N)
lrpq = dp2(0, 3, M+Q)

for i in range(M):
    l, r = mi()
    lrpq[i][1] = l-1
    lrpq[i][2] = r-1

for i in range(M, M+Q):
    p, q = mi()
    lrpq[i][0] = i
    lrpq[i][1] = p-1
    lrpq[i][2] = q-1

lrpq = sorted(lrpq, key=lambda x:(x[2], x[0]))

ans = [0]*(Q)

for i in range(M+Q):
    if lrpq[i][0] == 0:
        
        bit.add(lrpq[i][1]+1, 1)
        
    else:
        bit.sum(lrpq[i][2])
        if lrpq[i][1] > 0:
            ans[lrpq[i][0]-M] = bit.sum(lrpq[i][2]+1) - bit.sum(lrpq[i][1])
        else:
            ans[lrpq[i][0]-M] = bit.sum(lrpq[i][2]+1)

for num in ans:
    print(num)

Solution (Python):
import sys
sys.setrecursionlimit(10**8)
def ii(): return int(sys.stdin.readline())
def mi(): return map(int, sys.stdin.readline().split())
def li(): return list(map(int, sys.stdin.readline().split()))
def li2(N): return [list(map(int, sys.stdin.readline().split())) for _ in range(N)]
def dp2(ini, i, j): return [[ini]*i for _ in range(j)]



from itertools import accumulate 



def segfunc(a,b):
    return a+b

def init(init_val):
    
    for i in range(n):
        seg[i+num-1]=init_val[i]    
    
    for i in range(num-2,-1,-1) :
        seg[i]=segfunc(seg[2*i+1],seg[2*i+2]) 
    
def update(k,x):
    k += num-1
    seg[k] = x
    while k:
        k = (k-1)//2
        seg[k] = segfunc(seg[k*2+1],seg[k*2+2])
    
def query(p,q):
    if q<=p:
        return ide_ele
    p += num-1
    q += num-2
    res=ide_ele
    while q-p>1:
        if p&1 == 0:
            res = segfunc(res,seg[p])
        if q&1 == 1:
            res = segfunc(res,seg[q])
            q -= 1
        p = p//2
        q = (q-1)//2
    if p == q:
        res = segfunc(res,seg[p])
    else:
        res = segfunc(segfunc(res,seg[p]),seg[q])
    return res


n, M, Q = mi()


ide_ele = 0

num =2**(n-1).bit_length()
seg=[ide_ele]*2*num

L = [0]*n
init(L)

lrpq = dp2(0, 3, M+Q)

for i in range(M):
    l, r = mi()
    lrpq[i][1] = l-1
    lrpq[i][2] = r-1

for i in range(M, M+Q):
    p, q = mi()
    lrpq[i][0] = i
    lrpq[i][1] = p-1
    lrpq[i][2] = q-1

lrpq = sorted(lrpq, key=lambda x:(x[2], x[0]))

ans = [0]*(Q)

for i in range(M+Q):
    if lrpq[i][0] == 0:
        
        update(lrpq[i][1], seg[lrpq[i][1]+num-1]+1)
    else:
        ans[lrpq[i][0]-M] = query(lrpq[i][1], lrpq[i][2]+1)

for num in ans:
    print(num)

Solution (Python):
import sys
sys.setrecursionlimit(10**8)
def ii(): return int(sys.stdin.readline())
def mi(): return map(int, sys.stdin.readline().split())
def li(): return list(map(int, sys.stdin.readline().split()))
def li2(N): return [list(map(int, sys.stdin.readline().split())) for _ in range(N)]
def dp2(ini, i, j): return [[ini]*i for _ in range(j)]



from itertools import accumulate 


def segfunc(a,b):
    return a+b

def init(init_val):
    
    for i in range(n):
        seg[i+num-1]=init_val[i]    
    
    for i in range(num-2,-1,-1) :
        seg[i]=segfunc(seg[2*i+1],seg[2*i+2]) 
    
def update(k,x):
    k += num-1
    seg[k] = x
    while k:
        k = (k-1)//2
        seg[k] = segfunc(seg[k*2+1],seg[k*2+2])
    
def query(p,q):
    if q<=p:
        return ide_ele
    p += num-1
    q += num-2
    res=ide_ele
    while q-p>1:
        if p&1 == 0:
            res = segfunc(res,seg[p])
        if q&1 == 1:
            res = segfunc(res,seg[q])
            q -= 1
        p = p//2
        q = (q-1)//2
    if p == q:
        res = segfunc(res,seg[p])
    else:
        res = segfunc(segfunc(res,seg[p]),seg[q])
    return res


n, M, Q = mi()


ide_ele = 0

num =2**(n-1).bit_length()
seg=[ide_ele]*2*num

L = [0]*n
init(L)

lrpq = dp2(0, 3, M+Q)

for i in range(M):
    l, r = mi()
    lrpq[i][1] = l-1
    lrpq[i][2] = r-1

for i in range(M, M+Q):
    p, q = mi()
    lrpq[i][0] = i
    lrpq[i][1] = p-1
    lrpq[i][2] = q-1

lrpq = sorted(lrpq, key=lambda x:(x[2], x[0]))

ans = [0]*(Q)

for i in range(M+Q):
    if lrpq[i][0] == 0:
        
        update(lrpq[i][1], seg[lrpq[i][1]+num-1]+1)
    else:
        ans[lrpq[i][0]-M] = query(lrpq[i][1], lrpq[i][2]+1)

for num in ans:
    print(num)

Solution (Python):
import sys
sys.setrecursionlimit(10**8)
def ii(): return int(sys.stdin.readline())
def mi(): return map(int, sys.stdin.readline().split())
def li(): return list(map(int, sys.stdin.readline().split()))
def li2(N): return [list(map(int, sys.stdin.readline().split())) for _ in range(N)]
def dp2(ini, i, j): return [[ini]*i for _ in range(j)]



from itertools import accumulate 


def segfunc(a,b):
    return a+b

def init(init_val):
    
    for i in range(n):
        seg[i+num-1]=init_val[i]    
    
    for i in range(num-2,-1,-1) :
        seg[i]=segfunc(seg[2*i+1],seg[2*i+2]) 
    
def update(k,x):
    k += num-1
    seg[k] = x
    while k:
        k = (k-1)//2
        seg[k] = segfunc(seg[k*2+1],seg[k*2+2])
    
def query(p,q):
    if q<=p:
        return ide_ele
    p += num-1
    q += num-2
    res=ide_ele
    while q-p>1:
        if p&1 == 0:
            res = segfunc(res,seg[p])
        if q&1 == 1:
            res = segfunc(res,seg[q])
            q -= 1
        p = p//2
        q = (q-1)//2
    if p == q:
        res = segfunc(res,seg[p])
    else:
        res = segfunc(segfunc(res,seg[p]),seg[q])
    return res


n, M, Q = mi()


ide_ele = 0

num =2**(n-1).bit_length()
seg=[ide_ele]*2*num

L = [0]*n
init(L)

lrpq = dp2(0, 3, M+Q)

for i in range(M):
    l, r = mi()
    lrpq[i][1] = l-1
    lrpq[i][2] = r-1

for i in range(M, M+Q):
    p, q = mi()
    lrpq[i][0] = i
    lrpq[i][1] = p-1
    lrpq[i][2] = q-1

lrpq = sorted(lrpq, key=lambda x:(x[2], x[0]))

ans = [0]*(Q)

for i in range(M+Q):
    if lrpq[i][0] == 0:
        L[lrpq[i][1]] += 1
        update(lrpq[i][1], L[lrpq[i][1]])
    else:
        ans[lrpq[i][0]-M] = query(lrpq[i][1], lrpq[i][2]+1)

for num in ans:
    print(num)

Solution (Python):
import sys
sys.setrecursionlimit(10**8)
def ii(): return int(sys.stdin.readline())
def mi(): return map(int, sys.stdin.readline().split())
def li(): return list(map(int, sys.stdin.readline().split()))
def li2(N): return [list(map(int, sys.stdin.readline().split())) for _ in range(N)]
def dp2(ini, i, j): return [[ini]*i for _ in range(j)]



from itertools import accumulate 



N, M , Q = mi()
LR = li2(M)

dp = dp2(0, N+1, N+1)

for l, r in LR:
    dp[l][r] += 1

for i in range(N+1):
    dp[i] = list(accumulate(dp[i]))

for i in range(1, N+1):
    for j in range(N+1):
        dp[i][j] += dp[i-1][j]

for _ in range(Q):
    f, t = mi()
    f_ = max(0, f-1)
    print(dp[t][t] - dp[f_][t] - dp[t][f_] + dp[f_][f_])

Solution (Python):
import sys
sys.setrecursionlimit(10**8)
def ii(): return int(sys.stdin.readline())
def mi(): return map(int, sys.stdin.readline().split())
def li(): return list(map(int, sys.stdin.readline().split()))
def li2(N): return [list(map(int, sys.stdin.readline().split())) for _ in range(N)]
def dp2(ini, i, j): return [[ini]*i for _ in range(j)]



from itertools import accumulate 

N, M , Q = mi()
LR = li2(M)

dp = dp2(0, N+1, N+1)

for l, r in LR:
    dp[l][r] += 1

for i in range(N+1):
    dp[i] = list(accumulate(dp[i]))

for i in range(1, N+1):
    for j in range(N+1):
        dp[i][j] += dp[i-1][j]

for _ in range(Q):
    f, t = mi()
    f_ = max(0, f-1)
    print(dp[t][t] - dp[f_][t] - dp[t][f_] + dp[f_][f_])

Solution (Python):
import sys
sys.setrecursionlimit(10**8)
def ii(): return int(sys.stdin.readline())
def mi(): return map(int, sys.stdin.readline().split())
def li(): return list(map(int, sys.stdin.readline().split()))
def li2(N): return [list(map(int, sys.stdin.readline().split())) for _ in range(N)]
def dp2(ini, i, j): return [[ini]*i for _ in range(j)]



from itertools import accumulate 

N, M , Q = mi()
LR = li2(M)

dp = dp2(0, N, N)

for l, r in LR:
    dp[l-1][r-1] += 1

for i in range(N):
    dp[i] = list(accumulate(dp[i]))

for i in reversed(range(N-1)):
    for j in range(N):
        dp[i][j] += dp[i+1][j]

for _ in range(Q):
    f, t = mi()
    print(dp[f-1][t-1])

Solution (Python):

from collections import deque, Counter
from heapq import heappop, heappush
from bisect import bisect_right
from itertools import accumulate

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

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


if __name__ == "__main__":
    main()

Solution (Python):

def resolve():
    N, M, Q = list(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 for _ in range(N+1)] for _ in range(N+1)]
    for lr in LR:
        l, r = lr
        acc[l][r] += 1
    for i in range(1, N+1):
        for j in range(1, N+1):
            acc[i][j] += acc[i][j-1]
    for i in range(1, N+1):
        for j in range(1, N+1):
            acc[i][j] += acc[i-1][j]
    
    for pq in PQ:
        p, q = pq
        print(acc[q][q] - acc[p-1][q] - acc[q][p-1] + acc[p-1][p-1])


if '__main__' == __name__:
    resolve()

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

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

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

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

for qq in range(q):
  x,y=map(int,input().split())
  print(d[y][y]-d[y][x-1]-d[x-1][y]+d[x-1][x-1])

Solution (Python):
import sys

read = sys.stdin.buffer.read


def main():
    N, M, Q, *LRPQ = map(int, read().split())
    LR = LRPQ[: 2 * M]
    PQ = LRPQ[2 * M :]
    
    A = [[0] * (N + 1) for _ in range(N + 1)]
    for l, r in zip(LR[::2], LR[1::2]):
        A[l][r] += 1

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

    ans = [0] * Q
    for i, (p, q) in enumerate(zip(PQ[::2], PQ[1::2])):
        ans[i] = A[q][q] - A[q][p - 1] - A[p - 1][q] + A[p - 1][p - 1]

    print('\n'.join(map(str, ans)))
    return


if __name__ == '__main__':
    main()

Solution (Python):
import sys

read = sys.stdin.buffer.read


def main():
    N, M, Q, *LRPQ = map(int, read().split())
    LR = LRPQ[: 2 * M]
    PQ = LRPQ[2 * M :]

    A = [[0] * (N + 1) for _ in range(N + 1)]
    for l, r in zip(LR[::2], LR[1::2]):
        A[l][r] += 1

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

    ans = []
    for p, q in zip(PQ[::2], PQ[1::2]):
        ans.append(A[q][q] - A[q][p - 1] - A[p - 1][q] + A[p - 1][p - 1])

    print('\n'.join(map(str, ans)))
    return


if __name__ == '__main__':
    main()

Solution (Python):
import sys

read = sys.stdin.buffer.read


def main():
    N, M, Q, *LRPQ = map(int, read().split())
    LR = LRPQ[: 2 * M]
    PQ = LRPQ[2 * M :]
    
    A = [[0] * (N + 1) for _ in range(N + 1)]
    for l, r in zip(LR[::2], LR[1::2]):
        A[l][r] += 1

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

    ans = [0] * Q
    for i, (p, q) in enumerate(zip(PQ[::2], PQ[1::2])):
        ans[i] = A[q][q] - A[q][p - 1] - A[p - 1][q] + A[p - 1][p - 1]

    print('\n'.join(map(str, ans)))
    return


if __name__ == '__main__':
    main()

Solution (Python):
import sys

read = sys.stdin.read
readline = sys.stdin.readline
readlines = sys.stdin.readlines
sys.setrecursionlimit(10 ** 9)
INF = 1 << 60


def main():
    N, M, Q = map(int, readline().split())
    A = [[0] * (N + 1) for _ in range(N + 1)]
    for _ in range(M):
        l, r = map(int, readline().split())
        A[l][r] += 1

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

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

    print('\n'.join(map(str, ans)))
    return


if __name__ == '__main__':
    main()

Solution (Python):
import sys

read = sys.stdin.read
readline = sys.stdin.readline
readlines = sys.stdin.readlines
sys.setrecursionlimit(10 ** 9)
INF = 1 << 60


def main():
    N, M, Q = map(int, readline().split())
    A = [[0] * N for _ in range(N)]
    for _ in range(M):
        l, r = map(int, readline().split())
        A[l - 1][r - 1] += 1

    B = [[0] * (N + 1) for _ in range(N + 1)]
    for i in range(N):
        for j in range(N):
            B[i + 1][j + 1] = B[i][j + 1] + B[i + 1][j] - B[i][j] + A[i][j]

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

    print('\n'.join(map(str, ans)))
    return


if __name__ == '__main__':
    main()

Solution (Python):
import sys

read = sys.stdin.read
readline = sys.stdin.readline
readlines = sys.stdin.readlines
sys.setrecursionlimit(10 ** 9)
INF = 1 << 60


def main():
    N, M, Q = map(int, readline().split())
    A = [[0] * N for _ in range(N)]
    for _ in range(M):
        l, r = map(int, readline().split())
        A[l - 1][r - 1] += 1

    B = [[0] * (N + 1) for _ in range(N + 1)]
    for i in range(N):
        for j in range(N):
            B[i + 1][j + 1] = B[i][j + 1] + B[i + 1][j] - B[i][j] + A[i][j]

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

    print(*ans, sep='\n')
    return


if __name__ == '__main__':
    main()