题解 CF1392I Kevin and Grid

题目链接

考虑这个权值很小，可以转化为对连通块的计数问题。而对于一张平面图，我们熟知「欧拉定理」：

[|V|-|E|+|F|=chi + 2 ]

下记 (V_b,V_w) 为两种颜色的顶点个数，(E_b,E_w) 为边数，(F_b,F_w) 为面数。记不在边界上的连通块个数为 (N_b,N_w)，在的为 (B_b,B_w)。

于是欧拉定理可以表述为：

[left{ egin{aligned} & V_b-E_b+F_b=N_b+B_b+2\ & V_w-E_w+F_w=N_w+B_w+2 end{aligned} ight. ]

要求的答案为

[2N_b-2N_w+B_b-B_w ]

于是我们还需要 (N_b-N_w) 的值。考虑一个不经过边界的连通块一定被一个异色的面包围着，而所有异色的面，除去 (1 imes 1) 的小正方形的情况，也都一定包含一个本色的不经过边界的连通块。

于是记小正方形的个数为 (S_b,S_w)，那么有：

[left{ egin{aligned} & N_b=F_w-S_w\ & N_w=F_b-S_b end{aligned} ight. ]

于是对柿子进行化简，得到最终的答案为

[ans=(V_b-E_b+S_b)-(V_w-E_w+S_w) ]

这三个东西都是容易用 NTT 预处理出来的。总复杂度 (mathcal O(nlog n))，常数巨大。

#include<cmath>
#include<cstdio>
#include<algorithm>

typedef long long ll;
const int maxn = 4E+5 + 5;

namespace Poly {
	typedef std::vector<ll> poly;
	const double PI = acos(-1);

	struct comp {
		double r, i;
		inline comp(double _r = 0, double _i = 0) : r(_r), i(_i) {}
		
		inline comp conj() { return comp(r, -i); }
		inline comp operator+(const comp &x) { return comp(r + x.r, i + x.i); }
		inline comp operator-(const comp &x) { return comp(r - x.r, i - x.i); }
		inline comp operator*(const comp &x) { return comp(r * x.r - i * x.i, r * x.i + i * x.r); }
		inline comp operator/(double x) { return comp(r / x, i / x); }
	} I(0, 1);

	int rev[maxn << 2]; comp rt[maxn << 2];
	inline void FFTpre(int bit) {
		int N = 1 << bit;
		for(int i = 0; i < N; ++i)
			rev[i] = (rev[i >> 1] >> 1 | (i & 1) << bit - 1);

		for(int len = 1; len < N; len <<= 1) {
			rt[len] = 1;
			for(int j = 1; j < len; ++j)
				rt[len + j] = comp(cos(PI * j / len), sin(PI * j / len));
		}
	}

	inline void FFT(comp *f, int bit, int op) {
		int N = 1 << bit;
		for(int i = 0; i < N; ++i)
			if(i < rev[i]) std::swap(f[i], f[rev[i]]);

		for(int len = 1; len < N; len <<= 1) {
			for(int i = 0; i < N; i += len << 1) {
				for(int k = i, x = len; k < i + len; ++k, ++x) {
					comp g = f[k], h = f[k + len] * rt[x];
					f[k] = g + h, f[k + len] = g - h;
				}
			}
		}

		if(op == -1) {
			std::reverse(f + 1, f + N);
			for(int i = 0; i < N; ++i) f[i] = f[i] / N;
		}
	}
	
	comp P[maxn << 2];
	inline poly mul(const poly &F, const poly &G) {
		int N = 1, bit = 0;
		while(N < F.size() + G.size()) N <<= 1, ++bit;

		FFTpre(bit);
		for(int i = 0; i < F.size(); ++i) P[i] = comp(F[i], G[i]);
		for(int i = F.size(); i < N; ++i) P[i] = comp(0, 0);
		
		FFT(P, bit, 1);
		for(int i = 0; i < N; ++i) P[i] = P[i] * P[i];
		FFT(P, bit, -1);
		
		poly res(N);
		for(int i = 0; i < N; ++i) res[i] = ll(P[i].i / 2 + 0.5);
		
		res.resize(F.size() + G.size() - 1); return res;
	}
}
using Poly::poly;
using Poly::mul;

int n, m, q;
int a[maxn], b[maxn];

ll ans1[maxn], ans2[maxn];

int main() {
	scanf("%d%d%d", &n, &m, &q);
	for(int i = 1; i <= n; ++i) scanf("%d", &a[i]);
	for(int j = 1; j <= m; ++j) scanf("%d", &b[j]);
	
	static const int V = 2E+5;
	
	poly F, G; F.resize(V / 2 + 1), G.resize(V / 2 + 1);
	for(int i = 1; i <= n; ++i) ++F[a[i]];
	for(int i = 1; i <= m; ++i) ++G[b[i]];
	F = G = mul(F, G);
	
	for(int i = 1; i <= V; ++i) F[i] += F[i - 1];
	for(int i = V - 1; i >= 0; --i) G[i] += G[i + 1];
	for(int i = 1; i <= V; ++i) ans1[i] += F[i], ans2[i] += G[i];
	
	F.clear(), F.resize(V / 2 + 1);
	G.clear(), G.resize(V / 2 + 1);
	for(int i = 2; i <= n; ++i) ++F[std::max(a[i - 1], a[i])];
	for(int j = 1; j <= m; ++j) ++G[b[j]];
	F = mul(F, G);
	
	for(int i = 1; i <= V; ++i) F[i] += F[i - 1];
	for(int i = 1; i <= V; ++i) ans1[i] -= F[i];
	
	F.clear(), F.resize(V / 2 + 1);
	G.clear(), G.resize(V / 2 + 1);
	for(int i = 2; i <= m; ++i) ++F[std::max(b[i - 1], b[i])];
	for(int j = 1; j <= n; ++j) ++G[a[j]];
	F = mul(F, G);
	
	for(int i = 1; i <= V; ++i) F[i] += F[i - 1];
	for(int i = 1; i <= V; ++i) ans1[i] -= F[i];
	
	F.clear(), F.resize(V / 2 + 1);
	G.clear(), G.resize(V / 2 + 1);
	for(int i = 2; i <= n; ++i) ++F[std::min(a[i - 1], a[i])];
	for(int j = 1; j <= m; ++j) ++G[b[j]];
	F = mul(F, G);
	
	for(int i = V - 1; i >= 0; --i) F[i] += F[i + 1];
	for(int i = 1; i <= V; ++i) ans2[i] -= F[i];
	
	F.clear(), F.resize(V / 2 + 1);
	G.clear(), G.resize(V / 2 + 1);
	for(int i = 2; i <= m; ++i) ++F[std::min(b[i - 1], b[i])];
	for(int j = 1; j <= n; ++j) ++G[a[j]];
	F = mul(F, G);
	
	for(int i = V - 1; i >= 0; --i) F[i] += F[i + 1];
	for(int i = 1; i <= V; ++i) ans2[i] -= F[i];
	
	F.clear(), F.resize(V / 2 + 1);
	G.clear(), G.resize(V / 2 + 1);
	for(int i = 2; i <= n; ++i) ++F[std::max(a[i - 1], a[i])];
	for(int j = 2; j <= m; ++j) ++G[std::max(b[j - 1], b[j])];
	F = mul(F, G);
	
	for(int i = 1; i <= V; ++i) F[i] += F[i - 1];
	for(int i = 1; i <= V; ++i) ans1[i] += F[i];
	
	F.clear(), F.resize(V / 2 + 1);
	G.clear(), G.resize(V / 2 + 1);
	for(int i = 2; i <= n; ++i) ++F[std::min(a[i - 1], a[i])];
	for(int j = 2; j <= m; ++j) ++G[std::min(b[j - 1], b[j])];
	F = mul(F, G);
	
	for(int i = V - 1; i >= 0; --i) F[i] += F[i + 1];
	for(int i = 1; i <= V; ++i) ans2[i] += F[i];
	
	while(q --> 0) {
		int x; scanf("%d", &x);
		printf("%lld
", ans2[x] - ans1[x - 1]);
	}
}