【CSP-S刷题班】Day3

A

题目描述

可持久化是OI比赛中的一个常规考点，部分毒瘤的出题人可能会将一个问题强行加上可持久化

在本题中，你需要维护一个可持久化的数组，具体的，你有一个长度为 nn 的数组 a1,a2,...,ana_1,a_2,...,a_n，你需要在这个数组上进行 mm 次修改或询问，修改或询问的具体内容如下：

  1. 1 u v，将 aua_u 的值修改为 vv
  2. 2 u t，询问 aua_u 在第 tt 次操作后的值是多少

为了防止选手通过离线方式通过此题，本题部分测试点设置了强制在线，详见输入格式

输入格式

第一行三个整数 n,m,optn,m,opt

第二行 nn 个整数，第 ii 个整数表示 aia_i

接下来 mm 行，每行三个整数 1,ui,vi1,u_i,v_i 或 2,ui,ti2,u_i,t_i，表示一次操作或询问。

本题部分测试点设置强制在线，如果 opt=1opt=1，那么每次操作的 ui,vi,tiu_i,v_i,t_i 需要异或（C++中的xor或^运算）上 lstanslstans，其中 lstanslstans 表示上一次询问的答案，如果没有上一次询问则 lstans=0lstans=0。

输出格式

对于每次询问输出一行一个整数，表示答案

样例

样例 1 输入
1
2
3
4
5
6
7
5 5 0
8 3 4 6 7
1 2 5
2 2 0
2 2 1
1 5 5
2 5 3
样例 1 输出
1
2
3
3
5
7
样例 2 输入
1
2
3
4
5
6
7
5 5 1
8 3 4 6 7
1 2 5
2 2 0
2 1 2
1 0 0
2 0 6
样例 2 输出
1
2
3
3
5
7

子任务

子任务名 评分方式 时间限制 内存限制 说明 分数
默认子任务 求和 1000 ms 512 MB 共 10 个测试点 100

提示

对于 20%20\% 的数据，保证 n,m≤1000n,m \leq 1000

对于 40%40\% 的数据，保证 n,m≤10000n,m \leq 10000

对于 70%70\% 的数据，保证 opt=0opt=0

对于所有数据，1≤n,m≤300000,1≤ui≤n,0≤ai,vi≤109,1≤ti≤i1 \leq n,m \leq 300000,1 \leq u_i \leq n,0 \leq a_i,v_i \leq 10^9,1 \leq t_i \leq i

思路

可持久化数组，引用一下老师的话就是说，这个是专门用浪费只打板子的同学的时间的，然而我正巧不会使用可持久化数组，所以我就直接想了一个暴力

暴力开数组，三十万肯定开不下，因为要持久化，所以要开的是一个二维数组，但是我们真地用得到这个二维数组的所有空间吗，并不是每个时候每个位置的数据是改变的，所以我们只用存这个数据出现的最后位置就可以了，或者说这个数据出现的第一个位置，这样我们就想着用vector这个动态数组来储存每个数据和每个数据的位置，然后针对时间，在这个存储数据的时间点的数组上二分，这样就可以做出来这道题目

PS：竟然和我在考场上想出来的标程一毛一样，恩恩，但是我代码炸了

std

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
#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cstring>
#include <string>
#include <vector>
using namespace std;
const int maxn=300005;
vector <int> val[maxn],tv[maxn];
int n,q;
int flag,lastans=0;
int main()
{
	freopen("array.in","r",stdin);
	freopen("array.out","w",stdout);
	cin>>n>>q>>flag;
	for(int i=1;i<=n;i++)
	{
		int v;
		cin>>v;
		val[i].push_back(v);
		tv[i].push_back(0);
	}
	for(int t=1;t<=q;t++)
	{
		int op,a,b;
		cin>>op>>a>>b;
		if(flag) 
		a^=lastans,b^=lastans;
		if(op==1)
		{
			val[a].push_back(b);
			tv[a].push_back(t);
		}
		else if(op==2)
		{
			int l=0,r=val[a].size()-1;
			int pos=0;
			while(l<=r)
			{
				int mid=(l+r)>>1;
				if(tv[a][mid]<=b)
				pos=mid,l=mid+1;
				else
				r=mid-1;
			}
			lastans=val[a][pos];
			cout<<lastans<<'\n';
		}
	}
	return 0;
}

