Description：

给两个集合，每个数都在 $1\sim n$ 范围内，求两个子集使得权值和相等。

$1\leqslant n\leqslant 10^6$

Solution：

构造题，肯定是利用鸽笼原理，假设 $Sa_n\leqslant Sb_n$ ，那么对于每个 $i$ 找到第一个 $Sa_i\leqslant Sb_j$ 的位置，那么 $Sb_j-Sa_i\in[0,n-1]$ ，有 $n$ 种取值，这样的前缀有 $n+1$ 个（算上 $i=0$ ），那么一定能找到 $Sb_{j_1}-Sa_{i_1}=Sb_{j_2}-Sa_{i_2}$ ，那么之间的部分就是答案。

Code：

#include<algorithm>

#include<iostream>

#include<cstdlib>

#include<cstdio>

#include<cmath>

#include<cstring>

using namespace std;

int n;

#define MAXN 1000010

int a[MAXN],b[MAXN];

long long sa[MAXN],sb[MAXN];

int p[MAXN];

int ans[2][2];

int main()

{

	scanf("%d",&n);

	for(int i = 1;i <= n;++i)

	{

		scanf("%d",&a[i]);

		sa[i] = sa[i - 1] + a[i];

	}

	for(int i = 1;i <= n;++i)

	{

		scanf("%d",&b[i]);

		sb[i] = sb[i - 1] + b[i];

	}

	bool tag = false;

	if(sa[n] > sb[n])

	{

		tag = true;

		swap(a,b);

		swap(sa,sb);

	}

	memset(p,-1,sizeof(p));

	for(int i = 0;i <= n;++i)

	{

		int pb = lower_bound(sb,sb + 1 + n,sa[i]) - sb;

		if(p[sb[pb] - sa[i]] != -1)

		{

			ans[0][0] = p[sb[pb] - sa[i]];ans[0][1] = i;

			ans[1][0] = lower_bound(sb,sb + 1 + n,sa[ans[0][0]]) - sb;

			ans[1][1] = pb;

			break;

		}

		p[sb[pb] - sa[i]] = i;

	}

	if(tag)

	{

		swap(ans[0][0],ans[1][0]);swap(ans[0][1],ans[1][1]);

		swap(a,b);

	}

	cout << ans[0][1] - ans[0][0] << endl;

	for(int i = ans[0][0] + 1;i <= ans[0][1];++i)cout << i << " ";cout << endl;

	cout << ans[1][1] - ans[1][0] << endl;

	for(int i = ans[1][0] + 1;i <= ans[1][1];++i)cout << i << " ";cout << endl;

	return 0;

}