Flowers (Editorial)

Let's denote a bit string $s$ where s[i] = 1 if the element $i$ was taken with a plus and s[i] = 0 if the element $i$ was taken with a minus. For example, $10110$ corresponds to a[0] - a[1] + a[2] + a[3] - a[4] .

If we look at such a string after the operation $beauty$, it should start with $10$.

Actually, we can use the operation to obtain any array starting with $10$.

Proof by induction:

Supposing the statements for lengths less than $n$ are true, we want to prove the statement for $n$ is also true.

1. Case: In the string, the first element is $1$ and all the others are $0$.

   Let $n$ be the size of the string.

   In this case, we can perform beauty(1, n) and let m = n - 1 ;

   Then we perform recursively beauty(1, n - 1) to make the first element of the string $1$ and all the others $0$.

2. Case: There is more than one $1$ in the string.

   Let $ind$ be the index of the second $1$ from the left.

   We perform beauty(1, n).

   Let m = ind - 2 ;

   This way we need to perform beauty(1, ind-2) and beauty(ind-1, n), but beauty(ind-1, n) is taken with minus sign. So for beauty(ind-1, n) we need to revert the signs.

Then the answer to the query $l,r$ is a[l] - a[l + 1] + \sum_{i=l + 2}^r |a[i]|

where $|x|$ is the absolute value of $x$.

 
//In honor of TimDee

#define int long long
 
int inf = 4000000007000000007ll;
int NADIYA = 40;
int mod = 1000000007;
int log_ = 20;
 
vector <int> pref;
 
int get(int l, int r)
{
	if (l == 0)
		return pref[r];
	else
		return pref[r] - pref[l - 1];
}
 
signed main()
{
	std::ios::sync_with_stdio(false);
	std::cin.tie(nullptr); std::cout.tie(nullptr);
 
	int n , q;
	cin >> n >> q;
 
	vector <int> a(n);
 
	for (int i = 0; i < n; i++)
		cin >> a[i];
 
	int p = 0;
	pref.resize(n);
 
	for (int i = 0; i < n; i++)
	{
		p += abs(a[i]);
		pref[i] = p;
	}
 
	for (int i = 0; i < q; i++)
	{
		int l, r;
		cin >> l >> r;
 
		l--;
		r--;
 
		if (l == r)
		{
			cout << a[l] << endl;
			continue;
		}
 
		if (l + 1 == r)
		{
			cout << a[l] - a[l + 1] << endl;
			continue;
		}
 
		cout << a[l] - a[l + 1] + get(l + 2, r) << endl;
	}
}