After getting $$$998244353$$$ upvotes...

How about we count the upvotes on the post and enlarge this comment also accordingly

228

Mihai Eminescu

Luceafărul

A fost odată ca-n povești, A fost ca niciodată. Din rude mari împărătești, O prea frumoasă fată.

Și era una la părinți Și mândră-n toate cele, Cum e Fecioara între sfinți Și luna între stele.

Din umbra falnicelor bolți Ea pasul și-l îndreaptă Lângă fereastră, unde-n colț Luceafărul așteaptă.

Privea în zare cum pe mări Răsare și străluce, Pe mișcătoarele cărări Corăbii negre duce.

Îl vede azi, îl vede mâini, Astfel dorința-i gata; El iar, privind de săptămâni, Îi cade draga fată.

Cum ea pe coate-și răzima Visând ale ei tâmple, De dorul lui și inima Și sufletu-i se împle.

Și cât de viu s-aprinde el În orișicare sară, Spre umbra negrului castel Când ea o să-i apară.

...

Și pas cu pas pe urma ei Alunecă-n odaie, Țesând cu recile-i scântei O mreajă de văpaie.

Și când în pat se-ntinde drept Copila să se culce, I-atinge mâinile pe piept, I-nchide geana dulce;

Și din oglindă luminiș Pe trupu-i se revarsă, Pe ochii mari, bătând închiși Pe fața ei întoarsă.

Ea îl privea cu un surâs, El tremura-n oglindă, Căci o urma adânc în vis De suflet să se prindă.

Iar ea vorbind cu el în somn, Oftând din greu suspină: - O, dulce-al nopții mele domn, De ce nu vii tu? Vină!

Cobori în jos, luceafăr blând, Alunecând pe-o rază, Pătrunde-n casă și în gând Și viața-mi luminează!

El asculta tremurător, Se aprindea mai tare Și s-arunca fulgerător, Se cufunda în mare;

Și apa unde-au fost căzut În cercuri se rotește, Și din adânc necunoscut Un mândru tânăr crește.

Ușor el trece ca pe prag Pe marginea ferestei Și ține-n mână un toiag Încununat cu trestii.

Părea un tânăr voievod Cu păr de aur moale, Un vânăt giulgi se-ncheie nod Pe umerele goale.

Iar umbra feței străvezii E albă ca de ceară - Un mort frumos cu ochii vii Ce scânteie-n afară.

• Din sfera mea venii cu greu Ca să-ți urmez chemarea, Iar cerul este tatăl meu Și mumă-mea e marea.

Ca în cămara ta să vin, Să te privesc de-aproape, Am coborât cu-al meu senin Și m-am născut din ape.

O, vin'! odorul meu nespus, Și lumea ta o lasă; Eu sunt luceafărul de sus, Iar tu să-mi fii mireasă.

Colo-n palate de mărgean Te-oi duce veacuri multe, Și toată lumea-n ocean De tine o s-asculte.

• O, ești frumos, cum numa-n vis Un înger se arată, Dară pe calea ce-ai deschis N-oi merge niciodată;

Străin la vorbă și la port, Lucești fără de viață, Căci eu sunt vie, tu ești mort, Și ochiul tău mă-ngheață.

...

Trecu o zi, trecură trei Și iarăși, noaptea, vine Luceafărul deasupra ei Cu razele-i senine.

Ea trebui de el în somn Aminte să-și aducă Și dor de-al valurilor domn De inim-o apucă:

• Cobori în jos, luceafăr blând, Alunecând pe-o rază, Pătrunde-n casă și în gând Și viața-mi luminează!

Cum el din cer o auzi, Se stinse cu durere, Iar ceru-ncepe a roti În locul unde piere;

În aer rumene văpăi Se-ntind pe lumea-ntreagă, Și din a chaosului văi Un mândru chip se-ncheagă;

Pe negre vițele-i de păr Coroana-i arde pare, Venea plutind în adevăr Scăldat în foc de soare.