B

题目描述

给定一棵 nn 个节点 n−1n-1 条带权边的树

我们定义树上一个点集 AA 的权值为：初始时所有边均没有被标记过，将 AA 中每个节点到根节点 11 的路径上所有边全部标记一遍，最终所有被标记过的边的权值和为点集 AA 的权值

现在你有一个大小为 kk 的点集 XX，你需要对 XX 的所有子集 YY，求出 YY 的权值，由于输出量可能很大，你只需要求出所有 YY 的权值的按位异或（C++中的xor或^运算）和即可

输入格式

第一行两个整数 n,kn,k

接下来 n−1n-1 行，每行三个整数 ai,bi,cia_i,b_i,c_i 分别表示一条边连接的两个节点和这条边的边权

最后一行 kk 个整数，表示点集 XX 中的节点

输出格式

一行一个整数，表示答案

样例

样例 1 输入
1
2
3
4
5
4 2
1 2 3
2 3 5
2 4 7
3 4
样例 1 输出
1
13

子任务

子任务名 评分方式 时间限制 内存限制 说明 分数
默认子任务 求和 1000 ms 512 MB 共 10 个测试点 100

提示

空集的权值为 00

点集 {3}\{3\} 的权值为 88

点集 {4}\{4\} 的权值为 1010

点集 {3,4}\{3,4\} 的权值为 1515

四个数的xor和为 1313

对于测试点 11，k=1k=1

对于测试点 2,32,3，n≤1000,k≤10n \leq 1000,k \leq 10

对于测试点 4,5,6,74,5,6,7，k≤16k \leq 16

对于测试点 88，k≤20k \leq 20

对于测试点 99，k≤22k \leq 22

对于测试点 1010，k≤24k \leq 24

对于所有测试点，n≤300000,1≤ai,bi≤n,0≤ci≤109n \leq 300000,1 \leq a_i,b_i \le n,0 \leq c_i \leq 10^9

思路

首先最先想到的是暴力枚举集合，然后遍历整个集合求解答案，时间复杂度 O(2k×n)O(2^k \times n)

我们发现实际上并不需要遍历整棵树，如果是两棵结点的话，我们可以用个树上前缀和，然后在求一个lca来玩

但是这样并不行，然而老师用到了我之前一直懒得去学的树链剖分lca，发现代码异常地简单

我们将集合中的点 xix_i 按照他们在树上的 dfsdfs 序进行排序，记录结点 ii 到根节点的距离为 disidis_i，那么这个集合的答案为：
∑i=1kdisxi+∑i=2kdislca(xi−1,xi) \sum_{i=1}^k dis_{x_i}+ \sum_{i=2}^k dis_{lca(x_{i-1},x_i)}
当然，树链剖分lca的速度还是比较快的，但是也没有快到哪里去，和倍增lca实际上差不多，也是O(logn)O(logn)的

加上枚举集合的复杂度，时间复杂度就是O(2k×klogn)O(2^k \times k logn)

我们还可以进一步优化

我们在一开始的时候就可以将 kk 个点按照 dfsdfs 序进行排序

因为需要可能求解的lca的点对只有 k2k^2​ 个，所以我们可以先预处理出来他们的lca然后我们就可以快速求解

因为我们一开始就已经使用了 O(logn)O(logn) 的复杂度，但是由于后面的复杂度会更大，所以我们就把复杂度优化到了O(xk)O(x^k) 足以通过此题

