برکه (Lake)
روزی از روزهای تابستان، استاد و شاگردانش به دل طبیعت رفتهاند. برکهای در نزدیکی آنها وجود دارد که روی آن $n$ برگ در یک ردیف قرار گرفتهاند، به طوری که دو سمت ردیف خشکی قرار دارد. استاد متوجه شد روی برخی از برگها یک قورباغه نشسته است.
باران شدیدی میبارد. قورباغهها که از جمع شدن آب زیاد در برکه میترسند، میخواهند به سمت خشکی بروند. استاد به کمک قورباغهها میرود تا هر چه سریعتر همهی قورباغهها را به سمت خشکی هدایت کند. او در هر ثانیه میتواند به یک قورباغه دستور پرش در جهت دلخواهش بدهد. سپس قورباغه انتخاب شده در جهت مد نظر استاد میپرد و روی اولین برگی (یا خشکی) که قورباغهای روی آن نیست، فرود میآید.
وقتی همهی قورباغهها به خشکی برسند، استاد خوشحال میشود ولی استاد باید حواسش به شاگردانش نیز باشد، پس هر چه سریعتر باید قورباغهها را به خشکی برساند. استاد بسیار باهوش است و قورباغهها را در سریعترین زمان ممکن به خشکی میرساند.
بعد از بازگشت به مدرسه، استاد از همین اتفاق از بچهها امتحان میگیرد. او دنبالهای $n$ از قورباغهها را روی تخته میکشدد. سپس در $q$ گام، هر بار یکی از دو کار زیر را انجام میدهد:
- $change \,\, idx$: وضعیت قورباغه روی برگ $idx$ تغییر میکند، اگر روی آن قورباغهای بوده به برکه میرود و اگر نبوده قورباغهای از برکه روی آن میپرد.
- $get \,\, l \,\, r$: از یک دانشآموز سوال میپرسد که اگر فقط قورباغههای بازه $[l, r]$ را در نظر بگیریم و دو سمت این بازه را خشکی فرض کنیم، چند ثانیه زمان میبرد تا استاد همه قورباغهها را به خشکی برساند.
دانشآموزان در این اردو بسیار خسته شدهاند و توانایی جواب دادن به استاد را ندارند. با مهارتهای خود به دانشآموزان کمک کنید تا پاسخ سوالات استاد را پیدا کنند.
ورودی
در خط اول ورودی دو عدد طبیعی $n$ تعداد کل قورباغهها و $q$ تعداد پرسشهای استاد بهترتیب میآیند.
در خط دوم ورودی $a_1, a_2, \cdots a_n$ بهترتیب میآیند. $a_i$ برابر صفر است اگر روی $i$ -امین برگ از سمت چپ قورباغهای وجود نداشته باشد و در غیر این صورت برابر یک میباشد.
در هر یک از $q$ خط بعدی، یکی از دو شکل پرسشی که در صورت سوال گفته شد، میآید.
خروجی
به ازای هر بار پرسش نوع دوم استاد، در یک خط کمترین زمان ممکن برای به خشکی رساندن قورباغهها را چاپ کنید.
محدودیتها
- $1 \leq n \leq 100\,000$
- $1 \leq q \leq 100\,000$
- $0 \leq a_i \leq 1$
- $1 \leq l, r, idx \leq n$
زیرمسئلهها
- زیرمسئله اول (۱۴ نمره): $n \leq 3000$.
- زیرمسئله دوم (۵۳ نمره): در همه کوئریهای نوع دوم $l=1$ و $r=n$ میباشد.
- زیرمسئله سوم (۳۳ نمره): بدون محدودیت اضافی.
ورودی و خروجی نمونه
| ورودی نمونه | خروجی نمونه |
|---|---|
6 8 1 1 0 1 1 1 get 1 6 change 5 get 1 5 change 2 get 2 5 change 4 get 1 6 get 2 4 | 5 4 2 2 0 |