#P4914. [Sdoi2017]文本校正

    ID: 2307 传统题 1000ms 512MiB 尝试: 240 已通过: 11 难度: 10 上传者: 标签>难度分类省选/NOI-字符串KMPZ 算法border 链构造与建模复制数组处理环回文树series link 优化动态规划线性 DP枚举与搜索路径恢复数据结构哈希表CF2900

[Sdoi2017]文本校正

[SDOI2017] 文本校正

题目描述

小Q在研发一种数据混淆的算法时不慎将重要的文档都给混淆了。幸运的是,将这些文档校正对于他来说并不是难事。他凭借着敏锐的观察力成功地用肉眼完成了校正。

为了防止这种情况再次发生,小Q希望开发一种文本校正工具,他的目标是将一个文本串TT分成连续的33段,要求每段都不能为空,然后按一定顺序将这33段从左往右拼接起来,将其还原为初始文本串SS。

在进行了大量肉眼校正工作之后,小Q需要休息一下,因此他把这个任务交给了你。请写一个程序,判断是否可以还原,并给出一个合法的还原方案。

输入格式

第一行包含一个正整数CaseCase,表示需要进行的校正次数。

接下来CaseCase个部分依次表示每次校正工作,每个部分第一行包含两个正整数nn,mm,分别表示文本串的长度以及字符集的大小。

每个部分第二行包含nn个正整数S1,S2,…,SnS_1,S_2,\dots ,S_n,表示SS串。

每个部分第三行包含nn个正整数T1,T2,…,TnT_1,T_2,\dots ,T_n,表示TT串。

输出格式

对于每次校正工作,若无解,则仅输出一行"NO"(不含引号),否则第一行输出"YES"(不含引号),接下来三行每行两个正整数lil_i,rir_i,按拼接顺序依次表示 TT 的三个子串。下标从 11 开始,区间两端都包含,满足 1≤li≤ri≤n1\le l_i\le r_i\le n。三个区间必须互不重叠,而且合起来覆盖整个 TT。

若存在多种还原方案,请输出任意一种。

样例 #1

样例输入 #1

3
5 3
2 1 1 1 1
1 1 1 1 2
5 5
5 2 3 3 4
2 5 3 4 3
5 5
4 5 2 1 4
5 4 2 1 4

样例输出 #1

YES
5 5
1 3
4 4
NO
YES
2 2
1 1
3 5

数据范围

对于100%100\%的数据,3≤n≤10000003 \leq n \leq 1000000,1≤Si,Ti≤m≤10000001 \leq S_i,T_i \leq m \leq 1000000。

测试点 单组 n,mn,m 上界 CaseCase 上界 ∑n,∑m\sum n,\sum m 各自的上界
1–2 66 5000050000 300000300000
3–6 20002000 1010 2000020000
7–12 200000200000 3030 200000200000
13–20 10000001000000 10000001000000