horses.cpp

#include "horses.h"
#include <set>
#include <iostream>

using namespace std;

typedef long long llint;

const int MAXN = 1<<19;
const llint MAX = 1<<30;
const llint MOD = 1e9 + 7;

llint x[MAXN], y[MAXN];
set<int> non1;

llint inv(llint a)
{
	llint sol = 1;
	int b = MOD - 2;
	while (b)
	{
		if (b % 2)
			sol = sol * a % MOD;
		b /= 2;
		a = a * a % MOD;
	}
	return sol;
}

namespace tour
{
	pair<llint, int> data[2 * MAXN];
	
	void set(int node, llint val)
	{
		node += MAXN;
		data[node] = make_pair(val, node - MAXN);
		for (node /= 2; node; node /= 2)
			data[node] = max(data[2 * node], data[2 * node + 1]);
	}
	
	pair<llint, int> get(int start, int stop, int node = 1, int lo = 0, int hi = MAXN)
	{
		if (lo >= stop || hi <= start)
			return {0ll, 0};
		if (lo >= start && hi <= stop)
			return data[node];
		int mid = (lo + hi) / 2;
		return max(get(start, stop, 2 * node, lo, mid), get(start, stop, 2 * node + 1, mid, hi));
	}
}

namespace loga
{
	llint data[MAXN];
	
	void init()
	{
		for (int i = 0; i < MAXN; ++i)
			data[i] = 1;
	}
	
	void add(int i, llint val)
	{
		for (++i; i < MAXN; i += i&-i)
			data[i] = data[i] * val % MOD;
	}
	
	llint get(int i)
	{
		llint sol = 1;
		for (++i; i; i -= i&-i)
			sol = sol * data[i] % MOD;
		return sol;
	}
}

llint solve()
{
	auto it = prev(non1.end());
	int prv = *it;
	llint thres = 0;
	pair<llint, int> sol = {0ll, 0}, nes;
	
	do
	{
		--it;
		
		nes = tour::get(*it, prv);
		
		if (nes.first > thres)
		{
			sol = nes;
			thres = nes.first;
		}
		
		thres *= x[*it];
		
		prv = *it;
	} while (it != non1.begin() && thres < (1<<30));
	
	return sol.first * loga::get(sol.second) % MOD;
}

int init(int n, int X[], int Y[])
{
	loga::init();
	int i;
	
	for (i = 0; i < n; ++i)
	{
		x[i] = X[i];
		loga::add(i, x[i]);
		y[i] = Y[i];
		tour::set(i, y[i]);
	}
	
	non1.insert(0);
	non1.insert(n);
	for (i = 1; i < n; ++i) if (x[i] != 1)
		non1.insert(i);
	
	return solve();
}

int updateX(int pos, int val)
{
	loga::add(pos, inv(x[pos]));
	if (pos)
		non1.erase(pos);
	
	x[pos] = val;
	
	loga::add(pos, x[pos]);
	if (x[pos] != 1)
		non1.insert(pos);
	
	return solve();
}

int updateY(int pos, int val)
{
	y[pos] = val;
	tour::set(pos, val);
	
	return solve();
}