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

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

228

Bold text

Italic text

inline text

code:
#include <stdio.h>

int main()
{
    printf("SlavicG");

    return 0;
}

Username: SlavicG

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

Italic comment text for upvotes

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)

or stop using shit language ;)

i used segment tree and i got a "beautiful" wrong answer which is really annoying