+ محدودیت زمان: ۳ ثانیه + محدودیت حافظه: ۲۵۶ مگابایت + آزمون عملی سوم فاینال سی و دومین دوره المپیاد کامپیوتر ایران ---------- روزی از روزهای تابستان، استاد و شاگردانش به دل طبیعت رفته‌اند. برکه‌ای در نزدیکی آن‌ها وجود دارد که روی آن $n$ برگ در یک ردیف قرار گرفته‌اند، به طوری که دو سمت ردیف خشکی قرار دارد. استاد متوجه شد روی برخی از برگ‌ها یک قورباغه نشسته است. باران شدیدی می‌بارد. قورباغه‌ها که از جمع شدن آب زیاد در برکه می‌ترسند، می‌خواهند به سمت خشکی بروند. استاد به کمک قورباغه‌ها می‌رود تا هر چه سریع‌تر همه‌ی قورباغه‌ها را به سمت خشکی هدایت کند. او در هر ثانیه می‌تواند به یک قورباغه دستور پرش در جهت دلخواهش بدهد. سپس قورباغه انتخاب شده در جهت مد نظر استاد می‌پرد و روی اولین برگی (یا خشکی) که قورباغه‌ای روی آن نیست، فرود می‌آید. وقتی همه‌ی قورباغه‌ها به خشکی برسند، استاد خوشحال می‌شود ولی استاد باید حواسش به شاگردانش نیز باشد، پس هر چه سریع‌تر باید قورباغه‌ها را به خشکی برساند. استاد بسیار باهوش است و قورباغه‌ها را در سریع‌ترین زمان ممکن به خشکی می‌رساند. بعد از بازگشت به مدرسه، استاد از همین اتفاق از بچه‌ها امتحان می‌گیرد. او دنباله‌ای $n$ از قورباغه‌ها را روی تخته می‌کشد‌د. سپس در $q$ گام، هر بار یکی از دو کار زیر را انجام می‌دهد: + $change \,\, idx$: وضعیت قورباغه روی برگ $idx$ تغییر می‌کند، اگر روی آن قورباغه‌ای بوده به برکه می‌رود و اگر نبوده قورباغه‌ای از برکه روی آن می‌پرد. + $get \,\, l \,\, r$: از یک دانش‌آموز سوال می‌پرسد که اگر فقط قورباغه‌های بازه $[l, r]$ را در نظر بگیریم و دو سمت این بازه را خشکی فرض کنیم، چند ثانیه زمان می‌برد تا استاد همه قورباغه‌ها را به خشکی برساند. دانش‌آموزان در این اردو بسیار خسته شده‌اند و توانایی جواب دادن به استاد را ندارند. با مهارت‌های خود به دانش‌آموزان کمک کنید تا پاسخ سوالات استاد را پیدا کنند. # ورودی در خط اول ورودی دو عدد طبیعی $n$ تعداد کل قورباغه‌ها و $q$ تعداد پرسش‌های استاد به‌ترتیب می‌آیند. $$1 \le n, q \le 100,000$$ در خط دوم ورودی $a_1, a_2, \cdots a_n$ به‌ترتیب می‌آیند. $a_i$ برابر صفر است اگر روی $i$ -امین برگ از سمت چپ قورباغه‌ای وجود نداشته باشد و در غیر این صورت برابر یک می‌باشد. $$0 \le a_i \le 1$$ در هر یک از $q$ خط بعدی، یکی از دو شکل پرسشی که در صورت سوال گفته شد، می‌آید. $$1 \le l, r, idx \le n$$ # خروجی به ازای هر بار پرسش نوع دوم استاد، در یک خط کمترین زمان ممکن برای به خشکی رساندن قورباغه‌ها را چاپ کنید. # زیرمسئله‌ها | زیرمسئله | نمره | محدودیت | |:------------------:|:----------:|:------------------:| | ۱ | ۱۴ | $n \le 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 ```

