Links:

• Contest
• Problem

Author and Tester: stash jhasuraj01
Editorialist: rajpate77725

Difficulty:

• Hard

Prerequisites:

• Flood Fill Algorithm
• Disjoint Set Union

Problem:

Na'vi are fond of arrows dipped in a neurotoxin that will stop your heart in one minute. But Kiri was not satisfied with the design of the arrows. She believed that they could be improved, and set out to prove it. She started experimenting with different combination of colors on a particular arrow. Unfortunately she doesn't have enough time to perform all such experiments manually and is looking for your help.

Formally, Given an array of integers, A of size N, where each element represents a color of a Na'vi arrow. You will be given Q modifications to the array, where in each modification you will be given two integers, i and newColor, and you need to apply a flood fill algorithm on the arrow starting at index i and replace the existing color with newColor. After Q such modifications, the final arrow will appear very different from the original. Your task is to output the signature of the final array, which is defined as the sum of all elements in the array, modulo (10⁹ + 7).

Note: Your solution should be optimized for time complexity and also it should be able to handle large inputs and large modulos efficiently.

Input Format:

• First line contains two integer N and Q
• Second line contains N space seperated integer, the elements of an array A.
• Next Q lines of input contains two integers, i and newColor

Constraints:

• 1 <= N, Q <= 2*10⁶
• 0 <= i < N
• 0 <= A[i] < N

Output Format:

A single integer, the signature of the final array

Explaination:

Intuition: The problem can be solved using Disjoint Set Union(DSU) data structure as the graph keeps on changing after each modification(dynamic graph).
A Disjoint Set is a data structure that keeps track of a partition of a set into disjoint subsets. Initially, each element in the array belongs to a single-element set. For each modification, we can find the representative element of the set that the current index belongs to and then merge the sets of the current color and the new color.

Explaination: The disjoint set data structure is used to keep track of the parent of each node and to perform unionByRank operation to merge two sets, find minimum index as well as maximum index.

• Initialize the disjoint set data structure with the size of the array and set each element as a separate set with rank 1.
  
• The disjoint set uses union-by-rank and path compression optimization to join elements of the same color into a single set.
  
• It loops through the array and joins elements with the same color into the same set.
  
• For each query, the algorithm updates the color of a particular element and checks the extreme neighbors of the element (left and right). If the neighbors have the same color, it joins the sets containing the neighbors and the updated element into a single set with keeping the track of maximum and minimum indices in set.
  
• The mini and maxi arrays are used to keep track of the minimum and maximum indices of the nodes in each connected component. These arrays are updated during the union operation by finding the minimum and maximum of indices of the two components being merged.
  
• By keeping track of the minimum and maximum indices, the code can quickly determine if the adjacent nodes have the same color, and if they do, perform the union operation to merge the components. This information is used to maintain the graph structure and update it whenever a node's color is changed.

Algorithm:

Initialize the variables:

• rank, parent, size, color, mini, maxi vectors of size n+1
  
• n, q as the number of elements in the array and number of queries respectively
  
• vec as the array of n elements
  
• ds as a Disjoint Set object of size n
  
• Read the array vec of size n and set the color of each element in ds.color

Merge adjacent elements of the same color in the array using unionByRank function of ds

Repeat the following steps q times:
1. Read the index and color of the element to be updated.
2. Get the representative of the set that contains the element.
3. Update the color of the representative and check if the adjacent elements have the same color. If so, merge the two sets using unionByRank.

Print the color of each element of the array after processing all the queries.

Note: The unionByRank function merges two sets with the same rank by updating the parent of the set with a lower rank to the representative of the set with a higher rank. If the ranks are the same, the rank of the set with the higher representative is incremented. The size, mini, and maxi of the merged set are also updated accordingly.

Time Complexity:

The time complexity of each modification operation is O(α(N)), where α is the inverse Ackermann function, which is very small and can be considered constant. The total time complexity of the algorithm is O(N + Q * α(N)).

Code:

#include <bits/stdc++.h>
using namespace std;

// @author: stash ¯\_(ツ)_/¯
#define FAST cin.tie(0), cout.tie(0),ios_base::sync_with_stdio(false);
#define int long long
#define debug(x) cerr << "[" <<#x << " = " << x << "]" << endl
#define debug2(x, y) cerr << "[" <<#x << " = " << x << "]" << ", [" <<#y << " = " << y << "]" << endl
#define all(x) (x).begin(),(x).end()
#define endl "\n"

class DisjointSet {
public: 
    vector<int> rank, parent, size,color,mini,maxi; 
    DisjointSet(int n) {
        parent.resize(n+1);
        size.resize(n+1);
        rank.resize(n+1);
        mini.resize(n+1);
        maxi.resize(n+1);
        color.resize(n+1);
        for(int i=0;i<=n;i++)
        {
            parent[i]=i;
            mini[i]=i;
            maxi[i]=i;
            rank[i]=1;
            size[i]=1;
        }
    }

    int get(int node) {
        if(node == parent[node])
            return node; 
        return parent[node] = get(parent[node]); 
    }

        void unionByRank(int u,int v)
    {
        u=get(u);
        v=get(v);
        if(u==v)
            return;
        if(rank[u]==rank[v])
            rank[u]++;
        if(rank[u]<rank[v])
            swap(u,v);

        size[u]+=size[v];
        parent[v]=u;
        mini[u]=min(mini[u],mini[v]);
        maxi[u]=max(maxi[u],maxi[v]);
    }
};

int32_t main()
{
    FAST
    int n,q;
    cin >> n >> q;
    vector<int> vec(n);
    DisjointSet ds(n);
    for(int i=0;i<n;i++)
    {
        int x;
        cin >> x;
        vec[i]=x;
        ds.color[i]=x;
    }
    for(int i=1;i<n;i++)
    {
        if(vec[i]==vec[i-1])
            ds.unionByRank(i,i-1);
    }
    
    
    while(q--)
    {
        int ind,col;
        cin >> ind >> col;
        int x=ds.get(ind);
        ds.color[x]=col;
        if(ds.mini[x]-1>=0 && ds.color[ds.mini[x]-1]==ds.color[x])
            ds.unionByRank(x,ds.mini[x]-1);
        
        if(ds.maxi[x]+1<=n && ds.color[ds.maxi[x]+1]==ds.color[x])
            ds.unionByRank(x,ds.maxi[x]+1);

        for(int i=0;i<n;i++)
        {   
            cout << ds.color[ds.get(i)] << " ";
        }
        cout << endl;
    }
}