TopCoder SRM681(Div.1) Normal LimitedMemorySeries2

Posted on By 二价氢

题目大意

定义一个数列\({a_n}\)中,第\(i\)个数的“半径”\(r_i\)为最大的\(k\),使得\(\forall x \in [i - k, i - 1] \cup [i + 1, i + k], a_x < a_i\)

求\(\sum r_i\),要求不能存储整个数列。

解法

这里“不能存储整个数列”的条件是由题意推出来的,题目中的原话是使用不超过 1 MiB 的内存。题目的Tag是暴力,当然比赛时看不到这个Tag,一般而言,打上暴力的标签,就意味着我们需要复杂度分析。

我们先考虑如果不限制内存使用,我们会怎么做——显然,建线段树,二分答案,总的复杂度是\(O(n (\log n) ^ 2)\)。算是比较理想的复杂度。

不过,我们又会注意到,会贡献答案的,只是区间极值,所以,我们不妨考虑一下最坏情况,即区间最大值最多的情况,即有一半的数都是极大值(\(x_{i - 1} < x_i, x_i > x_{i + 1}\))的情况。这时,我们手动构造一组数据,能发现它会长成一棵满二叉树的鬼样子,继续观察,发现每一层答案对答案的贡献的期望值都是\(O(n)\)的。

到这里,我们的解法已经很明显了,我们可以直接暴力啊。

显然,暴力的复杂度也只有\(O(n \log n)\),比我们用线段树的答案还要优……而且,这种做法还不需要存储整个数列……

具体的做法看代码就好了。

Code

typedef pair<long long, pair<int, bool> > pii;
#define x first
#define y second
const int mod = 1000000007;
class LimitedMemorySeries2 {
public:
	inline long long getNext(long long x, long long a, long long b) {
		return ((x ^ a) + b) & ((1ll << 50) - 1);
	}
	inline long long getPrev(long long x, long long a, long long b) {
		return (((x - b) + (1ll << 50)) ^ a) & ((1ll << 50) - 1);
	}
	int getSum(int n, long long x0, long long a, long long b) {
		long long ret = 0;
		for (int i = 0; i < n; i++) {
			long long pre = getPrev(x0, a, b), nxt = getNext(x0, a, b);
			int j = 1;
			for (j = 1; i - j >= 0 && i + j < n; j++) {
				if (pre >= x0 || nxt >= x0) break;
				pre = getPrev(pre, a, b), nxt = getNext(nxt, a, b);
			}
			(ret += j - 1) %= mod;
			x0 = getNext(x0, a, b);
		}
		return ret;
	}
};

Level Upper 2016 - TopCoder 500 : 3 / 5