BZOJ3764 Petya 的序列

由于某种莫名其妙的原因一定要把这道题调完。。。

设幸运数字的个数为 \(s\) 。

这个题目一共就没几个切入点，所以要么在每个幸运数字上做手脚，要么就枚举端点然后优化。

然后你套路地枚举最左边的端点，记为 \(l\) ，算出这样每个合法的区间总数是多少。

然后不知道怎么做，枚举左边区间的第二个端点 \(r\) ，这样 \(r\) 右边不能在第二个区间中取到的地方就把后面的地方分成了若干个区间，他们组成的长度可重集合为 \(L = \{l_1, l_2, \cdots, l_k\}\) ，那么对于这样的一个区间 \([l, r]\) ，答案就是 \(\sum_i S(l_i)\) ，其中 \(S(k) = \frac{k\times (k + 1)}{2}\) 。

这样正着做就是把一个大区间分裂，不好维护（实际上是可以的），然后你先算 \([l, n]\) 的区间方案，然后将 \(r : n\rightarrow l\) 这样枚举，算出每个答案。

这样原来的分裂就变成了合并，用并查集维护每个区间，每次合并的时候减去原来的两段 \(S(P_1)\) 和 \(S(P_2)\)，再加上新合成的 \(S(P_1 + P_2)\) 。

这样就 \(\mathcal O (n ^ 2)\) 了。

记每一个左端点的答案为 \(suf_l\) 。

然后你发现，对于一个是幸运数字的位置 \(s_k\) ，对于 \(pos \in [s_{k - 1}, s_k - 1]\) 这段的 \(suf_{pos}\) ，看起来很好算，然后真的很好算，就是 \(suf_{s_k} + \sum_{t\in [pos + 1, s_k]} S(n - t)\) 。

这样就做到 \(\mathcal O (n\times s)\) 。

这个时候复杂度瓶颈在求 \(suf\) 上，然后你把不是幸运数字的极长连续段缩成一点，然后这一部分答案也很好算，对于一段不是长为 \(l_o\) 的空段，若右边有合法段长为 \(K\) ，那么对于 \(suf_l\) 的贡献就是 \((now - S(K))\times l_o + \sum_{t\in (K, K + l_o]} S(t)\) 。

这样就 \(\mathcal O (s ^ 2)\) 了。

