your array should be initialized with a constant value. In case of your code: int a[n+1] and int si[l] are wrong!

Yes, added!

Another solution :))

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

int main()
{
	int n;
	cin >> n;
	cout << (int)log2(n) + 1;
	return 0;
}

A condition

2 2 1 1 2

output: Yes

this might be the condition

For understanding what the tutorial is trying to say, first you need to understand how graph is stored in an adjacency list and BFS Order Traversal. If you understand these two things, then you can read ahead.

Basically, the way you store nodes in adjacency list, determine how your BFS Order Traversal is going to look like.

So, for checking the given BFS Order, you store the neighbours of a node in the list according to the order they appear in the given BFS Order Traversal. Basically, "we can sort the adjacency lists of all the nodes in the order in which they are present in the input BFS Sequence." (as mentioned in editorial)

Once you get the adjacency list according to given BFS Order, Do BFS on the list and then check whether it matches the given order or not.

Here is my editorial to D. Let me know if it helps :)

maybe this condition

see this comment

If you ever use Dijkstra with all edge weights as 1, use BFS instead. But I don't think it would work. You have to add all nodes connected to the last node in some order, but you can't mix them with other nodes (even if they are on same distance from 1).

You don't initialize local visited array with zeros

Median is middle element in a sorted array.

Now, modifying Median may break the sorted order of the array elements. So we make sure elements before the median are still smaller than new median and all the elements after median are larger than new median too.

For each character c, you need to precalculate grundy numbers of strings between consecutive occurrences of c, their prefixes and suffixes. When a string s breaks into multiple strings, the first part is a calculated suffix, last part is a calculated prefix. For other parts, you can keep prefix xor of the calculated xors. So suppose you have a string adbecbdabfr and query on dbecbdabf and you choose character b (as your first move), the precalculated grundy numbers will be of ad, ec, da and fr and their prefixes and suffixes. To answer the query, you take d suffix from ad and f prefix from fr. ec and da can be retrieved from prefix xor.

There are n + 26 such strings. You can consider them as queries while precalculating and order them properly such that the required values are calculated before the query.

To be able to make 1 you defnitely need the coin of value 1 so it has to be included.d now to make 2 you can include another coin of value one to sum to 2 or you can use a coin with value 2 so that you can make 3 as well so using coin with value 2 is optimal. You can go on inductively to show 2^k is optimal.

Lets assume that we can take <= log2(n) coins. We can choose some of them in 2^log2(n) = n different ways. So there are at most n different sums. One of them is 0. So we have at most n-1 non-zero sums. It is not enough to cover n numbers(1, ..., n). Thus answer is not <= log2(n), answer is >= log2(n)+1. So, log2(n)+1is optimal answer.

Now we have to find log2(n)+1 coins. These are 1, 2, 4, ..., 2^(log2(n)+1). We can prove its optimality by induction. First i coins cover numbers [1 ... 2^i-1]. Next coin is 2^i. With that coin we can obtain also sums 2^i, 2^i+1, ..., (2^i+2^i-1 = 2^(i+1)-1). So with first i+1 numbers we can cover 2^(i+1)-1 coins.

Maybe for work on boundary of array and taking this size to sure don't go out of size of array ... actually for more security

i see you have never got WA/RE because of wrong bounds

Can you please describe how the third sample test case works??????? I couldn't figure it out.

Just have a look at the solve() function rest is just template.

#define ve vector
int n, m, k;
cin >> n >> m >> k;
ve<pair<int, int> > Edges(m);
ve<int> Ans(m);
ve<int> degree(n);
ve<ve<pair<int, int> > > adj(n);
set<pair<int, int> > Good_set;
ve<int> in_good_set(n, true);
for (int i = 0; i<m; i++)
{
	cin >> Edges[i].first >> Edges[i].second;
	Edges[i].first--;
	Edges[i].second--;
	adj[Edges[i].first].pb({ Edges[i].second,i });
	adj[Edges[i].second].pb({ Edges[i].first,i });
	degree[Edges[i].first]++;
	degree[Edges[i].second]++;
}
for (int i = 0; i<n; i++)
{
	Good_set.insert({ degree[i],i });
}
while (!Good_set.empty() && Good_set.begin()->first<k)
{
	int node = Good_set.begin()->second;
	for (auto &y : adj[node])
	{
		int x = y.first;
		if (in_good_set[x])
		{
			Good_set.erase({ degree[x],x });
			--degree[x];
			Good_set.insert({ degree[x],x });
		}
	}
	Good_set.erase({degree[node],node});
	in_good_set[node] = false;
}

