بازه‌های زیبا


  • محدودیت زمان: ۱ ثانیه
  • محدودیت حافظه: ۲۵۶ مگابایت

آرایه‌ای متشکل از nn عدد داریم. یک بازه از این اعداد را زیبا می‌نامیم اگر و تنها اگر مجموع اعداد حاضر در این بازه کمتر یا مساوی عدد kk و بیشتر یا مساوی عدد k-k باشد. به عبارتی دیگر، قدر مطلق مجموع اعداد این بازه باید حداکثر kk باشد.

روی این آرایه qq بار عملیات انجام شده است، هر عملیات به این صورت است که دو عدد ii و xx مشخص شده‌اند (1in11 \le i \le n-1)، سپس عضو ii-ام آرایه با عدد xx جمع می‌شود و از عضو i+1i+1-ام آرایه عدد xx تفریق می‌شود. (توجه کنید که مقدار xx می‌تواند منفی هم باشد)

از شما خواسته شده یکبار در ابتدا و سپس بعد از اعمال هر عملیات، تعداد بازه‌های زیبای آرایه را محاسبه کنید.

دقت کنید تمامی عملیات‌ها پایا هستند، یعنی اثر آن‌ها در عملیات‌های بعدی نیز روی آرایه می‌ماند.

ورودی🔗

در خط اول ورودی به ترتیب سه عدد nn، kk و qq آمده‌اند. در خط دوم nn عدد آمده‌اند که اعداد اولیه‌ی آرایه هستند و عدد ii را با aia_i نمایش می‌دهیم. در qq خط بعدی، در هر خط به ترتیب دو عدد ii و xx آمده‌اند که عملیات را مشخص می‌کنند.

2n100000 2 \le n \le 100 \, 000 1q100000 1 \le q \le 100 \, 000 0k109 0 \le k \le 10 ^ 9 109ai,x109 -10 ^ 9 \le a_i, x \le 10 ^ 9 1in1 1 \le i \le n - 1

همچنین تضمین می‌شود قدر مطلق تمامی اعداد آرایه بعد از هر کوئری حداکثر 10910^9 خواهد ماند.

خروجی🔗

خروجی شما باید شامل q+1q+1 خط باشد که نشان دهد در ابتدا و بعد از انجام هر عملیات تعداد بازه‌های زیبای آرایه چقدر است.

مثال🔗

ورودی نمونه ۱🔗

5 3 2
1 2 3 4 5 
3 -2
2 4
Plain text

خروجی نمونه ۱🔗

4
5
4
Plain text

در این نمونه در ابتدا بازه‌های [1][1]، [2][2]، [3][3] و [1,2][1,2] زیبا هستند.

بعد از عملیات اول آرایه تبدیل می‌شود به: 1,2,1,6,51, 2, 1, 6, 5. بعد از این تغییر بازه‌های [1][1]، [2][2]، [3][3]، [1,2][1,2] و [2,3][2,3] زیبا خواهند بود.

بعد از عملیات دوم آرایه به این صورت خواهد بود: 1,6,3,6,51, 6, -3, 6, 5. بعد از این تغییر بازه‌های [1][1]، [3][3]، [2,3][2,3] و [3,4][3,4] زیبا هستند.

(منظور از بازه‌ی [i,j][i,j] بازه‌ای است که از عضو iiام شروع شده و تا عضو jjام ادامه دارد)

ورودی نمونه ۲🔗

5 5 5
-3 -4 0 5 -5 
2 1
2 3
4 -4
2 -1
3 5
Plain text

خروجی نمونه ۲🔗

12
12
13
12
12
13
Plain text

ورودی نمونه ۳🔗

7 5 10
-10 11 -15 -8 6 8 8 
2 -16
6 -7
2 13
2 -18
4 -6
3 -8
4 10
5 7
2 -2
6 17
Plain text

خروجی نمونه ۳🔗

6
7
10
8
9
8
6
10
8
7
7
Plain text