#include 
#define forn(i,s,t) for(int i = (s); i <= (t); ++i)
#define form(i,s,t) for(int i = (s); i >= (t); --i)
#define rep(i,s,t) for(int i = (s); i < (t); ++i)
using namespace std;
typedef long long i64;
const int N = 3e5 + 5;
int n, s, num[N]; i64 res, a[N], rft[N]; bool vis[N], vet[N]; vector P[N];
namespace BF {
	int ton[122]; i64 Sf[132];
	inline void solve() {
		forn (l1, 1, n) forn (r1, l1, n) {
			forn (k, l1, r1) if (!vis[k]) ton[a[k]] ++ ;
			forn (l2, r1 + 1, n) forn (r2, l2, n) {
				bool fl = 0; 
				forn (o, l2, r2) if (!vis[o] && ton[a[o]]) { fl = 1; break ; }
				if (!fl) { res ++ , Sf[l1] ++ ; }
			}
			forn (k, l1, r1) if (!vis[k]) ton[a[k]] -- ;
		}
		forn (i, 1, n) if (!vis[i]) cout << Sf[i] << " \n"[i == n];
					   else cout << 0 << " \n"[i == n];
		cout << res << '\n';
	}
}
i64 suf[N], Pre[N]; int fa[N], val[N];
int fnd(int u) { return fa[u] == u ? u : fa[u] = fnd(fa[u]); }
inline void mrg(int u, int v) {
	u = fnd(u), v = fnd(v);
	if (u == v) return ;
	val[v] += val[u], fa[u] = v;
}
inline i64 S(i64 k) { return k * (k + 1) >> 1; }
namespace SUB1 {
	inline void solve() {
		forn (i, 1, n) Pre[i] = Pre[i - 1] + 1ll * i * (i + 1) / 2;
		forn (l, 1, n) { // 算贡献的时候没判断是否已经相连。。。
			if (!vis[l]) {
				forn (i, 1, n) fa[i] = i, val[i] = 1, vet[i] = 0;
				forn (r, l, n) num[a[r]] ++ ;
				i64 now = 0; 
				form (r, n, l + 1) {
					--num[a[r]];
					if (vis[r]) {
						now ++ , vet[r] = 1;
						if (fnd(r) != fnd(r - 1) && vet[r - 1]) now -= S(val[fnd(r - 1)]) + S(val[fnd(r)]), mrg(r, r - 1), now += S(val[fnd(r)]);
						if (fnd(r) != fnd(r + 1) && vet[r + 1]) now -= S(val[fnd(r + 1)]) + S(val[fnd(r)]), mrg(r, r + 1), now += S(val[fnd(r)]);
					}
					if (!vis[r] && (!num[a[r]])) {
						for (const int& v : P[a[r]]) if (v > l) now ++ , vet[v] = 1;
						for (const int& v : P[a[r]]) if (v > l) {
							if (fnd(v) != fnd(v - 1) && vet[v - 1]) now -= S(val[fnd(v - 1)]) + S(val[fnd(v)]), mrg(v, v - 1), now += S(val[fnd(v)]);
							if (fnd(v) != fnd(v + 1) && vet[v + 1]) now -= S(val[fnd(v + 1)]) + S(val[fnd(v)]), mrg(v, v + 1), now += S(val[fnd(v)]);
						}
					}
					suf[l] += now;
				}
				--num[a[l]];
			}
		}
		int lst = 0;
		forn (i, 1, n) {
			if (!vis[i]) res += suf[i] * (i - lst), lst = i;
			res += S(n - i) * (i - lst);
		}
		cout << res << '\n';
	}
}
namespace SUB2 {
	int Lop[N], rot[N], nom[N], bol[N << 1];
	inline void solve() {
		forn (i, 1, n) Pre[i] = Pre[i - 1] + 1ll * i * (i + 1) / 2;
		int lst = 0; s = 0;
		forn (i, 1, n) if (!vis[i]) {
			if (i - lst - 1 == 0) Lop[i] = s, rot[s] = i, nom[s] = 1, ++s, lst = i;
			else Lop[i] = ++s, rot[s] = i, nom[s] = 1, nom[s - 1] = i - lst - 1, ++s, lst = i;
		}
		if (lst != n) nom[s] = n - lst;
		else s--;
		forn (l, 1, n) {
			if (!vis[l]) {
				forn (i, 1, s) fa[i] = i, val[i] = nom[i], vet[i] = 0;
				forn (r, Lop[l], s) if (rot[r]) num[a[rot[r]]] ++ ;
				i64 now = 0; 
				form (r, s, Lop[l] + 1) {
					if (rot[r]) --num[a[rot[r]]];
					if (rot[r]) {
						if (!num[a[rot[r]]]) {
							for (const int& v : P[a[rot[r]]]) if (v > l) now ++ , vet[Lop[v]] = 1;
							for (int v : P[a[rot[r]]]) if (v > l) {
								v = Lop[v];
								if (fnd(v) != fnd(v - 1) && vet[v - 1]) now -= S(val[fnd(v - 1)]) + S(val[fnd(v)]), mrg(v, v - 1), now += S(val[fnd(v)]);
								if (fnd(v) != fnd(v + 1) && vet[v + 1]) now -= S(val[fnd(v + 1)]) + S(val[fnd(v)]), mrg(v, v + 1), now += S(val[fnd(v)]);
							}
						}
						suf[l] += now;
					} else {
						i64 tmpx(0), tmpy(0);
						if (vet[r + 1]) tmpx = S(val[fnd(r + 1)]);
						suf[l] += (now - tmpx) * nom[r];
						if (vet[r + 1]) tmpx = val[fnd(r + 1)];
						now += S(val[r]), vet[r] = 1;
						if (fnd(r) != fnd(r - 1) && vet[r - 1]) now -= S(val[fnd(r - 1)]) + S(val[fnd(r)]), mrg(r, r - 1), now += S(val[fnd(r)]);
						if (fnd(r) != fnd(r + 1) && vet[r + 1]) now -= S(val[fnd(r + 1)]) + S(val[fnd(r)]), mrg(r, r + 1), now += S(val[fnd(r)]);
						tmpy = val[fnd(r)];
						suf[l] += Pre[tmpy] - Pre[max(tmpx, 0ll)];
					}
				}
				num[a[l]] -- ;
			}
		}
		lst = 0;
		forn (i, 1, n) {
			if (!vis[i]) res += suf[i] * (i - lst), lst = i;
			res += S(n - i) * (i - lst);
		}
		cout << res << '\n';
	}
}
int main() {
	ios::sync_with_stdio(false);
	cin.tie(0), cout.tie(0);
	cin >> n;
	forn (i, 1, n) {
		cin >> a[i]; int x = a[i];
		if (a[i] == 0) vis[i] = 1;
		else {
			while (x) vis[i] |= (x % 10 != 4 && x % 10 != 7), x /= 10;
		}
		if (!vis[i]) ++s;
		rft[i] = a[i];
	}
//	forn (i, 1, n) cout << vis[i] << " \n"[i == n];
	sort (rft + 1, rft + n + 1);
	int m = unique(rft + 1, rft + n + 1) - rft - 1;
	forn (i, 1, n) a[i] = lower_bound(rft + 1, rft + m + 1, a[i]) - rft , P[a[i]].push_back(i);
//	BF :: solve();
	if (s <= 0) SUB1 :: solve();
	else SUB2 :: solve();
	return 0;
}
/*
5
7 9 2 8 7
*/