有点意思的题目
直接统计每个格子的val是非常难办的。很难知道每秒新出来多少个格子
设$F[i]$表示，前i时刻覆盖的格子的数量
则，$ans=sum_{i=1}^T i*(F[i]-F[i-1])=T*F[T]-sum_{i=0}^{T-1} F[i]$
考虑$sum_{i=0}^{T-1} F[i]$怎么求
$F[i]$可以是矩形面积并，但是不能暴力求，T太大
一起求？
麻烦的事情自然是两个点代表的正方形在某个时刻相交了
考虑相交之后的面积并的式子，是一个容斥的式子，涉及的都是矩形面积的加减，
所以是一个关于T的二次函数！
而一共有$N^2$次相交
所以F图像是分段二次函数！！
对于每一段，可以3次插值求出表达式，然后求和。
每次插值就是一次矩形面积并了。
O(n^3logn)
#include<bits/stdc++.h> #define reg register int #define il inline #define fi first #define se second #define mk(a,b) make_pair(a,b) #define numb (ch^'0') #define pb push_back #define solid const auto & #define enter cout<<endl #define pii pair<int,int> using namespace std; typedef long long ll; template<class T>il void rd(T &x){ char ch;x=0;bool fl=false;while(!isdigit(ch=getchar()))(ch=='-')&&(fl=true); for(x=numb;isdigit(ch=getchar());x=x*10+numb);(fl==true)&&(x=-x);} template<class T>il void output(T x){if(x/10)output(x/10);putchar(x%10+'0');} template<class T>il void ot(T x){if(x<0) putchar('-'),x=-x;output(x);putchar(' ');} template<class T>il void prt(T a[],int st,int nd){for(reg i=st;i<=nd;++i) ot(a[i]);putchar(' ');} namespace Modulo{ const int mod=998244353; int ad(int x,int y){return (x+y)>=mod?x+y-mod:x+y;} void inc(int &x,int y){x=ad(x,y);} int mul(int x,int y){return (ll)x*y%mod;} int sub(int x,int y){return ad(x,mod-y);} void inc2(int &x,int y){x=mul(x,y);} int qm(int x,int y=mod-2){int ret=1;while(y){if(y&1) ret=mul(x,ret);x=mul(x,x);y>>=1;}return ret;} template<class ...Args>il int ad(const int a,const int b,const Args &...args) {return ad(ad(a,b),args...);} template<class ...Args>il int mul(const int a,const int b,const Args &...args) {return mul(mul(a,b),args...);} } using namespace Modulo; namespace Miracle{ const int N=505; int n,T; int X[N],Y[N]; int tmp[N]; int z[N]; #define ls (x<<1) #define rs (x<<1|1) #define mid ((l+r)>>1) struct node{ int ct,val; int sum; }t[4*N]; void pushup(int x){ if(t[x].ct) t[x].sum=t[x].val; else t[x].sum=t[x<<1].sum+t[x<<1|1].sum; } void build(int x,int l,int r){ if(l==r){ t[x].ct=0;t[x].sum=0; t[x].val=z[l]-z[l-1]; // cout<<" val "<<l<<" "<<r<<" : "<<t[x].val<<endl; return; } t[x].ct=0;t[x].sum=0; t[x].val=z[r]-z[l-1]; build(ls,l,mid); build(rs,mid+1,r); } void upda(int x,int l,int r,int L,int R,int c){ if(L<=l&&r<=R){ t[x].ct+=c;pushup(x); return; } if(L<=mid) upda(ls,l,mid,L,R,c); if(mid<R) upda(rs,mid+1,r,L,R,c); pushup(x); } struct qs{ int p,c; int u,d; qs(){} qs(int pp,int cc,int dd,int uu){ p=pp;c=cc;d=dd;u=uu; } bool friend operator <(qs a,qs b){ return a.p<b.p; } }h[N]; ll calc(int tim){ // cout<<" calc *******"<<tim<<endl; int ch=0,cl=0,cz=0; for(reg i=1;i<=n;++i){ h[++ch]=qs(X[i]-tim,1,Y[i]-tim,Y[i]+tim); h[++ch]=qs(X[i]+tim+1,-1,Y[i]-tim,Y[i]+tim); tmp[++cl]=Y[i]+tim; tmp[++cl]=Y[i]-tim; } sort(h+1,h+ch+1); sort(tmp+1,tmp+cl+1); cl=unique(tmp+1,tmp+cl+1)-tmp-1; z[0]=tmp[1]-1; for(reg i=1;i<=cl;++i){ z[++cz]=tmp[i]; if(i!=cl&&tmp[i+1]!=tmp[i]+1){ z[++cz]=tmp[i+1]-1; } } // cout<<" zz "<<endl; // prt(z,1,cz); build(1,1,cz); ll ret=0; for(reg i=1;i<=ch;++i){ if(i!=1){ ret+=(ll)t[1].sum*(h[i].p-h[i-1].p); } h[i].u=lower_bound(z+1,z+cz+1,h[i].u)-z; h[i].d=lower_bound(z+1,z+cz+1,h[i].d)-z; // cout<<" u "<<h[i].u<<" d "<<h[i].d<<endl; upda(1,1,cz,h[i].d,h[i].u,h[i].c); // cout<<"after "<<i<<" sum "<<t[1].sum<<endl; } // cout<<"RETETETE "<<ret<<endl; return ret%mod;//warning!!! % mod } int nr[55*55],num; ll px[5],py[5]; int ping(int n){ return mul(n,n+1,2*n+1,qm(6)); } int main(){ rd(n);rd(T); for(reg i=1;i<=n;++i){ rd(X[i]);rd(Y[i]); } nr[++num]=0; for(reg i=1;i<=n;++i){ for(reg j=i+1;j<=n;++j){ int yu=max((abs(X[i]-X[j])+1)/2,(abs(Y[i]-Y[j])+1)/2); nr[++num]=yu; } } nr[++num]=T; sort(nr+1,nr+num+1); num=unique(nr+1,nr+num+1)-nr-1; int ans=mul(T,calc(T)); // cout<<" ans "<<ans<<endl; for(reg i=1;i<=num;++i){ if(nr[i]==T) break; int tot=0; int ti=nr[i]; while(ti-nr[i]<3&&ti!=nr[i+1]){ px[++tot]=ti; py[tot]=calc(ti); ++ti; } // cout<<"tot----------- "<<tot<<endl; // prt(py,1,tot); if(tot<=2){ for(reg j=1;j<=tot;++j){ inc(ans,mod-py[j]); } }else{ // cout<<" TriTri "; int A=0,B=0,C=0; for(reg j=1;j<=tot;++j){ int lp=py[j]; int ss=0,sc=1; for(reg k=1;k<=tot;++k){ if(k==j) continue; lp=mul(lp,qm(ad(px[j],mod-px[k]))); inc(ss,px[k]); inc2(sc,px[k]); } A=ad(A,lp); B=ad(B,mod-mul(lp,ss)); C=ad(C,mul(lp,sc)); } int st=nr[i],nd=nr[i+1]-1; inc(ans,mod-ad(mul(A,sub(ping(nd),ping(st-1))),mul(B,(nd-st+1),(nd+st),qm(2)),mul(C,(nd-st+1)))); } } ot(ans); return 0; } } signed main(){ Miracle::main(); return 0; } /* Author: *Miracle* */
i*cnt，i每次+1，很套路
题意转化为求$sum_{i=0}^{T-1} F[i]$
发现，$F[i]$是一个分段二次函数，然后插值！