+ محدودیت زمان: ۲ ثانیه + محدودیت حافظه: ۲۵۶ مگابایت + آزمون عملی سوم فاینال سی و دومین دوره المپیاد کامپیوتر ایران ---------- جک بعد از اینکه به دوستان المپیاد کامپیوتری خود خیانت کرد و به سمت المپیاد ریاضی رفت، در کلاس های المپیاد ریاضی ثبت نام کرد. در هفته اول ۳ کلاس جبر، ترکیبیات و نظریه اعداد داشت. در کلاس جبر با تابع و در کلاس نظریه اعداد با ب.م.م (بزرگترین مقسوم علیه مشترک) و در کلاس ترکیبیات با مفاهیم جایگشت آشنا شد. حال او آموخته های خود را ترکیب کرده و تابع $f(x)$ را به شکل زیر ساخته است: $f(x)$ برابر بزرگترین مقسوم علیه مشترک تمامی عددهایی است که ممکن است از جایگشت دادن ارقام عدد $x$ به دست بیاید؛ برای مثال برای عدد ۱۲۰، جایگشت‌های ممکن برابر $\langle 12, 21, 102, 120, 201, 210 \rangle$ است که ب.م.م آنها برابر ۳ است. حال سوالی که برای جک پیش آمده این است که اگر به ازای همه‌ی اعداد ۱ تا $n$ مقدار $f(x)$ را حساب و جمع کنیم به چه عددی می‌رسیم؟ او این سوال را پیش دوستان المپیاد ریاضی خود مطرح کرد ولی دوستان او در حل این مسئله ناتوان بودند. او دست از پا درازتر پیش دوستان المپیاد کامپیوتری خود آمد و سوالش را به آن‌ها گفت تا برایش حل کنند. دوستان او از اینکه جک به آنها خیانت کرده بود، ناراحت بودند و به دنبال انتقام بودند؛ از این رو سوال او را دزدیدند و برای فاینال‌های عملی پیشنهاد دادند. از آنجا که سوال جک مورد قبول واقع شد، شما باید این سوال را حل کنید! # ورودی در تنها خط ورودی عدد $n$ داده می‌شود. $$1 \leq n < 10^{5,001}$$ # خروجی در تنها خط خروجی جواب سوال جک یا همان $\displaystyle \sum_{i=1}^{n} f(i)$ را چاپ کنید. # زیرمسئله‌ها | زیرمسئله | نمره | محدودیت | |:------------------:|:----------:|:------------------:| | ۱ | ۸ | $n \leq 10^6$ | | ۲ | ۳۵ | $n \leq 10^{18}$ | | ۳ | ۲۹ | $n < 10^{501}$ | | ۴ | ۲۸ | بدون محدودیت اضافی | # مثال *در اینجا چند نمونه برای فهم بهتر صورت سوال و قالب ورودی و خروجی تست‌ها داده می‌شود.* ## ورودی نمونه ۱ ``` 20 ``` ## خروجی نمونه ۱ ``` 79 ``` در مثال اول مقدار تابع به ازای اعداد یک‌رقمی و یازده برابر با خودشان، برای ۱۲ و ۱۵ برابر ۳، برای ۲۰ برابر ۲ و برای بقیه اعداد برابر ۱ است. پس حاصل به صورت کلی برابر ۷۹ خواهد بود. ## ورودی نمونه ۲ ``` 123456 ``` ## خروجی نمونه ۲ ``` 966228 ```