Din negru giulgi se desfășor Marmoreele brațe, El vine trist și gânditor Și palid e la față;

Dar ochii mari și minunați Lucesc adânc himeric, Ca două patimi fără saț Și pline de-ntuneric.

• Din sfera mea venii cu greu Ca să te-ascult ș-acuma, Și soarele e tatăl meu, Iar noaptea-mi este muma;

O, vin', odorul meu nespus, Și lumea ta o lasă; Eu sunt luceafărul de sus, Iar tu să-mi fii mireasă.

O, vin', în părul tău bălai S-anin cununi de stele, Pe-a mele ceruri să răsai Mai mândră decât ele.

• O, ești frumos cum numa-n vis Un demon se arată, Dară pe calea ce-ai deschis N-oi merge niciodată!

Mă dor de crudul tău amor A pieptului meu coarde, Și ochii mari și grei mă dor, Privirea ta mă arde.

• Dar cum ai vrea să mă cobor? Au nu-nțelegi tu oare, Cum că eu sunt nemuritor, Și tu ești muritoare?

• Nu caut vorbe pe ales, Nici știu cum aș începe - Deși vorbești pe înțeles, Eu nu te pot pricepe;

Dar dacă vrei cu crezământ Să te-ndrăgesc pe tine, Tu te coboară pe pământ, Fii muritor ca mine.

• Tu-mi cei chiar nemurirea mea În schimb pe-o sărutare, Dar voi să știi asemenea Cât te iubesc de tare;

Da, mă voi naște din păcat, Primind o altă lege; Cu vecinicia sunt legat, Ci voi să mă dezlege.

Și se tot duce... S-a tot dus. De dragu-unei copile, S-a rupt din locul lui de sus, Pierind mai multe zile.

...

În vremea asta Cătălin, Viclean copil de casă, Ce umple cupele cu vin Mesenilor la masă,

Un paj ce poartă pas cu pas A-mpărătesii rochii, Băiat din flori și de pripas, Dar îndrăzneț cu ochii,

Cu obrăjei ca doi bujori De rumeni, bată-i vina, Se furișează pânditor Privind la Cătălina.

Dar ce frumoasă se făcu Și mândră, arz-o focul; Ei, Cătălin, acu-i acu Ca să-ți încerci norocul.

Și-n treacăt o cuprinse lin Într-un ungher degrabă. - Da' ce vrei, mări Cătălin? Ia du-t' de-ți vezi de treabă.

• Ce voi? Aș vrea să nu mai stai Pe gânduri totdeauna, Să râzi mai bine și să-mi dai O gură, numai una.

• Dar nici nu știu măcar ce-mi ceri, Dă-mi pace, fugi departe - O, de luceafărul din cer M-a prins un dor de moarte.

• Dacă nu știi, ți-aș arăta Din bob în bob amorul, Ci numai nu te mânia, Ci stai cu binișorul.

Cum vânătoru-ntinde-n crâng La păsărele lațul, Când ți-oi întinde brațul stâng Să mă cuprinzi cu brațul;

Și ochii tăi nemișcători Sub ochii mei rămâie... De te înalț de subsuori Te-nalță din călcâie;

Când fața mea se pleacă-n jos, În sus rămâi cu fața, Să ne privim nesățios Și dulce toată viața;

Și ca să-ți fie pe deplin Iubirea cunoscută, Când sărutându-te mă-nclin, Tu iarăși mă sărută.

Ea-l asculta pe copilaș Uimită și distrasă, Și rușinos și drăgălaș, Mai nu vrea, mai se lasă,

Și-i zice-ncet: — Încă de mic Te cunoșteam pe tine, Și guraliv și de nimic, Te-ai potrivi cu mine...

Dar un luceafăr, răsărit Din liniștea uitării, Dă orizon nemărginit Singurătății mării;

