牛客小白月赛61 F.选座椅(双指针)

牛客小白月赛61 F.选座椅(双指针)

显然 ( l , r ) (l,r) (l,r)满足 ( l , r + 1 ) (l,r+1) (l,r+1)满足。

那么可以考虑双指针，枚举 l l l，然后计算贡献是一段区间，使用BIT实现区间加。维护满足的种类个数即可。

最后乘上 l e n ! len! len!就是答案。

时间复杂度： O ( n + m ) O(n+m) O(n+m)

#include <bits/stdc++.h>
using namespace std;const int M = (int)1e5;
const int mod = (int)1e9 + 7;int n, m;
vector<int> v[M + 5];
int t[M + 5], tot;
int d[M + 5];void work()
{scanf("%d %d", &n, &m);for(int _ = 0; _ < 3; ++_)for(int i = 1, a; i <= m; ++i) {scanf("%d", &a);v[a].push_back(i);}auto add = [&](int p) {for(const int& x: v[p])if(++t[x] == 1)++tot;};auto del = [&](int p) {for(const int &x: v[p])if(--t[x] == 0)--tot;};for(int l = 1, r = 0; l <= n; ++l) {while(r + 1 <= n && tot < m) add(++r);if(tot == m) ++d[r - l + 1], --d[n - l + 2];del(l);}for(int i = 1, fac = 1; i <= n; ++i) {fac = (long long)fac * i % mod;d[i] += d[i - 1];printf("%lld%c", (long long)fac * d[i] % mod, " \n"[i == n]);}
}int main()
{work();return 0;
}