for (int i = m - 1; i >= 0; i--)
{
	Ans[i] = Good_set.size();
	int u = Edges[i].first, v = Edges[i].second;
	if (in_good_set[u] && in_good_set[v])
	{
		Good_set.erase({ degree[u],u });
		--degree[u];
		Good_set.insert({ degree[u],u });

		Good_set.erase({ degree[v],v });
		--degree[v];
		Good_set.insert({ degree[v],v });

		while (!Good_set.empty() && Good_set.begin()->first<k)
		{
			int node = Good_set.begin()->second;
			for (auto &y : adj[node])
			{
				int x = y.first;
				if (y.second >= i)
					continue;
				if (in_good_set[x])
				{
					Good_set.erase({ degree[x],x });
					--degree[x];
					Good_set.insert({ degree[x],x });
				}
			}
			Good_set.erase({degree[node],node});
			in_good_set[node] = false;
		}
	}
}
for (int i = 0; i<m; i++)
{
	cout << Ans[i] << "\n";
}

https://www.geeksforgeeks.org/the-stock-span-problem/

Did you get the answer? I'm also confused why is it 2*k and not 2*k-1 in the explanation. EDIT: Got the answer. Here is a great explanation.

Consider of example the ith position of the array of leaves has value l_i, now we will be maintaining a set of persistent segment trees from left to right, that is persistent segment tree for ith leaf is obtained by adding value 1 to the l_i position of persistent segment tree of leaf i - 1. To do this, maintain three arrays, seg_tree, L_ptr, R_ptr. The node represented by integer id c will represent-

1. seg_tree[c]: The sum of values in the segment represented by current node.

2. L_ptr[c]: The left child of node represented by c.

3. R_ptr[c]: The right child of node represented by c.

Now to add the value l_i to the persistent segment tree of leaf i - 1 and get the root node for the persistent segment tree for leaf i, we can adopt the following algorithm.

If we have persistent segment of node i - 1 as c, we can obtain persistent segment tree for node i by calling add(c,0,|S|,l_i).

int add(int c, int l, int r, int pos)
{
	if (l>pos || r < pos)
		return c;
	int ID = Next++;
	if (l == r)
	{
		seg_tree[ID] = seg_tree[c] + 1;
		return ID;
	}
	int mid = (l + r) >> 1;
	L_ptr[ID] = add(L_ptr[c], l, mid, pos);
	R_ptr[ID] = add(R_ptr[c], mid + 1, r, pos);
	seg_tree[ID] = seg_tree[L_ptr[ID]] + seg_tree[R_ptr[ID]];
	return ID;
}

Now to find whether the current subtree contain any value in the range L ≤ R,

Let a + 1 be index of left-most leaf in the current subtree, and b be the right-most leaf in the current subtree and p_j represent the persistent segment tree of leaf j.

Now we need to only take two segment trees p_a and p_b and query if sum of values in the segment L... R is non zero.

To do this we can apply the following method or say call find_sum(p_a, p_b, 0, |S|, L, R)

int find_sum(int l_tree_c, int r_tree_c, int l, int r, int qry_l, int qry_r)
{
	if (qry_l > r || qry_r < l)
		return 0;
	if (l >= qry_l && r <= qry_r)
	{
		return seg_tree[r_tree_c] - seg_tree[l_tree_c];
	}
	int mid = (l + r) >> 1;
	return find_sum(L_ptr[l_tree_c], L_ptr[r_tree_c], l, mid, qry_l, qry_r) + \
		find_sum(R_ptr[l_tree_c], R_ptr[r_tree_c], mid + 1, r, qry_l, qry_r);
}

If returned value of the above function is non-zero then there is some value in the range L ... R. You may also like to see the find_first method in the code given in the tutorial to find the smallest value which is greater than L but less than R.

So this is how we can check in O(log|S|) time whether there is some leaf in the current subtree with value in range L ... R.

Let us know if something is still not clear.

You always start from root which is 1. So it's impossible that you visit any other node before 1. Therefore, sequence must always start with 1. Here it starts with 2.

hitman623

This is not clarification of the method from the tutorial, but slightly different method of calculating total count for each number.

On the figure above you can see progression of b arrays for given array a and k = 3. To calculate total count for number 8 you want to calculate count of all numbers in the triangle (their count is proportional to r - l) and then subtract blue ones (their count is proportional to i - l) and green ones (their count is proportional to r - i).

Turns out, you don't really need all that case work. Here.

don't do that, please

TooDumbToWin

Maybe this one is simpler :)

42377485

Yes, the editorial approach will work in that case also.

See this explanation from saluev

Aren't you using a vector<set<>> ? So time complexity can't be O(n). Shouldn't it be O(nlogn)? I'm not sure of my answer though