Și tainic genele le plec, Căci mi le umple plânsul Când ale apei valuri trec Călătorind spre dânsul;

Lucește c-un amor nespus, Durerea să-mi alunge, Dar se înalță tot mai sus, Ca să nu-l pot ajunge.

Pătrunde trist cu raze reci Din lumea ce-l desparte... În veci îl voi iubi și-n veci Va rămânea departe...

De-aceea zilele îmi sunt Pustii ca niște stepe, Dar nopțile-s de-un farmec sfânt Ce nu-l mai pot pricepe.

• Tu ești copilă, asta e... Hai ș-om fugi în lume, Doar ni s-or pierde urmele Și nu ne-or ști de nume,

Căci amândoi vom fi cuminți, Vom fi voioși și teferi, Vei pierde dorul de părinți Și visul de luceferi.

...

Porni luceafărul. Creșteau În cer a lui aripe, Și căi de mii de ani treceau În tot atâtea clipe.

Un cer de stele dedesubt, Deasupra-i cer de stele - Părea un fulger ne'ntrerupt Rătăcitor prin ele.

Și din a chaosului văi, Jur împrejur de sine, Vedea, ca-n ziua cea dentâi, Cum izvorau lumine;

Cum izvorând îl înconjor Ca niște mări, de-a-notul... El zboară, gând purtat de dor, Pân' piere totul, totul;

Căci unde-ajunge nu-i hotar, Nici ochi spre a cunoaște, Și vremea-ncearcă în zadar Din goluri a se naște.

Nu e nimic și totuși e O sete care-l soarbe, E un adânc asemene Uitării celei oarbe.

• De greul negrei vecinicii, Părinte, mă dezleagă Și lăudat pe veci să fii Pe-a lumii scară-ntreagă;

O, cere-mi, Doamne, orice preț Dar dă-mi o altă soarte, Căci tu izvor ești de vieți Și dătător de moarte;

Reia-mi al nemuririi nimb Și focul din privire, Și pentru toate dă-mi în schimb O oră de iubire...

Din chaos, Doamne,-am apărut Și m-aș întoarce-n chaos... Și din repaos m-am născut, Mi-e sete de repaos.

• Hyperion, ce din genuni Răsai c-o-ntreagă lume, Nu cere semne și minuni Care n-au chip și nume;

Tu vrei un om să te socoți Cu ei să te asameni? Dar piară oamenii cu toți, S-ar naște iarăși oameni.

Ei numai doar durează-n vânt Deșerte idealuri - Când valuri află un mormânt, Răsar în urmă valuri;

Ei doar au stele cu noroc Și prigoniri de soarte, Noi nu avem nici timp, nici loc Și nu cunoaștem moarte.

Din sânul vecinicului ieri Trăiește azi ce moare, Un soare de s-ar stinge-n cer S-aprinde iarăși soare;

Părând pe veci a răsări, Din urmă moartea-l paște, Căci toți se nasc spre a muri Și mor spre a se naște.

Iar tu, Hyperion, rămâi Oriunde ai apune... Cere-mi cuvântul meu dentâi - Să-ți dau înțelepciune?

Vrei să dau glas acelei guri, Ca dup-a ei cântare Să se ia munții cu păduri Și insulele-n mare?

Vrei poate-n faptă să arăți Dreptate și tărie? Ți-aș da pământul în bucăți Să-l faci împărăție.

Îți dau catarg lângă catarg, Oștiri spre a străbate Pământu-n lung și marea-n larg, Dar moartea nu se poate...

Și pentru cine vrei să mori? Întoarce-te, te-ndreaptă Spre-acel pământ rătăcitor Și vezi ce te așteaptă.

...

În locul lui menit din cer Hyperion se-ntoarse Și, ca și-n ziua cea de ieri, Lumina și-o revarsă.

Căci este sara-n asfințit Și noaptea o să-nceapă; Răsare luna liniștit Și tremurând din apă

