# Ôn tập mảng cộng dồn 2

### Bài 2: CSES - Restaurant Customers
#### a. Hướng tiếp cận
- Mảng cộng dồn/ đánh dấu
- Giới hạn của đề bài 10⁹ => Nếu như ta tạo mảng đánh dấu thì không thể đánh dấu tới 10⁹
=> Ta chỉ cần theo dõi lúc nào có giá trị thay đổi
=> lúc vào và lúc đi
=> lưu lại thời gian khách vào và đi và đánh dấu
#### b. Giải thuật
- Tạo ra mảng để đánh dấu giá trị thời gian và loại hành động vào hoặc đi và sắp xếp theo thứ tự thời gian
- tạo ra 1 mảng 2 chiều, lưu giá trị thời gian và đánh dấu hành động rồi sắp xếp lại
- Theo dõi biến động rồi tính và so sánh

#### c. Code

n = int(input())
a = []
for i in range(n):
    x,y = map(int,input().split())
    a.append((x,1))
    a.append((y,-1))

a.sort()

_max = 0
d = 0
#print(a)
for _,i in a:
    d += i
    _max = max(_max,d)

print(_max)

### Bài 3: Cộng tăng dần vào đoạn
#### a. Hướng tiếp cận
- Đánh dấu điểm thay đổi
- Cộng dồn các thay đổi
- Đánh dấu lại các điểm dừng
- Cộng dồn theo bước nhảy

n,m = map(int,input().split())
a = [0]*(n+5)
b = [0]*(n+5)
c = [0]*(n+5)
l = [0]*(m+5)
r = [0]*(m+5)

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

for i in range(1, n + 1):
    c[i] = b[i] + c[i-1]

for i in range(1, n + 1):
    print(c[i],end=" ")
    

#### Bài 4: codefcs04
##### 1. Yêu cầu
- Tìm và xác định vị trí đoạn con liên tiếp có tổng lớn nhất

##### 2. Phân tích
s[a:b] là lớn nhất
s[a:b] = s[b]-s[a-1]
s[a-1] nhỏ nhất
- cộng dồn
- đánh dấu giá trị cộng dồn nhỏ nhất từ b trờ về trước
-

7
-82 82 -36 49 -51 42 -50

f = [0,-82,0,-36,13,-38,4,-46] # cộng dồn
m = [0,0,-82,-82,-82,-82,-82,-82] # đánh dấu giá trị nhỏ nhất

s = [0,-82,82,46,95,44,86,36]

#### Bài 1: Siêu thị

3 4 3 2
1 1 1 4
2 2 3 3
2 3 3 4

##### Mảng cộng dồn 2 chiều
[Lý thuyết mảng cộng dồn 2 chiều](https://vnoi.info/wiki/algo/data-structures/prefix-sum-and-difference-array.md#m%E1%BA%A3ng-c%E1%BB%99ng-d%E1%BB%93n-hai-chi%E1%BB%81u)

https://meet.jit.si/ClinicalResolutionsNeedOverall

m = 3
n = 4
k = 3
s = 2
#a = [[3,   -6,    7,    8],
#[-7,   9,   4,  -4],  
#[1,    -1,    7,    1],  
#[4,     4,  -2,  -3]]
a = []
for i in range(m+2):
    a.append([0]*(n+2))
for i in range(k):
    x,y,u,v = map(int,input().split())
    a[x][y] +=1
    a[u+1][v+1] -=1
s = []
for i in range(m+1):
    s.append([0]*(n+1))

for i in range(1,m+1):
    for j in range(1,n+1):
        s[i][j] = s[i-1][j] + s[i][j-1] + a[i-1][j-1] - s[i-1][j-1]
print(s)
        
#s = [[0, 0, 0, 0, 0], 
#[0, 3, -3, 4, 12], 
#[0, -4, -1, 10, 14], 
#[0, -3, -1, 17, 22], 
#[0, 1, 7, 23, 25]]