[YT2sOJ1404]多重集[鸽巢原理]

首先进行一个处理：若a的元素和大于b的元素和，则交换序列 a 和 b

令 A 表示序列a的前缀和数组 Ｂ表示序列b的前缀和数组 对于A中的每个元素 \(A_i\) ，B中一定存在 \(B_j\) 满足 \(B_j \geq A_i\)，我们找到最小的满足条件的 \(B_j\), 又因为值域在 \([1..n]\) 内，所以 \(0\leq A_i-B_{j-1}< n\)

ll prea[MAXN], preb[MAXN];
pii g[MAXN], emp;
void solve() {
  int n = in;
  lop1(i, n) prea[i] = prea[i - 1] + int(in);
  lop1(i, n) preb[i] = preb[i - 1] + int(in);
  bool flag = 0;
  if (prea[n] > preb[n]) swap(prea, preb), flag = 1;
  lop0(i, n + 1) {
    int v = upper_bound(preb, preb + 1 + n, prea[i]) - 1 - preb;
    if (g[prea[i] - preb[v]] != emp) {
      int l = g[prea[i] - preb[v]].fi, L = g[prea[i] - preb[v]].se, r = i, R = v;
      if (flag) swap(l, L), swap(r, R);
      out, r - l, '\n';
      lop(i, l + 1, r) out, i, ' ';
      puts("");
      out, R - L, '\n';
      lop(i, L + 1, R) out, i, ' ';
      return ;
    }
    g[prea[i] - preb[v]] = {i, v};
  }
}

[YT2sOJ1404]多重集[鸽巢原理]

原文：https://www.cnblogs.com/storz/p/10423305.html