Și umple cu-ale ei scântei Cărările din crânguri. Sub șirul lung de mândri tei Ședeau doi tineri singuri:

• O, lasă-mi capul meu pe sân, Iubito, să se culce Sub raza ochiului senin Și negrăit de dulce;

Cu farmecul luminii reci Gândirile străbate-mi, Revarsă liniște de veci Pe noaptea mea de patimi.

Și de asupra mea rămâi Durerea mea de-o curmă, Căci ești iubirea mea dentâi Și visul meu din urmă.

Hyperion vedea de sus Uimirea-n a lor față: Abia un braț pe gât i-a pus Și ea l-a prins în brațe...

Miroase florile-argintii Și cad, o dulce ploaie, Pe creștetele-a doi copii Cu plete lungi, bălaie.

Ea, îmbătată de amor, Ridică ochii. Vede Luceafărul. Și-ncetișor Dorințele-i încrede:

• Cobori în jos, luceafăr blând, Alunecând pe-o rază, Pătrunde-n codru și în gând, Norocu-mi luminează!

El tremură ca alte dăți În codri și pe dealuri, Călăuzind singurătăți De mișcătoare valuri;

Dar nu mai cade ca-n trecut În mări din tot înaltul: - Ce-ți pasă ție, chip de lut, Dac-oi fi eu sau altul?

Trăind în cercul vostru strâmt Norocul vă petrece, Ci eu în lumea mea mă simt Nemuritor și rece.

1883, aprilie

There is no limit if you use a bit of CSS :D

Italic comment text for upvotes

Если ШЦПМ это московская школа, то может даже 4.

Я бы сказал, 5 раундов подряд будет)

SIS is such a great camp, that it is always the time for SIS.

!!!!!You Will!!!!!

1587 is exactly my highest rating, and the rest is history :rofl. Wish you luck ;)

Me too!

Expert!!!

wish u luck too

Same here

ABC only required

can

there is no exact answer, everything can change

your wish was fulfilled by the author

Too dangerous !!

not much, but i struggled for an hour on what i think was some overflow (WA on pretest 2). At the end i just put ll everywhere and it passed the pretests

same

NOTE: m2 is alive

Me too. Unfortunately, I resent two times the same code while refreshing the web, maybe can admins remove my last RE submission 169136909? It's exactly the same as the RE submission 169136355.

same