std

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
#include<bits/stdc++.h>
using namespace std;
const int maxn=300100;
int head[maxn],nxt[maxn<<1],ver[maxn<<1],val[maxn<<1],tot;
inline void addedge(int a,int b,int c)
{
	nxt[++tot]=head[a];ver[tot]=b;val[tot]=c;head[a]=tot;
	nxt[++tot]=head[b];ver[tot]=a;val[tot]=c;head[b]=tot;
}
int fa[maxn],dep[maxn],size[maxn],hson[maxn];
long long sumv[maxn];
inline void dfs1(int x,int fat)
{
	fa[x]=fat;dep[x]=dep[fat]+1;
	size[x]=1;int mxsize=0;
	for(int i=head[x];i;i=nxt[i])
	{
		int y=ver[i];if(y==fat) continue;
		sumv[y]=sumv[x]+val[i];dfs1(y,x);
		if(size[y]>mxsize) hson[x]=y,mxsize=size[y];
	}
}
int id[maxn],idtot,top[maxn];
inline void dfs2(int x,int Top)
{
	id[x]=++idtot;top[x]=Top;
	if(hson[x]) dfs2(hson[x],Top);
	for(int i=head[x];i;i=nxt[i])
	{
		int y=ver[i];if(y==fa[x]||y==hson[x]) continue;
		dfs2(y,y);
	}
}
inline int lca(int x,int y)
{
	while(top[x]^top[y])
	{
		if(dep[top[x]]<dep[top[y]]) swap(x,y);
		x=fa[top[x]];
	}
	if(dep[x]>dep[y]) return y;else return x;
}
long long calv[30][30],ans;
int v[30],n,m;
inline int cmp(int a,int b){return id[a]<id[b];}
inline void dfs(int x,int lst,long long now)
{
	if(x>m) {ans^=now;return;}
	dfs(x+1,lst,now);
	dfs(x+1,x,now+calv[lst][x]);
}
int main()
{
	freopen("tree.in","r",stdin);
	freopen("tree.out","w",stdout);
	scanf("%d%d",&n,&m);
	for(int i=1,a,b,c;i<n;i++) scanf("%d%d%d",&a,&b,&c),addedge(a,b,c);
	dfs1(1,0);dfs2(1,1);
	for(int i=1;i<=m;i++) scanf("%d",v+i);
	sort(v+1,v+m+1,cmp);
	for(int i=1;i<=m;i++) calv[0][i]=sumv[v[i]];
	for(int i=1;i<=m;i++) for(int j=i+1;j<=m;j++) calv[i][j]=sumv[v[j]]-sumv[lca(v[i],v[j])];
	dfs(1,0,0);printf("%lld\n",ans);cerr<<ans<<endl;return 0;
}

C

题目描述

从题目名称不难看出，本题与括号序列有很强的关系

给定一个仅包含 () 的长度为 nn 的字符串 ss，你需要求出下面式子的值：

∑1≤l≤r≤nf(l,r)∗3l∗5r−l+1\sum_{1 \leq l \leq r \leq n} f(l,r)*3^l*5^{r-l+1}

其中 f(l,r)f(l,r) 的值当 sl..rs_{l..r} 为合法的括号序列时为 11，否则 f(l,r)=0f(l,r)=0

由于答案可能很大，你只需要输出答案对 998244353998244353 取模的值即可

合法的括号序列定义如下：

  1. 空串是合法的括号序列
  2. 如果 A 是合法的括号序列，那么 (A) 是合法的括号序列
  3. 如果 A 与 B 是合法的括号序列，那么 AB 是合法的括号序列

输入格式

第一行一个正整数 nn

第二行一个长度为 nn 的字符串 ss

输出格式

一行一个整数，表示答案

样例

样例 1 输入
1
2
5
)(())
样例 1 输出
1
6300
样例 2 输入
1
2
8
)(()()))
样例 2 输出
1
164250

子任务

