Коти махають своїми хвостами, коли стоять перед вибором, при цьому одне бажання блокує інше. Наприклад, якщо кіт стоїть в дверному отворі, і хоче вийти, а на вулиці йде дощ, хвіст гойдатиметься із-за внутрішнього конфлікту. Кіт хоче вийти, але не хоче промокнути. Як тільки він прийме рішення (залишитися удома, або вийти під дощ), хвіст негайно припинить розгойдуватися.
Jakscho korotko, to kil'kist' usih zrostajuchyh poslidovnostej mozhna porahuvaty za O(1) - jih bezlich
A jakscho serjozno:
Jakscho hochesh, schob tobi tut dopomogly, to abo daj bil'sh konkretnu umovu, abo link na neji, abo link na konkretnu gilku forumu de obgovorjujut' zadachu.
Ja, napryklad, ne zrozumiv, chy treba rahuvaty vsi chy lyshe najdovshi pidposlidovnosti. Krim togo, jakscho treba schob rozvjazok pracjuvav ne dovshe 10s, to bazhano znaty hoch jakus' ocinku dlja N (kil'kosti elementiv poslidovnosti).
Nu po pershe, nemaje obmezhennja na chysla, ale jih kil'kist' ne bil'sha za 500K, tomu persh za vse masyv vsih chysel potribno peretvoryty v chysla vid 1 do N.
Nu a dali treba perebyraty chysla poslidovnosti po cherzi i rahuvaty, do skil'koh poslidovnostej jih mozhna dopysaty. Tobto, jakscho potochne chyslo X, to treba znaty skil'ky pidposlidovnostej z poperednih chysel zakinchujet'sja na chyslo Y < X. Tobto jakscho F(Y) - kil'kist' pidposlidovnostej, scho zakinchujut'sja na Y, to nam treba znaty sumu F(Y) dlja vsih Y < X - ce i bude kil'kist' novyh poslidovnostej, scho zakinchujut'sja na X (+ treba dodaty odnu poslidovnist', scho skladajet'sja lyshe z chysla X). Pidkazka: tut dopomozhe Range Sum Querry (RSQ).