这道题个人觉得理论上来说分块是可以做的，但不知道为什么一直会 T 在第 11 个点，改成线段树后惊奇的发现居然是目前洛谷上的最优解，写篇题解纪念一下。

题目大意

给出一个长度为 nn 的数列 aa，初始时所有元素都为 00，有 mm 次修改，每次把 ava_{v} 的值改成 tt，且 t∈[0,3]t\in[0,3]，修改完之后，询问如果把这个数列中所有的 00 都改成 11 到 33 中的某个整数（两个 00 可以改为不同的值），有多少种方案使这个数列是一个幸运的数列。

定义一个数列为幸运的数列，当且仅当对于所有 1≤i≤n−11\le i\le n-1，数对 (ai,ai+1)(a_i,a_{i+1}) 是幸运的，用一个 3×33\times 3 的矩阵 ww 来表示幸运的数对，当 wi,j=1w_{i,j}=1 时，表示数对 (i,j)(i,j) 是幸运的，反之则表示它不是幸运的。

答案对 777777777777777777 取模。

思路

这道题其实就是大力线段树乱搞就行了，毕竟 nn 才到 7777777777（那为什么分块会 T 啊喂）。

显然，我们只关心那些所有元素都为 00 的区间（为了方便，下面都称之为 00 区间），而这些区间彼此又是无关的，也就是说，这个 00 区间选的变换方案是什么，跟那个 00 区间选的变换方案是什么并没有什么卵关系，因此在询问时，我们只需要将每个 00 区间的方案总数乘起来就行了，这一部分可以直接 DP 预处理，用 fi,j,lenf_{i,j,len} 表示一段长度为 lenlen，开头选择数字 ii，结尾选择数字 jj 的 00 区间的方案总数，那么状态转移方程显然如下：

fi,j,len=∑k=13fi,k,len−1(ak,j=1)f_{i,j,len}=\sum\limits^3_{k=1} f_{i,k,len-1} (a_{k,j}=1)

这个状态转移方程可以视为是在 fi,k,len−1f_{i,k,len-1} 的结尾再加上一个数 jj，由于必须满足 ak,j=1a_{k,j}=1，那么显然加上 jj 之后的数列仍是一个幸运的数列。

显然如果每次都暴力把所有 00 区间扫一遍，复杂度为 O(nm)O(nm)，略微用脚趾一算就知道过不了，所以我们考虑用数据结构去维护。

那么什么数据结构能维护这样一种东西，同时时间复杂度还很优秀呢。

肯定是万能的线段树啊。

我们用每个节点表示这个区间内的答案是多少，然后在 pushup 的时候将两个儿子的答案乘起来，但由于每个区间两端的 00 区间的长度并不明确，所以我们在计算这个节点的答案时并不能把这部分算进去，而应该在 pushup 时进行合并。

如上图，我们在计算左儿子的答案时，只计算前两个 00 区间，也就是 [2,2][2,2] 和 [5,6][5,6] 的答案，而右儿子则直接不计算，因为它并没有一个完整的 00 区间。

在 pushup 时，我们先把左儿子的答案乘上右儿子的答案，然后再计算它们中间夹的那个 00 区间的答案，这样上面那个节点的答案就是 [2,2][2,2]，[5,6][5,6] 和 [8,13][8,13] 三个 00 区间的答案的乘积。

还有一点需要注意，如果这个数列中本来就有不幸运的数对，比如说我们定义幸运的数对有 (1,2)(1,2)，(2,3)(2,3)，但我们却把一个数列修改成了 1,3,0,0,21,3,0,0,2 这样，那么不论那些 00 怎么变，都不会有幸运的数列产生，此时则应输出 00，对应到线段树上，我们发现其实只需要在 pushup 的时候，判断左右儿子最边上的两个数（设为 xx 和 yy）是否非零，且 (x,y)(x,y) 不是一个幸运的数对就行了，如果出现这种情况，就直接把这个节点的答案变成 00（其他时候默认都为 11），这样在算的时候答案就一定为 00 了。

在查询的时候，我们只需要对根节点进行计算，先找到它记录的答案，再统计它左右两边没有被算进这个节点的答案的 00 区间的方案数，最后乘起来就行了，不过这里还要特判，如果整个序列都为 00 的话，就需要特殊计算。

具体的看一下代码吧。