子任务名 评分方式 时间限制 内存限制 说明 分数
默认子任务 求和 2000 ms 512 MB 共 10 个测试点 100

提示

对于 20%20\% 的数据，n≤300n \leq 300

对于 50%50\% 的数据，n≤5000n \leq 5000

对于另 30%30\% 的数据，ss 是一个合法的括号序列

对于所有数据，1≤n≤3000001 \leq n \leq 300000

思路

首先瓶颈在于，我们要判断一个括号序列是否合法

我们记录
ai={1si=′(′−1si=′=)′ a_i= \begin{cases}1 &s_i ='(' \\ -1 &s_i ='=)' \end{cases}
然后记录
sumi=∑j=1iai sum_i=\sum_{j=1}^i a_i
不难发现一个括号序列 sl..rs_{l..r} 合法，首先满足 sumi−1=sumrsum_{i-1}=sum_r

如果只有上面这个条件还是不够的，结合暴力判断的过程，我们还可以发现还需要判断 mini=lrsumi≥suml−1min_{i=l}^r sum_i \geq sum_{l-1}​是否成立；如果不成立的话，括号序列就不合法

两个条件同时满足我们就能判断这是一个括号序列了

明确了怎么判断一个括号序列的合法性之后，我们就对于每一个左端点 ll 然后通过判断确定一个 pospos 满足 pos≥lpos \ge l 并且 sumpos+1<suml−1sum_{pos+1<sum_{l-1}} 的最小整数或者 nn 这样右端点选择 [l.pos][l.pos]​ 之间的数字就一定可以，满足合法括号序列，寻找这个位置可以用ST表预处理，然后二分pos来解决

然后我们考虑另外一个条件 suml−1=sumrsum_{l-1}=sum_r ,只需要对于每个不同的值 tt 预处理一个 vector，储存所有的 sumi=tsum_i=t和 5i5^i的值就可以了，然后区间询问的时候直接在vector上面直接求区间和就可以了

时间复杂度 O(nlogn)O(nlog n)

std

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
#include<bits/stdc++.h>
using namespace std;
const int maxn=300100,mod=998244353,A=3,B=5;
inline void Add(int &a,int b)
{
	a=a+b>=mod?a+b-mod:a+b;
}
inline int ksm(int a,int b)
{
	int res=1;
	for(;b;b>>=1,a=1ll*a*a%mod) 
	if(b&1) 
	res=1ll*res*a%mod;
	return res;
}
int n,f[maxn][20],Log2[maxn],ans=0;
inline int query(int L,int R) 
{
	int t=Log2[R-L+1];
	return min(f[L][t],f[R-(1<<t)+1][t]);
}
char s[maxn];
vector<int> pos[maxn<<1],val[maxn<<1];
int main()
{
	freopen("bracket.in","r",stdin);
	freopen("bracket.out","w",stdout);
	scanf("%d%s",&n,s+1);
	for(int i=1;i<=n;i++) 
	f[i][0]=f[i-1][0]+(s[i]=='('?1:-1);
	for(int j=1;j<20;j++) 
	for(int i=1;i+(1<<j)-1<=n;i++) 
	f[i][j]=min(f[i][j-1],f[i+(1<<(j-1))][j-1]);
	for(int i=2;i<=n;i++) 
	Log2[i]=Log2[i>>1]+1;
	for(int i=0;i<=2*n;i++) 
	pos[i].push_back(0),val[i].push_back(0);
	for(int i=1;i<=n;i++) 
	pos[f[i][0]+n].push_back(i),val[f[i][0]+n].push_back(ksm(B,i));
	for(int i=0;i<=2*n;i++) 
	for(int j=1;j<(int)val[i].size();j++) 
	Add(val[i][j],val[i][j-1]);
	for(int i=1;i<=n;i++)
	{
		int L=i,R=n,res=i-1,V=f[i-1][0];
		while(L<=R)
		{
			int mid=(L+R)>>1;
			if(query(i,mid)<V) R=mid-1;
			else res=mid,L=mid+1;
		}
		if(res<i) continue;
		int lpos=lower_bound(pos[V+n].begin(),pos[V+n].end(),i)-pos[V+n].begin();
		int rpos=upper_bound(pos[V+n].begin(),pos[V+n].end(),res)-pos[V+n].begin()-1;
		int calv=1ll*(val[V+n][rpos]-val[V+n][lpos-1]+mod)%mod*ksm(ksm(B,mod-2),i-1)%mod;
		Add(ans,1ll*calv*ksm(A,i)%mod);
	}
	printf("%d\n",ans);
	cerr<<ans<<endl;
}

D

题目描述

在win7电脑上，一些同学在无聊时会玩小工具中的 4∗44*4 拼图，在本题中，你需要解决与之类似的 n∗mn*m 的拼图。

给定一个 n∗mn*m 的拼图板，其中 n∗m−1n*m-1 个位置分别有写着数字 1,2,...,n∗m−11,2,...,n*m-1 的方块，剩下的一个位置是空位，用数字 00 表示。不难发现，还原win7小工具中的 4∗44*4 拼图需要用到的操作可以简化为以下形式，在本题中，你只能够进行以下的操作，下面记空格所在位置为 (x,y)(x,y)（下标从 11 开始），所有操作的前提为操作描述中的坐标不超过 n∗mn*m 拼图板的范围：

  1. D 操作，将 (x+1,y)(x+1,y) 中的数字移到 (x,y)(x,y)，移动完毕后空位位于 (x+1,y)(x+1,y)
  2. U 操作，将 (x−1,y)(x-1,y) 中的数字移到 (x,y)(x,y)，移动完毕后空位位于 (x−1,y)(x-1,y)
  3. R 操作，将 (x,y+1)(x,y+1) 中的数字移到 (x,y)(x,y)，移动完毕后空位位于 (x,y+1)(x,y+1)
  4. L 操作，将 (x,y−1)(x,y-1) 中的数字移到 (x,y)(x,y)，移动完毕后空位位于 (x,y−1)(x,y-1)

通过上述操作，你可以将这个拼图的状态进行一些改变，你需要在 50000005000000 步内将拼图还原到最终状态，或者判断这个拼图无解。与同学们所熟知的最终状态类似，在本题的最终状态中，(i,j)(i,j) 的数字为 (i−1)∗m+j(i-1)*m+j，特别的，(n,m)(n,m) 为空位。

注意：你并不需要最小化步数

输入格式

第一行两个整数 n,mn,m

接下来 nn 行，每行 mm 个整数 ai,ja_{i,j}，表示拼图板的初始状态

输出格式

如果拼图无解，输出一行一个字符串 NO，否则输出一行一个字符串 YES 并按照下述说明完成输出。

由于本题输出量可能很大，输出需要经过特殊处理，请选手直接使用下图的代码输出，其中函数的参数 ss 是一个仅包含 UDRL 字符的 答案字符串，表示你的操作序列。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
inline void print(const string &s) {
	printf("%d\n",(int)s.size());
	for(int i=0;i<(int)s.size();i+=30) {
		long long x=0;
		for(int j=i;j<i+30&&j<(int)s.size();j++) {
			long long v=-1;
			if(s[j]=='D') v=0;
			if(s[j]=='U') v=1;
			if(s[j]=='R') v=2;
			if(s[j]=='L') v=3;
			assert(v>=0&&v<4);
			x|=v<<((j-i)*2);
		}
		printf("%lld\n",x);
	}
}

样例

样例 1 输入
1
2
3
4
3 3
1 0 3
4 5 6
7 8 2
样例 1 输出
1
2
3
YES
11
2152898
样例 2 输入
1
2
3
4
3 3
1 0 3
4 5 6
7 2 8
样例 2 输出
1
NO

子任务

子任务名 评分方式 时间限制 内存限制 说明 分数
默认子任务 求和 1000 ms 512 MB 共 10 个测试点 100

提示

样例1的操作序列为 RDDLURULDDR

对于测试点 1,21,2，n,m≤3n,m \leq 3

对于测试点 3,43,4，n,m≤4n,m \leq 4

对于测试点 5,6,75,6,7，n=2n = 2

对于测试点 8,98,9，n,m≤50n,m \leq 50

对于所有测试点，2≤n,m≤1002 \leq n,m \leq 100

思路

首先考虑如何将一个数字在较为开阔的地方向四个方向移动

只需要将空位移动到它的上下左右，然后直接移动这个数字就可以了

不难发现 2∗n2*n 的巨型足够开阔，使得一个数字能够通过上面的方式不断地移动到任何位置

然后现在考虑如何一次归位一对数，以1,6为例首先我们可以将6移动到左上角，然后把移动到左上角右边的位置，然后空位置跑到左下角，执行 URL 就可以了

但是上面的做法有一些问题，如果运气特别不好的话，当6移动的左上角的时候恰好在左下角，这个时候不移动6的话1就不能移动出来了

所以我们要对这种情况进行特判

可以通过给出一组解的方式来证明，在这个特判中，将1，6互换位置至少且仅仅需要3列，即1,6所在的列，以及这列右边的两列

得出这一组解可以利用实战经验得出，在 2∗32*3 的矩形里面跑暴力搜索，大概需要20步

在最后的 2∗22*2 操作里面，只能简单地将数字顺时针或者逆时针旋转，如果不能将这一部分还原的话，是因为逆序对的奇偶性，这个时候就不存在解

到现在，我们解决了 2∗n2*n 的情况

现在是 n∗mn*m 的情形

由于空出来了2行2列，我们保证除去已经归位的数字之后，剩下的区域足够开阔

因此我们可以把 (n−2)∗(m−2)(n-2)*(m-2) 的矩形轻松地归位

最后的两行去掉最右下角的 2∗22*2 和 2∗n2*n 的情形是等价的，最后两列也是同理的

最后剩下来的 2∗22*2 如果无法还原的话，仍然因为逆序对奇偶性的原因无解

总次数是 O(n∗m∗(n+m))O(n*m*(n+m)) ，不考虑常数的话这也是这道题目使用次数的一个下界，将矩形上下左右分别反转就能得到了

这道题目可能的做法比较多，但是这种做法相对来说实现难度比较低，在考场上可实现性高

std

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
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
#include<bits/stdc++.h>
using namespace std;
inline int Abs(int x){return x<0?-x:x;}
const int dx[]={1,-1,0,0},dy[]={0,0,1,-1};
const int D=0,U=1,R=2,L=3;
const char dv[]={'D','U','R','L'};
const int maxn=310;
string ans;
int n,m,a[maxn][maxn],posx[maxn*maxn],posy[maxn*maxn];
int ex,ey;
void print(){
	for(int i=1;i<=n;i++) {
		for(int j=1;j<=m;j++) printf("%d ",a[i][j]);
		putchar('\n');
	}
}
inline void Move(int v)
{
	ans+=dv[v];
	swap(a[ex][ey],a[ex+dx[v]][ey+dy[v]]);
	posx[a[ex][ey]]=ex;posy[a[ex][ey]]=ey;
	ex+=dx[v];ey+=dy[v];
}
int flg[maxn][maxn],lstv[maxn][maxn],qx[20],qy[20],he,ta,tmpv[20],tmpc;
inline void Moveto(int tx,int ty,int ox,int oy,int limx,int limy)
{
	if(ex<=tx&&ey>=ty) {
		while(ex<tx) {
			if(max(Abs(ey-oy),Abs(ex-ox))==1) break;
			Move(0);
		}
		while(ex>tx) {
			if(max(Abs(ey-oy),Abs(ex-ox))==1) break;
			Move(1);
		}
	}
	while(ey>ty) {
		if(max(Abs(ey-oy),Abs(ex-ox))==1) break;
		Move(3);
	}
	while(ey<ty) {
		if(max(Abs(ey-oy),Abs(ex-ox))==1) break;
		Move(2);
	}
	if(!(ex<tx&&ey>ty)) {
		while(ex<tx) {
			if(max(Abs(ey-oy),Abs(ex-ox))==1) break;
			Move(0);
		}
		while(ex>tx) {
			if(max(Abs(ey-oy),Abs(ex-ox))==1) break;
			Move(1);
		}
	}
	int lx=max(1,ox-1),rx=min(n,ox+1),ly=max(1,oy-1),ry=min(m,oy+1);
	for(int i=lx;i<=rx;i++) for(int j=ly;j<=ry;j++)
	{
		flg[i][j]=1;lstv[i][j]=0;
		if(i==ox&&j==oy) flg[i][j]=0;
		if((i<limx||(i==limx&&j<limy))&&j<=m-2) flg[i][j]=0;
	}
	he=1;ta=1;qx[1]=ex;qy[1]=ey;lstv[ex][ey]=-1;
	while(he<=ta)
	{
		int x=qx[he],y=qy[he];he++;
		for(int i=0;i<4;i++) {
			int nx=x+dx[i],ny=y+dy[i];
			if(nx<lx||nx>rx||ny<ly||ny>ry) continue;
			if(lstv[nx][ny]||flg[nx][ny]==0) continue;
			lstv[nx][ny]=i+1;
			qx[++ta]=nx;qy[ta]=ny;
		}
	}
/*	puts("--------");
	for(int i=lx;i<=rx;i++)
	{
		for(int j=ly;j<=ry;j++) cout<<flg[i][j]<<' ';
		putchar('\n');
	}
	cout<<ox<<' '<<oy<<' '<<tx<<' '<<ty<<' '<<ex<<' '<<ey<<endl;*/
	assert(lstv[tx][ty]);tmpc=0;
	int nx=tx,ny=ty;
	while(nx!=ex||ny!=ey) {
		tmpv[++tmpc]=lstv[nx][ny]-1;
		nx-=dx[tmpv[tmpc]];
		ny-=dy[tmpv[tmpc]];
	}
	reverse(tmpv+1,tmpv+tmpc+1);
	for(int i=1;i<=tmpc;i++) Move(tmpv[i]);
}
inline void print(const string &s) {
	printf("%d\n",(int)s.size());
	for(int i=0;i<(int)s.size();i+=30) {
		long long x=0;
		for(int j=i;j<i+30&&j<(int)s.size();j++) {
			long long v=-1;
			if(s[j]=='D') v=0;
			if(s[j]=='U') v=1;
			if(s[j]=='R') v=2;
			if(s[j]=='L') v=3;
			assert(v>=0&&v<4);
			x|=v<<((j-i)*2);
		}
		printf("%lld\n",x);
	}
}
int main()
{
	freopen("puzzle.in","r",stdin);
	freopen("puzzle.out","w",stdout);
	scanf("%d%d",&n,&m);
	for(int i=1;i<=n;i++) for(int j=1;j<=m;j++)
	{
		scanf("%d",&a[i][j]);
		if(a[i][j]==0) ex=i,ey=j;
		else posx[a[i][j]]=i;posy[a[i][j]]=j;
	}
	for(int i=1;i<=n-2;i++) for(int j=1;j<=m-2;j++)
	{
		int val=(i-1)*m+j,vx=posx[val],vy=posy[val];
		if(vx<=i) {
			while(vx<i) {
				Moveto(vx+1,vy,vx,vy,i,j);
				Move(1);vx++;
			}
			while(vy>j) {
				Moveto(vx,vy-1,vx,vy,i,j);
				Move(2);vy--;
			}
			continue;
		}
		while(vy<j) {
			Moveto(vx,vy+1,vx,vy,i,j);
			Move(3);vy++;
		}
		while(vy>j) {
			Moveto(vx,vy-1,vx,vy,i,j);
			Move(2);vy--;
		}
		while(vx>i) {
			Moveto(vx-1,vy,vx,vy,i,j);
			Move(0);vx--;
		}
	}
	for(int i=1;i<=n-2;i++) {
		int vl=i*m-1,vr=i*m,vx=posx[vl],vy=posy[vl];
		while(vy<m) {
			Moveto(vx,vy+1,vx,vy,n-2,m-2);
			Move(3);vy++;
		}
		while(vx>i) {
			Moveto(vx-1,vy,vx,vy,n-2,m-2);
			Move(0);vx--;
		} 
		if(a[i][m-1]==0) Move(0);
	//	if(a[i][m-1]==vr) cout<<"fjdlsjkfdsl "<<i<<endl;
		if(a[i][m-1]==vr) {
			Moveto(i+1,m,i,m,n-2,m-2);
			Move(U);Move(L);Move(D);Move(D);
			Move(R);Move(U);Move(U);Move(L);
			Move(D);Move(R);Move(U);Move(L);
			Move(D);Move(D);Move(R);Move(U);
			Move(L);Move(D);Move(R);Move(U);
			Move(U);Move(L);Move(D);
			continue;
		}
		vx=posx[vr],vy=posy[vr];
		while(vy<m) {
			Moveto(vx,vy+1,vx,vy,n-2,m-2);
			Move(3);vy++;
		}
		while(vx>i+1) {
			Moveto(vx-1,vy,vx,vy,n-2,m-2);
			Move(0);vx--;
		}
		Moveto(i+2,m-1,i+1,m,n-2,m-2);
		Move(1);Move(1);Move(2);Move(0);
	}
	for(int j=1;j<=m-2;j++)
	{
		int vu=(n-2)*m+j,vd=(n-1)*m+j,vx=posx[vd],vy=posy[vd];
		while(vx>n-1) {
			Moveto(vx-1,vy,vx,vy,n-2,m);
			Move(0);vx--;
		}
		while(vy>j) {
			Moveto(vx,vy-1,vx,vy,n-2,m);
			Move(2);vy--;
		}
		if(a[n][j]==0) Move(R);
		if(a[n][j]==vu) {
			Moveto(n-1,j+1,n-1,j,n-2,m);
			Move(L);Move(D);Move(R);Move(R);
			Move(U);Move(L);Move(L);Move(D);
			Move(R);Move(U);Move(L);Move(D);
			Move(R);Move(R);Move(U);Move(L);
			Move(D);Move(R);Move(U);Move(L);
			Move(L);Move(D);Move(R);
			continue;
		}
		vx=posx[vu],vy=posy[vu];
		while(vx>n-1) {
			Moveto(vx-1,vy,vx,vy,n-2,m);
			Move(0);vx--;
		}
		while(vy>j+1) {
			Moveto(vx,vy-1,vx,vy,n-2,m);
			Move(2);vy--;
		}
		Moveto(n,j+2,n-1,j+1,n-2,m);
		Move(L);Move(L);Move(U);Move(R);
	}
	if(ex<n) Move(D);
	if(ey<m) Move(R);
	int flag=0;
	for(int i=1;i<=3;i++) {
		if(a[n-1][m-1]==(n-1)*m-1&&a[n-1][m]==(n-1)*m) {flag=1;break;}
		Move(U);Move(L);Move(D);Move(R);
	}
	if(flag==0) puts("NO");else puts("YES");
	if(flag) print(ans);
//	cout<<ans.size()<<endl;
	if(flag) for(int i=1;i<=n;i++) for(int j=1;j<=m;j++) {
		if(i==n&&j==m) assert(a[i][j]==0);
		else assert(a[i][j]==(i-1)*m+j);
	}
//	cout<<ans<<endl;
}