原题传送门
第一道黑题祭！
拿到这一题有些人啪的一下就输出无解，很快啊！
但是这作为一道构造题，无脑骗分是很容易被偷袭的。
大胆猜(kou)想(hu)：一定有解，且一定存在连续子序列的解。
接下来尝试证明。
令 A_i 表示 a_n 的前缀和，B_i 表示 b_n 的前缀和。
不失一般性，我们假设 A_n ≤ B_n 。对于 0 ≤ i ≤ n ，我们定义 j 是满足 A_i ≥ B_j 的最大整数，显然 j < n。
由于 A_n ≤ B_n ，则 A_i ≤ B_j + b_{j+1} ，故 0 ≤ A_i - B_j < n。
由鸽笼原理，一定存在 $i_1 \not= i_2$，满足 $A_{i_1}$ - $B_{j_1}$ = $A_{i_2}$ - $B_{j_2}$ 。
同样不失一般性假定 $i_1 > i_2$，那么 $A_{i_1}$ - $A_{i_2}$ = $B_{j_1}$ - $B_{j_2}$。则连续子序列
{$a_{i_2+1}$, · · · , $a_{i_1}$} 和 {$b_{j_2+1}$, · · · , $b_{j_1}$} 就是一个合法的方案。
两个数列中分别找到子序列起点和终点，对于子序列的值开个桶记录一下即可，值域从 $1$ 到 $\text{n}$ 。
时间复杂度 $\text{O(n)}$ 。
---
## Code
```cpp
#include <cstdio>
#include <iostream>
using namespace std;
const int N=1e6+10;
int n,l[N][2],la,lb,ra,rb;
long long a[N],b[N];
bool modify,cnt[N];
void swap(int &x,int &y) {x^=y^=x^=y; return ;}
int main()
{
// freopen("work.in","r",stdin); freopen("work.out","w",stdout);
scanf("%d",&n);
for(int i=1;i<=n;i++) {scanf("%lld",&a[i]); a[i]+=a[i-1];}
for(int i=1;i<=n;i++) {scanf("%lld",&b[i]); b[i]+=b[i-1];}
if(a[n] > b[n]) {modify=true; for(int i=1;i<=n;i++) swap(a[i],b[i]);}//不失一般性
for(int i=0,j=0;i<=n;i++)
{
for(;a[i]>=b[j] && j<=n;j++); j--;//移动j的位置
if(cnt[a[i]-b[j]]) {la=l[a[i]-b[j]][0]+1; lb=l[a[i]-b[j]][1]+1; ra=i; rb=j; break;}//找到答案
l[a[i]-b[j]][0]=i; l[a[i]-b[j]][1]=j;//记录
cnt[a[i]-b[j]]=true;//这个值已经搞出来
}
if(modify) {swap(la,lb); swap(ra,rb);}
printf("%d\n",ra-la+1);
for(int i=la;i<=ra;i++) printf("%d ",i);
printf("\n%d\n",rb-lb+1);
for(int i=lb;i<=rb;i++) printf("%d ",i);
// fclose(stdin); fclose(stdout);
return 0;
}
```
这里解释一下为什么需要 $\text{cnt}$ 数组而不能直接`l[a[i]-b[j]][0]`判断是否在桶中已经存在值。
例如这种数据。
```
10
9 9 9 9 9 9 9 9 9 9
10 10 10 10 10 10 10 10 10 10
```
数列从第一项开始，而此时桶中会存下 $\text{0}$ ，而这个 $\text{0}$ 是有效数据。
## $\text{Thank you for your reading!}
您的点赞和评论是对作者最大的支持！