Destroying Array | Editorial by ankitraj1996

Hello everyone this is the editorial for the question **Destroying Array** from the codeforces round 722 and its a C problem so it carries a good concept.

**Problem Statement :-**

You are given an array consisting of n non-negative integers a1, a2, ..., an.

You are going to destroy integers in the array one by one. Thus, you are given the permutation of integers from 1 to n defining the order elements of the array are destroyed.

After each element is destroyed you have to find out the segment of the array, such that it contains no destroyed elements and the sum of its elements is maximum possible. The sum of elements in the empty segment is considered to be 0.

**Sample Input :-**

4
1 3 2 5
3 4 1 2

**Sample Output :-**

5
4
3
0

**Explanation :-**

Initially the array is [1, 3, 2, 5]
After deleting the element from 3rd position the array changes to [1, 3, _ , 5]
So the maximum sum segment of the array with no destroyed elements is 5
After deleting the element from  4th position the array changes to [1, 3, _ , _ ]
So the maximum sum segment of the array with no destroyed elements is 4
And so on we can see that the results will be 3 and 0 for the given positions to be destroyed.

**Pre-requisites :-**

I have solved this problem using Disjoint Set Data Structures (**DSU**), it can also be solved by using Segment Trees.

**Solution :-**

We can solve this question in a reverse order and we solve the queries in an offline way. Offline solving means all the queries will be processed at once.
Now the idea is that while solving in the reverse order, the positions given for destroying the element will work as index to insert elements in the array.
**Example** - The destruction indices are [3, 4, 1, 2], so if we reverse it we will get [2, 1, 4, 3] . Now let us assume that we have an temproary array which was initially empty, so following 
the insertion order our array will be filled up like this :-
Also let us have an array named result .
step 1 - result[1] will be **0** since initially the temproary array was empty and after inserting the value the array will look like [ _ , 3, _ , _ ] since at index 2 we have value 3 
step 2 - result[2] will be **3** since the temproary array contains only 3, and after inserting the value the temproary will look like [1, 3, _ , _ ] since at index 1 we have value 1
step 3 - result[3] will be **4** since we have a continuous segment [1, 3] and it sums to be 4, and after inserting the temproary array will be [1, 3, _ , 5] since at index 4 we have value 5
step 3 - result[4] will be **5** since we have two segments [1, 3] and [5] and the higher value is 5, and after inserting the temproary array will be  [1, 3, 2, 5]

So now we can use disjoint data structure in this case, and here is the logic.
And I will explain it with the help of code snippets :-
```
/*
 * Ankit Raj, NIT Agartala
 */
#include<bits/stdc++.h>
using namespace std;
#define lld long long int
#define lim 100007
#define BOOST ios_base::sync_with_stdio(0) 
#define NITRO cin.tie(NULL)
#define pb push_back
#define mp make_pair
#define F first
#define S second
lld parent[lim];        // This array is used to store the parent of each element
lld size[lim];            // This array is used to store the size of each tree which contains ith element or has the root as the ith element
lld destroy[lim];      // Array used to store the index of elements to be destroyed
lld arr[lim];             
lld val[lim];              // Array used to keep the sum value of each tree
bool visited[lim];    // To check if the ith element is visited or not
lld res[lim];
lld answer = 0;
//////////////////////////////DSU WITH PATH COMPRESSION AND UNION BY SIZE////////////////////////////////////////////
void make_set(int v)
{
	parent[v]=v;
	size[v]=1;
	//nexti[v]=v+1;
}
int root(int v)     //finding the root of the tree in which v is located using path compression
{
	if(v==parent[v])
	{
		return v;
	}
	return parent[v]=root(parent[v]);
}
void union_set_by_size(int a,int b)    //union by size method
{
	a = root(a);
	b = root(b);
	if(a!=b)
	{
		if(size[a]<size[b])
		{
			parent[a] = b;
			size[b] += size[a];
			val[b] += val[a];
		}
		else
		{
			parent[b]=a;
			size[a]+=size[b];
			val[a]+=val[b];
		}
	}
}
//////////////////////////////////////////////////////////////////////////////////////////////////////////////////
int main()
{
	BOOST;
	NITRO;
	clock_t t1,t2;
	t1 = clock();
	/*
	#ifndef ONLINE_JUDGE
	freopen("input.txt","r",stdin);
	freopen("output.txt","w",stdout);
	#endif
	*/ 
	//Main Code
	int n,i;
	cin>>n;
	for(i=1;i<=n;i++)
	{
		cin>>arr[i];
		parent[i]=i;
		size[i]=1;
		val[i]=arr[i];
	}
	for(i=n;i>=1;i--)
	{
		cin>>destroy[i];
	}
    
    // This is the main loop where the problem is been solved, first we assing res[i] = answer and then we assign the destroy[i] as true in the visited array,
    // Now suppose in the [ _, 3, _ , 4] we are adding 5 at index 3, so we can see that after adding 5 the largest sum subsegment becomes [3, 5 ,4]. So if
    // we are adding a value at ith index then we should check if a value exists at (i-1) or (i+1) and if the value exists we should merge them and update the val[]
    // for each element, and this is done by union_set_by_size method.
    
	for(int i=1;i<=n;i++)
	{
		res[i] = answer;
		visited[destroy[i]]=true;
		if(visited[root(destroy[i]-1)])
		{
			union_set_by_size(destroy[i]-1,destroy[i]);
		}
		if(visited[root(destroy[i]+1)])
		{
			union_set_by_size(destroy[i]+1,destroy[i]);
		}
		answer=max(answer,val[root(destroy[i])]);
	}
	for(i=n;i>=1;i--)
	{
		cout<<res[i]<<"\n";
	}
	return 0;

t2 = clock();
	float diff = (float)t2 - (float)t1;
	float execution_time = diff/CLOCKS_PER_SEC;
	//cout<<"\n"<<execution_time;
	//system("pause");
}

```

I hope the editorial is useful, and to know about DSU one can read about it on cp-algorithms page.

Destroying Array | Editorial by ankitraj1996

Download submission

All caught up!

View submission

Is your resume even shortlisted?