自动搬运

查看原文

来自洛谷，原作者为

	ayaka 周而复始的7days。

搬运于2025-08-24 23:10:00，当前版本为作者最后更新于2025-03-25 18:15:32，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

思路

我在做完这道题后想出了一个更好理解的推结论过程，所以这里附出更简单的版本。至于更丑陋的考场版本有兴趣可以看看。

答案显然是每一段连续的 $0$ 的情况相乘后的答案，因此先只考虑连续的 $0$。因为显然对一个位置进行操作 $2$ 后，直到其左边第一个非 $0$ 数，之间的所有数全部会被染成一种颜色，不好讨论，考虑从左到右来进行操作。

随后，不难发现，对于一个已经被选择为 $0$ 的点，即使这个点被后面的一次操作 $2$ 染上色了，这也仍然只是一种情况，可推出对于每一个点，有进行操作 $1$，进行操作 $2$，以及不操作三种情况，可得如果有 $n$ 个连续的 $0$，总情况为 $3^n$。

然后我们的问题就变成了如何求出每次询问里序列 $a$ 中 $0$ 的数量。不难想到离散化后使用线段树维护即可，因为不是此题重点就不细说了。

时间复杂度 $O(q\log n)$。

代码

#include<bits/stdc++.h>
using namespace std;
#define int long long
#define ll (k<<1)
#define rr (k<<1|1)
#define mid ((l+r)>>1)
const int mod = 1e9 + 7;
int qpow(int a, int b) {
	int res = 1;
	while (b) {
		if (b & 1) res = res * a % mod;
		a = a * a % mod;
		b >>= 1;
	}
	return res;
}
struct que {
	int l, r;
} p[1000005];
map <int, int> mp;
int num[1000005], cnt, ls[1000005], un;
struct tree {
	int l, r, lazy, num, sum;
} t[4000005];
int n, q;
inline void pushup(int k) {
	t[k].num = t[ll].num + t[rr].num;
}
void build(int k, int l, int r) {
	t[k].l = l;
	t[k].r = r;
	if (l == r) {
		t[k].num = num[l];
		t[k].sum = num[l];
		return ;
	}
	build(ll, l, mid);
	build(rr, mid + 1, r);
	pushup(k);
	t[k].sum = t[ll].sum + t[rr].sum;
	return ;
}
inline void pushdown(int k) {
	if (t[k].lazy) {
		t[ll].lazy ^= 1;
		t[rr].lazy ^= 1;
		t[ll].num = t[ll].sum - t[ll].num;
		t[rr].num = t[rr].sum - t[rr].num;
		t[k].lazy = 0;
	}
}
void update(int k, int l, int r) {
	if (t[k].r < l || t[k].l > r) return ;
	if (t[k].r <= r && t[k].l >= l) {
		t[k].lazy ^= 1;
		t[k].num = t[k].sum - t[k].num;
		return ;
	}
	pushdown(k);
	update(ll, l, r);
	update(rr, l, r);
	pushup(k);
	return ;
}
signed main() {
	cin >> n >> q;
	for (int i = 1; i <= q; i++) {
		cin >> p[i].l >> p[i].r;
		ls[i * 2 - 1] = p[i].l, ls[i * 2] = p[i].r;
	}
	sort(ls + 1, ls + q * 2 + 1);
	un = unique(ls + 1, ls + q * 2 + 1) - ls - 1;
	for (int i = 1; i <= un; i++) {
		num[i * 2 - 1] = ls[i] - ls[i - 1] - 1;
		num[i * 2] = 1;
		mp[ls[i]] = i * 2;
	}
	num[un * 2 + 1] = n - ls[un];//num 数组保存的是这一个新点存储了几个点 
	build(1, 1, un * 2 + 1); 
	for (int i = 1; i <= q; i++) {
		p[i].l = mp[p[i].l];
		p[i].r = mp[p[i].r];
		update(1, p[i].l, p[i].r);
		cout << qpow(3, t[1].num) % mod << "\n";
	}
	return 0;
//}

关于更多

这里附考场思路：

首先只考虑对一段连续的 $0$ 做操作 $2$ 的情况。操作 $2$ 也就是把从一个点到其左边第一个非 $0$ 数前的所有数染上同一个颜色。接下来，我们对于每个数就有了“染了色”和“未染色”两种情况。根据题面给出的“等价”的概念，我们不用在意这个染色具体是哪种颜色，只需要知道这一段的颜色与其他所有颜色都不同就好了。

接下来对这个情况进行简单的讨论：

• 当有 $1$ 个 $0$ 时，显然对于第 $1$ 个数有两种选择：染色或不染。
• 当有 $2$ 个 $0$ 时，对于第 $2$ 个数，前一个数未被染色的情况有 $1$ 个，此时这一个数也只能不染色，因为按照操作 $2$ 的定义，不可能存在两段染了色的段中间有一段未染色的情况。因此前一个数未染色而这一个数未染色的情况有一种；而前一个数被染色的情况有 $1$ 种，那这个点有三种选择：染前一个点的颜色，染新的颜色，不染。最后总情况为 $4$ 种，这个点未被染色的有 $2$ 种，被染色的有 $2$ 种。
• 当有 $3$ 个 $0$ 时，根据上一种情况可得前一个数未染色可推出的情况有 $1\times 2=2$ 种，而前一个数被染色的情况有 $3\times 2=6$ 种，总情况有 $8$ 种，这个点未被染色的有 $4$ 种，被染色的有 $4$ 种。

接着根据这个规律，显然可得有 $n$ 个 $0$ 时，总情况有 $2^n$ 种。

接下来，我们加入第 $1$ 种操作。可以将第 $1$ 种操作看作是把一段连续的 $0$ 拆成几个部分，显然若添加了 $x$ 个 $-1$，则总情况为 $2^{n-x}$ 种。可得总情况为：

根据牛顿二项式定理（或者打一点表出来看）可得此式为 $3^n$。随后可得结论。