题解：P14322 「ALFR Round 11」E 空崎ヒナ

一道很好的题，只是数据有点差强人意。

特别鸣谢 Iniaugoty 的讨论提供了本题理论可过解的时间复杂度，一定程度上帮助我解出了本题。

首先，我们不难将题目中给出的

b_y\equiv x\pmod {\displaystyle\max_{l\le i\le y} a_i}

转化为

|b_y-x|\equiv 0\pmod{\displaystyle\max_{l\le i\le y}a_i }

，其充要性显然。

所以，在第一步，我们可以预处理

1

到

\max(x,\displaystyle\max_{i=1}^n |a_i-x|)

中所有数的因数，以便于接下来的操作。设

v=\max(x,\displaystyle\max_{i=1}^n |a_i-x|)

，则该部分时间复杂度为

O(v\ln v)

。显然，本题的时间瓶颈不可能出现在这里。

接下来，考虑这样一个问题：对于一个固定的右端点

i

，如何判断查询的左端点为哪些

1\le l\le i

时，位置

i

会给该查询的答案贡献

1

？转化上面的化简得到

|b_i-x|\equiv 0\pmod{\displaystyle\max_{l\le j\le i} a_j}

。显然，此时

|b_i-x|

是定值，我们可以方便地知道哪些

\displaystyle\max_{l\le j\le i} a_j

是能对答案产生贡献的。

我们使用树状数组维护每个左端点的答案，而对于最大值发生变化的位置，我们可以使用一个单调栈进行维护。接着，对于每个

i

，处理完单调栈后，直接枚举单调栈中的每个最大值，在每次找到一个合法最大值时给这个最大值所覆盖的左端点区间加上

1

，查询时单点查询即可。

这是个非常优美且直接的写法。你将它完成实现并上交，发现你 AC 了这道题。它跑得很快，挤进了最优解的第一页。

但不要急。仔细思考一下，我们不难构造一个

a

值单调下降的样例。

#include <iostream>
using namespace std;
const int N = 1e6;
int main()
{
	cout << N << ' ' << N << ' ' << 1 << '\n';
	for (int i = 0; i < N; i++)
		cout << N - i << " \n"[i == N - 1];
	for (int i = 0; i < N; i++)
		cout << i << " \n"[i == N - 1];
	for (int i = 0; i < N; i++)
		cout << i << " \n"[i == N - 1];
	for (int i = 0; i < N; i++)
		cout << i << " \n"[i == N - 1];
}

在这种情况下，按照上面的算法，你的程序将会在每个

i

中遍历

1\le l<i

的所有位置，其时间复杂度为

O(n^2)

！而且，你在这些遍历时每一次都需要进行模运算，其常数巨大无比！

在这惊诧之下，你决定寻找更优的解。

思考一下我们刚才的过程。单调栈内的元素数量可能很大，每次枚举单调栈内的所有元素显然是不现实的。但我们要想起我们在一开始花费

O(v\ln v)

时间构造的因数序列。显然，单调栈内没有重复出现的元素，而若我们称数

k

的因数有

d(k)

个，我们可以进行一个粗略的估计：

对于一个数

k

，我们不难得出其唯一质因数分解：

k=\prod_{i=1}^s p_i^{t_i}

其中，每个

p_i

都是不同的质数。那么不难得到

d(k)=\prod_{i=1}^s (t_i+1)

对于每个质数

p_i

，我们可以选出

[0,t_i]

个乘起来，得到一个

k

的因数。每个选择是独立的，由此可以得到上面的式子。

显然，

d(k)

在大多数时候上显著小于

n

。将上面的枚举单调栈元素改为枚举因数，我们得到了一个显著更优的时间复杂度。你将其上交：没有疑问，又是一个绿色的 AC。

但此时，你仍然感觉哪里不对。

根据上面的定义，我们不难发现构建一个尽量小的有很多不同因数的数的最高效方法是选取不同的最小质数乘起来。

使用计算器，我们用这种方法构建一个有很多不同因数的不大于

10^6

的数：

510510=2\times 3\times 5\times 7\times 11\times 13\times 17

这个数有

2^7=128

种不同的因数。同样的，我们构建一个长度为

10^6

的序列

a

，在它的前面，按降序排列着

510510

的

128

种不同的因数，中间可能还要夹几个不是它的因数的数来避免特判优化；后面则是填满了

1

。

随后，我们随机生成一个

b

序列，并将其中的很多（但不是全部）的数替换成一个与

x

的差为

510510

的数。

而询问，对于每个右端点

r

，任取一左端点

1\le l\le r

即可。

在此种情况下，我们对计算量进行一个不算严谨的估计：

一次树状数组操作的时间复杂度是

O(\log n)

的。在

n=10^6

的情况下，我们认为这个值约为

20

。

在（一个足够后的）右端点

i

，其对应的单调栈中包含

2^7

个或多一点点的元素，其中完整地包含了

510510

的所有

2^7

个因数。你将会枚举这

2^7