参考代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
#include <bits/stdc++.h>
#define judge(x) (tree[x].lz == tree[x].r-tree[x].l+1)//拿来判断这个节点的区间里的数是否全为 0
using namespace std;
namespace IO
{
	char buf[1<<23],*p1=buf,*p2=buf;
	#define getchar() (p1==p2&&(p2=(p1=buf)+fread(buf,1,1<<21,stdin),p1==p2)?EOF:*p1++)
	#define isdigit(c) (c>=48&&c<=57)
	#define isalpha(c) ((c>=65&&c<=90)||(c>=97&&c<=122))
	template<typename T> inline void read(T &x)
	{
		x=0;
		register char ch=getchar();
		while(!isdigit(ch))
			ch=getchar();
		while(isdigit(ch))
		{
			x=(x<<1)+(x<<3)+(ch^48);
			ch=getchar();
		}
	}
	template <typename T,typename... Args> inline void read(T& t, Args&... args)
	{
		read(t);read(args...);
	}
}
using namespace IO;
typedef long long ll;
const int N = 8e4+10, inf = 0x3f3f3f3f, mod = 777777777;
struct SegTree
{
	int l;//表示区间的左端点
	int r;//表示区间的右端点
	int lz;//靠着左边的 0 区间的长度
	int rz;//靠着右边的 0 区间的长度
	int ln;//左边第一个不为 0 的数
	int rn;//右边第一个不为 0 的数
	ll dat;//这个区间里除开左右两端其他 0 区间的答案乘积（也就是这个区间的答案）
};
SegTree tree[N<<2];
int n, m, a[10][10];
ll f[N][10][10];
inline void push_up(int i)
{
	tree[i].lz = tree[i<<1].lz;
	tree[i].rz = tree[i<<1|1].rz;
	tree[i].ln = tree[i<<1].ln;
	tree[i].rn = tree[i<<1|1].rn;//这四句显然，不再解释
	if(judge(i<<1) && judge(i<<1|1))//如果左右儿子的区间都是 0 区间
	{
		tree[i].lz = tree[i].rz = tree[i].r-tree[i].l+1;
		tree[i].dat = 1;
	}
	if(judge(i<<1) && !judge(i<<1|1))//如果左儿子的区间是 0 区间，右儿子的不是
	{
		tree[i].lz += tree[i<<1|1].lz;
		tree[i].ln = tree[i<<1|1].ln;
		tree[i].dat = tree[i<<1|1].dat;
	}
	if(!judge(i<<1) && judge(i<<1|1))//如果左儿子的区间不是 0 区间，右儿子的是
	{
		tree[i].rz += tree[i<<1].rz;
		tree[i].rn = tree[i<<1].rn;
		tree[i].dat = tree[i<<1].dat;
	}
	if(!judge(i<<1) && !judge(i<<1|1))//如果两个儿子的区间都不是 0 区间
	{
		tree[i].dat = tree[i<<1].dat*tree[i<<1|1].dat%mod;
		if(tree[i<<1].rz || tree[i<<1|1].lz)//单独统计两个儿子中间夹的那个 0 区间
		{
			ll t = 0;
			for(int j = 1; j <= 3; j++)
				for(int k = 1; k <= 3; k++)
					if(a[tree[i<<1].rn][j] && a[k][tree[i<<1|1].ln])
						t = (t+f[tree[i<<1].rz+tree[i<<1|1].lz][j][k])%mod;
			tree[i].dat = tree[i].dat*t%mod;
		}
	}
	if(!tree[i<<1].rz && !tree[i<<1|1].lz && !a[tree[i<<1].rn][tree[i<<1|1].ln])//判断是否有不合法的数对
		tree[i].dat = 0;
}
void build(int i, int l, int r)
{
	tree[i].l = l;
	tree[i].r = r;
	tree[i].lz = tree[i].rz = r-l+1;
	tree[i].dat = 1;
	if(l == r)
		return;
	int mid = (l+r)>>1;
	build(i<<1, l, mid);
	build(i<<1|1, mid+1, r);
}
void update(int i, int x, int k)
{
	if(tree[i].l == tree[i].r)//显然，不做解释
	{
		if(k)
			tree[i].lz = tree[i].rz = 0;
		else
			tree[i].lz = tree[i].rz = 1;
		tree[i].ln = tree[i].rn = k;
		return;
	}
	if(tree[i<<1].r >= x)
		update(i<<1, x, k);
	else
		update(i<<1|1, x, k);
	push_up(i);
}
ll query()
{
	if(tree[1].lz == n)//判断是否整个数列的数都为 0
	{
		ll t = 0;
		for(int i = 1; i <= 3; i++)
			for(int j = 1; j <= 3; j++)
				t = (t+f[n][i][j])%mod;
		return t;
	}
	ll ans = tree[1].dat;
	if(tree[1].lz)//左边的 0 区间
	{
		ll t = 0;
		for(int i = 1; i <= 3; i++)
			for(int j = 1; j <= 3; j++)
				if(a[j][tree[1].ln])
					t = (t+f[tree[1].lz][i][j])%mod;
		ans = ans*t%mod;
	}
	if(tree[1].rz)//右边的 0 区间
	{
		ll t = 0;
		for(int i = 1; i <= 3; i++)
			for(int j = 1; j <= 3; j++)
				if(a[tree[1].rn][i])
					t = (t+f[tree[1].rz][i][j])%mod;
		ans = ans*t%mod;
	}
	return ans;
}
signed main()
{
	read(n, m);
	for(int i = 1; i <= 3; i++)
		for(int j = 1; j <= 3; j++)
			read(a[i][j]);
	f[1][1][1] = f[1][2][2] = f[1][3][3] = 1;
	for(int i = 2; i <= n; i++)//DP 预处理，上面解释过了
		for(int j = 1; j <= 3; j++)
			for(int k = 1; k <= 3; k++)
				for(int l = 1; l <= 3; l++)
					if(a[l][k])
						f[i][j][k] = (f[i][j][k]+f[i-1][j][l])%mod;
	build(1, 1, n);
	for(int i = 1; i <= m; i++)
	{
		int v;
		ll t;
		read(v, t);
		update(1, v, t);
		printf("%lld\n", query());
	}
	return 0;
}

所以为什么分块过不了啊喂。