如何将差分改写为长尾？

本文共计481个文字，预计阅读时间需要2分钟。

这是一道模拟题。题目描述：给定大小为N的两个数组A和B，求长度为1~M的满足以下条件的连续序列数量：对于每个i（从1到N），ai和bi至少有一个是偶数。

This is a fake summary.

题目传送门：E - At Least One (atcoder.jp)

题意：

给定大小为N的两个数组A，B，求长度分别为1~M的满足以下条件的连续序列数量，条件为：

对于每个i（从1~N），Ai和Bi至少有一个包含于此序列之内。

思路：双指针 + 差分

容易知道，当序列[L, R]是满足条件的连续序列时，则左边界向左拓展，右边界向右拓展时，得到的新序列依旧满足条件。

那么我们枚举左边界L，然后移动右边界，使得其为满足条件的最小右边界（记为Rmin），则长度在[Rmin - L + 1, M - L + 1]之间的答案都增加1，可以用双指针+差分实现。

代码参考：

//Jakon; Two Pointers and Difference
#include <bits/stdc++.h> using namespace std; const int N = 200010; int n, m, cnt[N], ans[N]; vector<int> v[N]; int main() { cin >> n >> m; for(int i = 1; i <= n; i++) { int a, b; scanf("%d%d", &a, &b); v[a].push_back(i), v[b].push_back(i); } int sum = 0; for(int i = 1, j = 0; i <= m && j <= m; i++) { //以i为左边界，找到满足条件的最小右边界j while(sum < n && j < m) { ++ j; for(auto& idx : v[j]) { ++ cnt[idx]; if(cnt[idx] == 1) ++ sum; } } //若区间[i, j]满足条件，则长度在[j-i+1, m-i+1]的答案都+1，即以i为左边界的所有可能情况都+1 if(sum == n && j <= m) { ++ ans[j - i + 1], -- ans[m - i + 2]; } //左边界i要右移一位，于是先把原本i的贡献去掉 for(auto& idx : v[i]) { -- cnt[idx]; if(cnt[idx] == 0) -- sum; } } for(int i = 1; i <= m; i++) cout << (ans[i] += ans[i - 1]) << " "; cout << endl; return 0; }