+ محدودیت زمان: ۱ ثانیه + محدودیت حافظه: ۲۵۶ مگابایت + آزمون عملی سوم فاینال سی و دومین دوره المپیاد کامپیوتر ایران ---------- # **سیستم داوری این سوال در کوئرا مشکل داره!** در یک کارخانه جعبه‌سازی تعدادی جعبه روی هم قرار داده شده‌اند. جعبه‌ها در تعدادی ستون روی یکدیگر هستند. $a_i$ جعبه در ستون $i$ ام روی هم قرار گرفته‌اند. رئیس کارخانه به تازگی یک ماشین چرخش تهیه کرده که می‌تواند عملیات زیر را انجام دهد: + بازه دلخواه $[l, r)$ را انتخاب می‌کند، یک مستطیل که طول $[l, r)$ و ارتفاع $[0, \max(a_l, a_{l+1}, \cdots, a_{r-1}))$ می‌کشد و مستطیل را ۹۰ درجه پادساعتگرد می‌چرخاند، سپس فضای خالی زیر جعبه‌ها توسط جاذبه پر می‌شود. |  | |:--------:| | چرخش بازه $[1, 4)$ . ستون‌ها از $0$ شماره‌گذاری می‌شوند. | رئیس کارخانه به دنبال این است که تمامی ستون‌ها حداکثر شامل یک جعبه باشند. او می‌خواهد مهندسی استخدام کند تا با استفاده از ماشین چرخش او را به هدفش برساند. ماشین چرخش پر هزینه است و رئیس شرکت می‌خواهد با تعداد کمی عملیات او را به خواسته‌اش برسانید. در قسمت زیرمسئله‌ها در مورد نحوه نمره‌دهی بخوانید. رئیس کارخانه ستون‌ها را به صورت یک رشته دودویی دراورده است به طوری که هر ستون تعدادی $0$ متوالی در رشته است که با $1$ از یکدیگر جدا می‌شوند و خود ۱ نیز در آن حساب می‌شود. به طور مثال در شکل ۱ که دنباله ستون‌ها $\langle 3, 4, 2, 5, 6, 5 \rangle$ می‌باشد، رشته آن برابر $0010001010000100000100001$ می‌باشد. تضمین می‌شود که آخرین حرف این رشته حتما $1$ است. # ورودی در خط اول ورودی سه عدد طبیعی $n$ طول رشته، $m$ تعداد تعداد ستون‌ها و $k$ شماره زیرمسئله به‌ترتیب می‌آیند. $$1 \leq n, m \leq 4 \, 000 \, 000$$ $$1 \leq k \leq 4$$ # خروجی ابتدا تعداد عملیات‌هایی که انجام می‌دهید را چاپ کنید. سپس به‌ترتیب در هر خط بازه‌ای که آن را می‌چرخانید را به صورت $l$ و $r$ چاپ کنید که یعنی بازه $[l, r)$ با شماره‌گذاری‌های جدید را می‌چرخانید. # زیرمسئله‌ها ### توجه کنید که به دلیل محدودیت‌های فعلی امکان نمره دهی جزئی وجود ندارد و مانند سوال های دیگر برای گرفتن نمره‌ی یک زیرمسئله باید آن را کامل حل کرده باشید و حتی اگر طبق امتیاز دهی گفته شده باید قسمتی از نمره یک زیرمسئله را می‌گرفتید برای شما ۰ حساب می‌شود. | زیرمسئله | نمره | محدودیت | |:------------------:|:----------:|:------------------:| | ۱ | ۵ | $n \leq 10^3$، حداکثر $500$ عملیات می‌توانید انجام دهید. | | ۲ | ۲۵ | $n \leq 10^5$، حداکثر $650$ عملیات می‌توانید داشته باشید و اکر $x$ عملیات داشته باشید، نمره شما از این زیرمسئله $min(25, 20 + 5 \times \frac{650 - x}{330})$ خواهد بود. | | ۳ | ۲۵ | $n \leq 5 \times 10^5$، حداکثر $85$ عملیات می‌توانید انجام دهید. | | ۴ | ۴۵ | $n \leq 4 \times 10^6$ و حداکثر $140$ عملیات می‌توانید انجام دهید. اگر تعداد عملیات‌های شما $x$ و $100 \leq x \leq 140$ باشد، در صورت $x = 140$ $10$ نمره می‌گیرید و $x=100$ $20$ نمره و هر مقدار بین این دو به صورت خطی نمره افزایش می‌یابد. اگر $70 < x \leq 100$ $20$ نمره می‌گیرید. در صورت $30 \leq x \leq 70$ نیز به صورت خطی بین $30$ تا $45$ نمره دریافت می‌کنید. در صورت $x \leq 30$ نیز کل نمره را دریافت خواهید کرد. | # مثال ## ورودی نمونه ۱ ``` 15 6 1 100011001001001 ``` ## خروجی نمونه ۱ ``` 6 0 6 1 4 0 7 2 3 1 2 0 1 ```