And why is it always C :(

Not sure it's that big gap I solved C it doesn't need any data structures but it wasn't easy for sure

The C of this round is nowhere as hard as the C of edu round 133

A had multiple TCs*

I become Master again! thx D! I solved it quickly on 00:11

Don't underestimate your opponent, ejjii!

you already spoke*

Let's say, you know the result for the initial array. Try to find how changing one value will affect the result.

Though it took me a lot of time to solve this, general idea for any such problem is, we want to know, if there is something with a[i-1],a[i] and a[i],a[i+1], when we do an update on index i.

You can check that our summation for a given array of size n = (n*(n+1))/2 + sum of (n-1-x)*(x+1), where 0<=x<n-1 and a[x]!=a[x+1].

Now, it is easy to refer to 169149222

Individual contribution of each index to the whole. So, if all numbers are distinct, then each index contributes (i + 1) * (n — i) to the total sum.

When you modify a number, check if it is equal to the left or right index. If it is, then subtract its individual contribution from the sum. If it was equal but now different, then add its individual contribution to the sum.

The exact individual contribution formula is weird and just takes a lot of time to find. (Ex. it's different if it's the same as the left neighbour vs the right neighbour, different for the first element, middle elements, and the last elements etc.)

I tried writing an explanation but I found I was unable to explain it clearly. Nonetheless I have left the explanation in case it helps.

First, how to calculate answer overall? Calculating prefix of blocks is simple, and all subarray s contianing the first element must sum all these. Then just iterate from left to right and if you find a new block, subtract (length remaining — 1), otherwise subtract -1. Answer is sum of all this.

To be clear: suppose you have 1 2 2 3 2 4 block_prefix = 1 2 2 3 4 5 answer for v[0] = 5 + 4 + 3 + 2 + 2 + 1 = 17 answer for v[1] = 17 — 5 (remaining numbers) — 1 = 11 answer for v[2] = 10 (since it's the same block, we only remove 1 from the answer) // and so on

final answer is sum of all these.

So now we know how to find the initial answer in O(n). How would it help us find the answer?

After a query: we have 4 cases

either this element begins a block on the left or begins a block on the right or breaks a block on the left or breaks a block on the right

If it begins a block on the left, we subtract 1 from all the elements to our left. If it begins a block on the right, we subtract a 1 from all the elements to our left including us. We just reverse this if it breaks a block.

for(int d=0;d<m;d++) {
            int i,x;
            cin>>i>>x;
            --i;
            int l = n &mdash; i;
            if(v[i] != x) {
                // Case 1: We are breaking a block on the left hand side
                if(i != 0 && v[i] == v[i-1]) {
                    s += (l*i);
                }
                // Case 2: We are breaking a block also on the right hand side
                if(i != n-1 && v[i+1] == v[i]) {
                    s += (l-1)*(i+1);
                }
                // Case 3: We are creating a block on the left hand side
                if(i != 0 && x == v[i-1]) {
                    s -= (l*i);
                }
                // Case 4: We are creating a block also on the right hand side
                if(i != n-1 && v[i+1] == x) {
                    s -= (l-1)*(i+1);
                }
            }
            v[i] = x;
            cout<<s<<'\n';
        }
    }

You just need to understand how often subarray of length 2 appear in array.

For exmp:

1 2 3 4 5

Currently ans = 35. Lets say we want to change 3rd (pos = 3) element (1-indexed) to 2, so it became this:

1 2 2 4 5

Now we consider 2 things:

was a[pos] equal a[pos + 1] before and if it is equal now. If it was equal and now it isn't, we just need to decrease ans by how many times does this subarray appears. In this exmp it appears 6 times: {2, 2}, {2, 2, 4}, {2, 2, 4, 5}, {1, 2, 2}, {1, 2, 2, 4}, {1, 2, 2, 4, 5}. So, now ans = ans — 6, so it is equal to 29. Else we increase ans by this number.

was a[pos — 1] equal to a[pos] before and if it is equal now. (Do the same as this 1st case).

Try to think of a way to calculate the contribution of each index in O(1) time. Any number affects only the numbers just after and before it. Then the problem is simple. Whenever any number is changed, subtract the contributions of the 3 numbers(before, after and itself). Then add the new contributions after a number is changed.

As far as calculating contribution, think of it this way — All numbers in a block except one are useless.

First calculate maximum answer (i.e when all elements are distinct)

Let B[i] = arr[i] == arr[i+1] with length n-1. Then subtract from maximum answer the sum of all subarrays of B (which can be done in O(n)). Answering queries can be done by extending the idea of sum of all subarrays: update can only change 2 values of B and it's easy to recalculate new sum of B.

Assuming we have an array $$$pref$$$ where $$$pref[i]$$$ is the number of elements with indices $$$k\leq i$$$ where $$$arr[k]\neq arr[k-1]$$$. For a given $$$[L, R]$$$ segment, its awesomeness $$$=pref[r]-pref[l]+1$$$. Hence, the answer is $$$\dfrac{N*(N+1)}{2}$$$ + $$$\sum_{i=1}^{n}{\sum_{j=i}^{n}{pref[j]-pref[i]}}$$$ $$$=$$$ $$$\dfrac{N*(N+1)}{2}$$$ $$$+$$$ $$$1*pref[1]+2*pref[2]+...+n*pref[n]$$$ $$$-n*pref[1]-(n-1)*pref[2]-...-1*pref[n]$$$.

So, whenever $$$arr[i]$$$ changes, it can can add $$$\pm 1$$$ to $$$pref[i]$$$, $$$pref[i+1]$$$, ..., $$$pref[n]$$$ (if the equality between $$$arr[i]$$$ and $$$arr[i-1]$$$ changes) and can add $$$\pm 1$$$ to $$$pref[i+1]$$$, $$$pref[i+2]$$$, ..., $$$pref[n]$$$ (if the equality between $$$arr[i+1]$$$ and $$$arr[i]$$$ changes.

The effect of adding or subtracting $$$1$$$ to all prefix values in some suffix corresponds to adding or subtracting arithmetic sums to the answer, e.g, if we add $$$1$$$ to all the prefix values in the suffix starting at $$$k$$$, this corresponds to setting $$$ans$$$ to $$$ans+\sum_{i=k}^{n}{i}-\sum_{i=1}^{n-k+1}{i}$$$.

Hence, we can process each query and modify our answer accordingly as needed then print the modified answer.

Submission

The initial answer is easy with DP. Then for every update at position i, you consider all segments including i, you check how their contribution change. To make life easier, you can classify segments into 3 types: 1. ends at i 2. starts from i 3. i is neither end nor start. That's the basic idea.

I can see you solved C, can you please explain your approach !

x will be compared with arr[i-1] and arr[i+1] and not arr[i].

	for (int i = 0; i < n; i++) {

You know, subs += (n - i) * i; overflows because i is int.

You can $$$and$$$ all the $$$x$$$ values of the triplets $$$l, r, x$$$ with $$$l = i$$$ or $$$r = i$$$ to find out which bits can/can't be placed at $$$a[i]$$$.

First consider the case of $$$i = j$$$ in a statement.

Then find all bit positions that MUST be 0. Then find all bit positions that MUST be 1. After this, you can greedily construct the lexicographically least array by deciding on the bits that are still unknown.

Denote $$$unset[i]$$$ as the mask representing bits that must be unset in $$$arr[i]$$$, this can be known from the unset bits in $$$x$$$ values which are the result of an $$$OR$$$ operation with $$$arr[i]$$$.

So we can calculate first the array $$$unset$$$ and then iterate on the queries. For the $$$qi^{th}$$$ query, for every bit set in $$$x$$$ and must be unset in one of $$$arr[i]$$$ and $$$arr[j]$$$, then we are sure we must set it in the other element. This has to be done before any further processing to ensure no extra unneeded bits are set somewhere.

What is remaining is those $$$x$$$ values where some set bits in them can be set in either $$$arr[i]$$$ or $$$arr[j]$$$. Assuming $$$j\geq i$$$, let's sort first the queries in ascending order of $$$j$$$, then process the queries in that order, and whenever we find a set bit in $$$x$$$ that is still unset in $$$i$$$ and $$$j$$$, set it in $$$j$$$.

The reason for that latest sorting done on queries is to handle the case when we have queries $$${i, j, x_1}$$$ and $$${j, k, x_2}$$$, where $$$i<j<k$$$ and the $$$k^{th}$$$ bit is set in $$$x_1$$$ and $$$x_2$$$. So, it is sufficient here to set the $$$k^{th}$$$ bit only in $$$j$$$.

Submission

If i-th bit of x is 0, then i-th bit of a[l] and a[r] must be 0. After that consider all queries where l = 1 (1-indexing). If i-th bit of x is 1 and i-th bit of a[r] must be 0, then we have to set 1 at i-th bit of a[1]. After considering all queries where l = 1 we can do it one more time, but now if i-th bit of x is 1 and i-th bit of a[1] is also 1, then we don't have to set 1 at i-th bit of a[r]. Now we do the same for all 2 <= l <= n

You don't need to — the length of the blocks is immaterial, the only thing you care about is if a block is created or not.

i don't know if there is an easier solution but either u use segment tree with lazy propagation or using BIT ( binary indexed tree)