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).
Birthday(s):
