Submission #65693338

Source Code Expand

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
def li():return list(map(int,input().split()))
from atcoder.fenwicktree import FenwickTree
n,m=li()
l=[]
for _ in range(m):
    a,b=li()
    if a>b:
        a,b=b,a
    l.append((a,b))
q=int(input())
C=[]
D=[]
for _ in range(q):
    c,d=li()
    C.append(c)
    D.append(d)
nn=2*n
 
 
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX

def li():return list(map(int,input().split()))
from atcoder.fenwicktree import FenwickTree


n,m=li()
l=[]
for _ in range(m):
    a,b=li()
    if a>b:
        a,b=b,a
    l.append((a,b))
q=int(input())
C=[]
D=[]
for _ in range(q):
    c,d=li()
    C.append(c)
    D.append(d)

nn=2*n

end=[0]*(nn+2)
for a,b in l:
    end[a]+=1
    end[b]+=1

pre=[0]*(nn+2)
for i in range(1,nn+2):
    pre[i]=pre[i-1]+end[i]
dev=[]
for j in range(q):
    l,r=C[j],D[j]
    if l<r:
        dev.append((l,r,j))
    else:
        dev.append((l,nn+1,j))
        dev.append((0,r,j))

l.sort(reverse=True)
dev.sort(reverse=True)

ft=FenwickTree(nn+2)
inside=[0]*q
idx=0
for l,r ,id in dev:
    while idx<m and l[idx][0]>l:
        b=l[idx][1]
        ft.add(b,1)
        idx+=1
    inside[id]+=ft.sum(r-1)
for j in range(q):
    l,r=C[j],D[j]
    if l<r:
        e=pre[r-1]-pre[l]
    else:
        e=pre[nn]-pre[l]+pre[r-1]-pre[0]
    ans=e-2*inside[j]
    print(ans)

Submission Info

Judge Result