无限大的网格，第 $0$ 秒有 $n$ 个点燃烧，每一秒正燃烧的点会使与其八连通的点燃烧，每个点的权值为其最早燃烧的时间，求 $t$ 秒后的权值和。
$1 \le n \le 2000,1 \le t \le 10^8,-10^8 \le x,y \le 10^8$。
记 $f_i$ 为 $i$ 秒后燃烧格子的数量，那么答案为
$f_i$ 可用扫描线 $O(n\log n)$ 求解，可以求出所有 $f_i$ 代入上式获得答案，时间复杂度 $O(tn \log n)$。
由于每秒矩形都会扩大 $1$，并且所有矩形的大小相等，那么猜测 $f_i$ 与 $i$ 成某个简单的函数关系。矩形并的轮廓线的大小即为 $f_i$ 的增大量，发现轮廓线的大小成等差数列。准确来说，当矩形的相交关系不变时，$f_i$ 为关于 $i$ 的二次函数。总共有 $O(n^2)$ 种两两相交，它们将时间分成了 $O(n^2)$ 段，每段中 $f_i$ 的函数表达式不变。那么求出三个 $f_i$ 就可以得到本段中 $f_i$ 之和。时间复杂度 $O(n^3\log n)$。本方法足以通过 CF 原题。
发现矩形的交是好求的，考虑容斥，记 $g_{S,i}$ 为集合 $S$ 中的初始点在 $i$ 秒后形成矩形的交的大小，那么答案为
记 $dx,dy$ $S$ 中的点横纵坐标差的极大值，那么
通过推式子，$(-1)^{|S|+1}(tg_{S,t} - \sum_{i=0}^{t-1} g_{S,i})$ 可以 $O(1)$ 求解，记为 $G_S$。
进一步观察，若 $S$ 中存在一个点 $x$ 使得删去这个点后横纵坐标差的极大值不变，那么 $G_{S} + G_{S \setminus \{x\}} = 0$（符号相反），那么合法的 $S$ 大大减少，事实上只有 $O(n^2)$ 个。
将节点按横坐标排序，枚举 $i < j$ 框定横坐标差的极大值。需要判断 $(i,j)$ 中是否存在点的纵坐标在 $i,j$ 纵坐标内，如果存在那么包含 $i,j$ 的集合都不合法，否则将 $G_{\{i,j\}}$ 计入答案，并找到 $(i,j)$ 中 $i,j$ 纵坐标的前驱/后继，枚举它们是否计入 $S$ 计入答案。用 set 实现，时间复杂度 $O(n^2\log n)$。用链表实现可以做到 $O(n^2)$。
有一个细节是对于横/纵坐标相等的点，发现怎样钦定它们的顺序都是对的。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
| #include<bits/stdc++.h>
using namespace std;
#define ar(x) array<int,x>
const int N=2e3+100,INF=1e9,MOD=998244353,inv3=332748118;
inline void mod(int &x){ if(x>=MOD) x-=MOD; if(x<0) x+=MOD; }
inline int qm(int x,int y=MOD-2){ int res=1; for(;y;y>>=1,x=1ll*x*x%MOD) if(y&1) res=1ll*res*x%MOD; return res; }
#define gc getchar()
#define rd read()
inline int read(){
int x=0,f=0; char c=gc;
for(;c<'0'||c>'9';c=gc) f|=(c=='-');
for(;c>='0'&&c<='9';c=gc) x=(x<<1)+(x<<3)+(c^48);
return f?-x:x;
}
int n,t,ans=0; ar(2) a[N]; set<int> s;
int f(int x,int y,int i){ return 1ll*max(0,(2*i-x+1))*max(0,(2*i-y+1))%MOD; }
int S1(int x){ return 1ll*x*(x+1)/2%MOD; }
int S2(int x){ return 1ll*x*(x+1)/2%MOD*(2*x+1)%MOD*inv3%MOD; }
int calc(int x,int y){
int res=1ll*t*f(x,y,t)%MOD,l=(max(x,y)+1)/2,r=t-1;
if(l>r) return res;
mod(res-=4ll*(S2(r)-S2(l-1))%MOD);
mod(res+=2ll*(x-1+y-1)*(S1(r)-S1(l-1))%MOD);
mod(res-=1ll*(x-1)*(y-1)%MOD*(r-l+1)%MOD);
return res;
}
void solve(int i,int j){
int dx=a[j][0]-a[i][0],p=INF,q=INF;
if(a[i][1]>a[j][1]) swap(i,j);
auto it1=s.upper_bound(a[j][1]);
auto it2=s.lower_bound(a[i][1]);
if(it1!=it2) return;
mod(ans-=calc(dx,a[j][1]-a[i][1]));
if(it1!=s.end()) mod(ans+=calc(dx,*it1-a[i][1])),p=*it1;
if(it2!=s.begin()) --it2,mod(ans+=calc(dx,a[j][1]-*it2)),q=*it2;
if(p!=INF&&q!=INF) mod(ans-=calc(dx,p-q));
}
void solve(){
n=rd,t=rd,ans=1ll*n*calc(0,0)%MOD;
for(int i=1;i<=n;++i) a[i]={rd,rd}; sort(a+1,a+n+1);
for(int i=1;i<=n;++i){
s.clear();
for(int j=i+1;j<=n;++j)
solve(i,j),s.insert(a[j][1]);
}
printf("%d\n", ans);
}
int main(){
int T=1;
while(T--) solve();
return 0;
}
|