# Competitive Programing Typical 90 Problem day17

Day 17.

There are 3 types of solutions.

1st code is below.

#1st solution

n, M = map(int,input().split())
lr =
for i in range(M):
l,r = map(int,input().split())
lr.append((l,r))

for i in range(M-1):
a, b = lr[i]
for j in range(i+1,M):
c,d = lr[j]
if a<c<b<d or c<a<d<b:

2nd code is below.

#2nd solution
n, m = map(int,input().split())
lr =
cnt = *n
cntl = *n
cntr = *n
posr = [ for j in range(n)]
for i in range(m):
l,r = map(int,input().split())
lr.append((l,r))
cnt[l-1]+= 1
cnt[r-1]+= 1
cntl[l-1]+= 1
cntr[r-1]+= 1
posr[r-1].append(l-1)

cntrs = cntr[:1] + *(n-1)
for i in range(n-1):
cntrs[i+1] = cntrs[i] + cntr[i+1]

ans1 = 0
for i in range(n):
ans1 += cnt[i]*(cnt[i]-1)//2

ans2 = 0
for i in range(n):
if i > 0:
ans2 += cntl[i] * cntrs[i-1]

ans3 = 0
weight = *n
for i in range(n):
for j in posr[i]:
for k in range(j+1,n):
ans3 += weight[k]
for j in posr[i]:
weight[j] += 1

print(m*(m-1)//2 - ans1-ans2-ans3)

3rd code is below.

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

class BIT:
def __init__(selfn):
self.size = n
self.tree =  * (n+1)

def sum(selfi):
s = 0
while i > 0:
s += self.tree[i]
i -= i&-i
return s

while i <= self.size:
self.tree[i] += x
i += i&-i

bitl= BIT(n+2)
bitr = BIT(n+2)

lr =
for i in range(m):
l,r = map(int,input().split())
lr.append*1

lr.sort(key = lambda x :(x,-x))

ans = 0
for l,in lr:
ans += bitl.sum(l-1)-bitr.sum(l)
print(ans)
• express conditions in equation
• thinking of complementary event
• because in some cases, it it easy to classify or calculate.
• using Binary Indexed Tree.
• to successively calculate and memorize information quickly
• adding some value on element of arrays
• summation of some area of arrays
• As I said in the past blog, Order is really important thing when we want to apply some algorithm.
• This last solution is somehow greedy.
• Maybe, the problem using 1 array is related to the some order.
• but it is hard to understand what kind of order it (data) follows.

Bye!

*1:l,r