Призначення
У класі діти сідають на стільці, розташовані по колу. Вони чогось чекають. З їхніх сяючих очей ми відчуваємо, що вони чекають чогось хорошого. Можливо, це не буде папір. Їх охоче розчавлюють, і багато хто вже слинять. Вони чекають на якусь їжу? За безлад? Або вони чекають найбільшого скарбу з усіх ласощів, самого шоколаду?
Так, учитель незабаром прийде до кімнати і принесе їм шоколад. На жаль, шоколад - це лише один 1, тому дітям доведеться ділитися шоколадом. Деякі можуть навіть не досягти успіху.
Допоможіть вчителю з’ясувати, скільки дітей можна їсти з шоколаду.
Завдання
Шоколадний стіл складається з \ (r \) рядків та \ (s \) стовпчиків шоколадних кубиків. Вчитель починає з того, що передає шоколад дитині по колу. Дитина відламує або один ряд, або одну колонку шоколаду, а решту передає дитині, яка сидить праворуч.
Хлопчики ненажерливі, і коли вони отримують шоколад, вони обриваються якомога більше. Отже, коли шоколад має більше рядків, ніж стовпців, вони розбивають один стовпець, інакше - один рядок.
Дівчата не такі жадібні, і вони також хочуть дотримуватися стрункої лінії. Тому вони відламують найменший можливий шматок, також один рядок або один стовпець, але вибирають те, що має менше кубиків шоколаду.
Дізнайтеся, скільки у дітей закінчився шоколад, якщо вчитель вибере, з якої дитини почати. Дитину підраховують лише один раз, навіть якщо він пропустив шоколад більше одного разу.
Формат введення
Перший рядок містить кількість класів \ (t \), в яких ця проблема повинна бути вирішена. На кожному з наступних рядків \ (t \) є опис одного класу, що складається з чисел \ (r \), \ (s \) та рядка \ (Z \) .
Шоколад має розміри \ (r \ раз s \) кубиків. \ (Z \) - рядок, що складається з літер «C» і «D», що описує, які діти хлопчики, а які дівчатка.
Букви "С" позначають хлопчиків і "Д" дівчаток, при цьому дитина сидить найближче до дошки в першій позиції струни \ (Z \), а дитина сидить праворуч від дитини у другій позиції, потім дитина, що сидить праворуч від іншого, тощо. Перша дитина в ланцюжку також сидить праворуч від останньої дитини.
Обмеження щодо розмірів вводу такі:
Кількість рядків і кількість стовпців кожного шоколаду становить принаймні \ (1 \) і не більше \ (10 ^ 6 \). У кожному класі є принаймні \ (1 \) учнів і щонайбільше \ (10 ^ 6 \) учнів.
Кількість класів становить максимум \ (10 ^ 6 \), а крім того, у всіх класах разом не більше \ (10 ^ 7 \) учнів. Усі цукерки разом мають не більше \ (10 ^ 7 \) рядків і не більше \ (10 ^ 7 \) стовпців.
У таблиці ви можете побачити верхні межі кількості класів \ (t \) та кількості учнів в одному класі \ (z \) та кількості рядків \ (r \) та стовпців \ (r \) один шоколад у кожному наборі входів.
| Максимум \ (t \) | \ (50 \) | \ (1 \, 000 \) | \ (10 ^ 6 \) | \ (10 \) | \ (10 ^ 6 \) |
| Максимум \ (z, r, s \) | \ (50 \) | \ (1 \, 000 \) | \ (20 \) | \ (10 ^ 6 \) | \ (10 ^ 6 \) |
Вихідний формат
Напишіть \ (t \) рядки для виходу, для кожного класу напишіть, скільки дітей може їсти шоколад, якщо вони поділять його так, як описано в завданні.
Приклад
Вхідні дані:
Вихід:
У третьому класі дівчата повинні їсти першими, адже хлопець з’їдає весь шоколад, який до нього потрапляє. У четвертому класі шоколад настільки великий, що його може з’їсти кожен. У п’ятому класі діти їстимуть у такому порядку: CCDDCDC. Таким чином, розміри шоколаду становитимуть (4.4), (4.3), (4.2), (3.2), (2.2), (2.1), (1.1), (0), 0) і всі їдять.
Тому що в школі мало грошей. ”
Ключова частина рішення полягає в тому, щоб мати можливість швидко відповісти на таке запитання: "якби ми почали роздавати шоколад від \ (i \) -тої дитини до \ (j \) -тої дитини, чи вистачило б шоколаду для нас?"
А саме, якби ми це знали, ми могли б вирішити проблему, використовуючи так звану техніку двох бігунів. Беремо двох бігунів і сідаємо обох на початку кола. Бігунів називатимуть Іваном та Джожо та будуть знаходитись на позиціях \ (i \) та \ (j \). Всякий раз, коли ми можемо годувати дітей з положення \ (i \) в положення \ (j \), Джожо переходить на наступний квадрат у колі. Інакше Іван рухається. Зверніть увагу, що Іван ніколи не обганяє Йожу, бо ми можемо нагодувати нуль дітей. Алгоритм закінчується, коли Джожо двічі обійде все коло, і вирішенням проблеми буде максимально можлива відстань бігунів під час пробігу алгоритму. Подумайте, чому це так.
Виняток полягає в тому, що якщо відповідь більша за кількість дітей, ми перелічимо лише кількість дітей.
Обидва бігуни виконують не більше \ (2 \ ell \) кроків, де \ (\ ell \) - розмір кола (довжина рядка \ (Z \)), що робить алгоритм значно швидшим, ніж якби ми перевірили всі \ (O (\ ell ^ 2) \) пари \ ((i, j) \) .
То як ви знаєте, чи можна частину дітей годувати?
Спочатку ми перевертаємо шоколад так, щоб він був принаймні настільки ж широким. Тоді ми можемо зберегти цю властивість протягом усього споживання - хлопчик завжди їсть колонку і звужує шоколад. Якщо дівчина отримує шоколад, який вищий за ширший, вона їсть лінію. Однак, якщо дівчина їсть шоколад висотою настільки ж широкий, вона їсть плитку.
Давайте розглянемо розділ дітей від \ (i \) до \ (j \). Уявіть, що дитина \ (i \) -te першою поїла шоколад. Нехай \ (c \) - кількість хлопчиків у цьому розділі, \ (d \) - кількість дівчат та \ (e \) - кількість дівчат, які з'їли плитку шоколаду. Тоді шоколад розмірів \ (r \ times s \), де \ ((r \ leq s) \) достатньо для дітей від \ (i \) до \ (j \), якщо \ (e + c \ leq s \) і одночасно \ (de \ leq r \). В іншому випадку це те саме, що перевірити \ (e + c \ leq s \) та \ (c + d \ leq r + s \) .
Знайти \ (c \) та \ (d \) для деякої ділянки кола легко. Єдиною складною частиною цього завдання було ефективне з'ясування \ (e \) .
Зверніть увагу, що коли дівчина ходить за хлопчиком шоколадом, це, безумовно, не враховує \ (e \). Подібним чином, якщо ми маємо \ (8 \) дівчаток після \ (8 \) хлопчиків. Інтуїтивно зрозуміло, що для того, щоб бути великим \ (е \), нам потрібно багато дівчат, які їдять шоколад, а багато хлопців не їдять шоколаду перед собою. Точніше, візьмемо послідовності дітей із позиції \ (i \), у всі можливі позиції \ (k \), \ (k \ leq j \), у кожній послідовності ми підраховуємо дівчаток та хлопчиків, і нехай \ (f \) - найбільша з різниць кількості дівчат мінус кількість хлопців. Тоді \ (e = max (0, (s-r + f + 1) // 2) \). (Подумайте, чому.)
Отже, нам просто потрібно з’ясувати, як обчислити \ (f \). Це можна зробити, витративши разом час \ (O (\ ell) \) для обчислення всього \ (f \), але досить більш простого рішення із використанням дерева інтервалів у часі \ (O (\ ell \ log \ ell) \ \), використовуючи мультимножину однакової складності.
Спочатку ми зберігаємо різницю в кількості дівчат та хлопців від початку кола до заданої позиції в окремому полі для кожної позиції. Щоб знайти \ (f \), нам потрібно знати максимум інтервалу від \ (i \) до \ (j \) у цьому полі та відняти значення в позиції \ (i-1 \) .
Обговорення
Тут ви можете вільно обговорювати рішення, ділитися своїми фрагментами коду тощо.
Ви повинні увійти, щоб додати коментарі.