CodeForces 1562D Two Hundred Twenty One

pufanyi

发布于：Aug 28, 2021

给定一个长度为 $n$ 的字符串表示一个序列 $a_i$ ，字符串中只有 '+'、'-'，第 $i$ 个字符为 '+' 表示 $a_i = 1$ ，为 '-' 表示 $a_i = -1$ 。 $q$ 组询问，每组询问给定两个整数 $l, r\,(1\le l\le r\le n)$ ，将 $a_{l\sim r}$ 单独取出后，求最少删除多少个数字，使得所成长度为 $m$ 的序列 $\left\{b_{i}\right\}$ 满足 $\sum_{i=1}^m(-1)^{i-1}b_i=0$ 。

D1 仅要求出最少删除多少个数字，D2 需要求出删除哪些数字（多解输出任意一组即可）。

$T$ 组数据， $1\le T\le 10^3, 1\le n, q\le 3\cdot 10^5$ 。

先考虑没有多组询问。

窝萌首先发现一个性质，那就是如果有两个连续的相同字符，那么这两个字符对答案无贡献，我们可以直接删掉。那我们一次删掉之后，最后得到的序列只能是正负交替的了。于是我们只要考虑此种情况即可。我们发现如果删完的序列长度为奇数的话，我们只要删除最中间那个数就可以了。我们考虑偶数，如果长度已经为 $0$ ，那显然就不用删除了，如果不为 $0$ 的话，考虑到们此相同字符消除一定是两个两个删的，所以至少要删两个数，有考虑到如果随便删一个数，那么序列长度就变成奇数了，所以我们只需要删两个数即可。

于是我们发现，如果是询问系列长度为奇数，那答案最多是 $1$ ，如果是偶数，我们可以维护前缀和 $S_i=\sum_{j=1}^i(-1)^{j-1}a_j$ ，如果 $S_r-S_{l-1}$ 是 $0$ ，那答案就是 $0$ ，否则是 $2$ 。

这样 D1 就做完了。

我们考虑 D2，我们先考虑奇数的情况，我们假设要删掉的数是第 $k$ 个，那我们有 $\sum_{i=l}^{k - 1}(-1)^{i-1}a_{i}+(-1)\cdot\sum_{i=k+1}^r(-1)^{i-1}a_i=0$ 也即 $S_{k-1}-S_{l-1}=S_{r}-S_{k}$ 也即 $S_{k-1}+S_k=S_{l-1}+S_r$ ，于是我们对每个 $S_{k-1}+S_k$ 相同的开个 set，之后对每组询问 $\left<l,r\right>$ ，我们只要在所有 $S_{k-1}+S_k=S_{l-1}+S_r$ 数中 lower_bound 出一个在 $[l,r]$ 中的答案即可。

长度为偶数就直接随便删掉最左边或是最右边的数，然后按照奇数的方法做即可。

const int maxn = 300005;

int qzh[maxn];
char s[maxn];

void solve() {
  int n, q;
  scanf("%d%d%s", &n, &q, s + 1);
  std::map<int, std::set<int>> mp;
  for (int i = 1; i <= n; ++i) {
    qzh[i] = qzh[i - 1] + (((i & 1) == (s[i] == '+')) ? 1 : -1);
    mp[qzh[i - 1] + qzh[i]].insert(i);
  }
  while (q--) {
    int l, r;
    scanf("%d%d", &l, &r);
    if (qzh[r] - qzh[l - 1]) {
      if ((r - l) & 1) {
        puts("2");
        writesp(r);
        r--;
      } else {
        puts("1");
      }
      writeln(*mp[qzh[l - 1] + qzh[r]].lower_bound(l));
    } else {
      puts("0");
    }
  }
}

int main() {
  int T;
  scanf("%d", &T);
  while (T--) {
    solve();
  }
  return 0;
}