LBC_2C - Trò chơi vòng kẹo

https://luyencode.net/problem/lbc_2

Để làm được bài này, bạn cần biết kĩ thuật mảng hiệu:

VNOI_prefix_sum

Gọi

$d[i]$ là hiệu của

$a[i]-a[i-1]$.

Vậy

$a[i]=d[1]+d[2]+...+d[i]$

Với mỗi truy vấn, có

$2$ trường hợp:

• $l\le r$: Thao tác của mảng hiệu bình thường,
  $d[l]+=1$,
  $d[r+1]-=1$.
• $r<l$: Do đoạn cần cập nhật có thể xoay vòng, nên thao tác này có thể tách thành
  $2$ thao tác là tăng đoạn
  $l$ đến
  $n$, và đoạn từ
  $1$ đến
  $r$

Sau khi có được mảng

$d$, ta chỉ cần cộng dồn lại để được mảng

$a$ và lấy số max và in ra.