个因数，每一个因数均会完美命中一个单调栈元素。并且为了处理差分数组的一次加和一次减，你将会执行

2^{7+1}\times 20=2^{10}\times 5

次操作。

接下来，对于

n

个右端点，我们（姑且）认为每个位置都会进行一次上面的操作，那么其计算量来到了

10^6\times 2^8\times 5=1.28\times 10^9

树状数组有较小的常数，所以上面的估计可能稍大了一点。在本题 2s 的时限下，通过本题已经不成问题。

但你仍不满足。你注意到了另一件事情：在上面的构造中，树状数组上进行了

2^8\times 10^6

次修改操作，但查询只有

10^6

次！这显然是太不平衡了。

为了解决这个问题，你想到了一个东西，一个可以被用到莫队里面，用来替换树状数组以更好地平衡左右端点移动与查询的时间复杂度的结构：分块差分数组。

分块差分数组由

k

层差分数组组成，此处显然有

k>1

。设数组长度为

n

，则设阈值为

b=\sqrt[k] n

。对于

1\le i<k

层差分数组，其大小为

b^i

；而对于第

k

层，长度为

n

。不难发现，该结构可以使用

k

次计算完成一次后缀修改，使用

O(k\sqrt[k] n)

次计算完成一次单点查询。

而关键就在这里。该结构的修改复杂度远小于查询复杂度，这刚好和我们的需求相吻合。

现在，我们终于可以确定我们的时间复杂度了。

对于

n

个右端点，我们进行

d(v)

次修改操作，其计算量为

O(nkd(v))

；对于

q

次询问，我们查询一次前缀和，其计算量为

O(qk\sqrt[k]n)

。则总时间复杂度为

O(nkd(v)+qk\sqrt[k]n)

。令

k=3

，估计计算量为

10^6\times 3\times 2\times 2^7+10^6\times 3\times 10^2=1.068\times 10^9

在这样的计算量下，我们终于可以有信心地认为任何正常的评测系统都不可能在这种计算量量级下返回时间超限的结果。

#include <algorithm>
#include <cmath>
#include <iostream>
#include <string>
using namespace std;
const int N = 1e6 + 10, K = 1e2 + 10;
int n, m, k, a[N], b[N], l[N], mx, blks1, blks2, blk1[N], blk2[N], stk[N], sidx, stkd[N], res[N];
int sm[N], sm1[K * K], sm2[K];
basic_string<int> qry[N], fac[N];
void update(int x, int v)
{
	sm[x] += v;
	sm1[blk1[x]] += v;
	sm2[blk2[x]] += v;
}
int query(int x)
{
	int res = 0;
	while (x and blk1[x] == blk1[x + 1])
		res += sm[x], x--;
	while (x and blk2[x] == blk2[x + 1])
		res += sm1[blk1[x]], x -= blks1;
	while (x)
		res += sm2[blk2[x]], x -= blks2;
	return res;
}
int main()
{
	freopen("input.txt", "r", stdin);
	freopen("output.txt", "w", stdout);
	cin.tie(0);
	cout.tie(0);
	ios::sync_with_stdio(0);
	cin >> n >> m >> k;
	blks1 = cbrtl(n);
	blks2 = blks1 * blks1;
	for (int i = 1, j = 0, k = 0; i <= n; i++, j = (j + 1 == blks1 ? 0 : j + 1), k = (k + 1 == blks2 ? 0 : k + 1))
		cin >> a[i], blk1[i] = blk1[i - 1] + !j, blk2[i] = blk2[i - 1] + !k;
	for (int i = 1; i <= n; i++)
		cin >> b[i], mx = max(mx, b[i]);
	mx = max(mx, k);
	for (int i = 1; i <= mx; i++)
	{
		for (int j = i; j <= mx; j += i)
			fac[j] += i;
	}
	for (int i = 1; i <= m; i++)
		cin >> l[i];
	for (int i = 1, r; i <= m; i++)
	{
		cin >> r;
		qry[r] += i;
	}
	for (int i = 1; i <= n; i++)
	{
		while (sidx and a[stk[sidx]] <= a[i])
		{
			stkd[a[stk[sidx]]] = 0;
			sidx--;
		}
		stk[++sidx] = i;
		stkd[a[i]] = sidx;
		if (b[i] != k)
		{
			b[i] = abs(b[i] - k);
			for (auto &j : fac[b[i]])
			{
				if (!stkd[j])
					continue;
				update(stk[stkd[j] - 1] + 1, 1);
				update(stk[stkd[j]] + 1, -1);
			}
		}
		else
		{
			update(1, 1);
			update(i + 1, -1);
		}
		for (auto &j : qry[i])
			res[j] = query(l[j]);
	}
	for (int i = 1; i <= m; i++)
		cout << res[i] << " \n"[i == m];
}

题解：P14322 「ALFR Round 11」E 空崎ヒナ

文章操作

相关推荐

评论

题解：P14322 「ALFR Round 11」E 空崎ヒナ