CF 1086 题解

Author： RainAir
发布时间：September 19, 2020
1373views
3 comments
1246 words
Categories：题解

这场 C sb了敲错一个字符爆零了。。最后发现 D 也很简单。

策略以后还是要先做掉简单题，然后难题调不出来就换题，先大体浏览一下题目再做（说不定后面有我擅长的题呢）

A

我们按照 $x$ 坐标排序，设 $y$ 坐标处于中间位置的点是 $a$，另外的点是 $b,c$，那么可以先连两条过 $b,c$ 垂直于 $a$ 所在的水平线上的两条线，然后连一下 $a$ 的水平线即可。

B

注意到可以设置为 $0$ 边，并且直径的两个端点一定是叶子，设叶子有 $l$ 个，可以给每个叶子上面的边分配 $\frac{s}{l}$，答案是 $2\frac{s}{l}$。

C

类似数位 dp 枚举卡上界/下界分别卡到哪里，能得到一堆限制区间，现在变成了将区间和区间内的点配对的问题，可以按照左端点排序每次取右端点最小的区间配对。

但是我把 $n$ 和 $k$ 写反了。。。要不然早就过了

D

发现一个点前后是独立的，分别考虑。

考虑它的前缀：这个点能胜利要么前面所有的点都和它平局或者被它打败，要么有能打败它的和能被它打败的。证明考虑每一对能打败它的和能被它打败的点即可。

统计答案的时候我们枚举每种动作，如果一个点合法，当且仅当它的前缀/后缀不会出现仅存在能打败它的动作，但是发现这是若干个区间的交，不是很好做，于是我们容斥后去求不合法的区间的并，用 set 维护一下每种颜色编号最大和最小的位置，树状数组维护一下数字的排名就行了。

E

先思考有多少个好的矩阵：这个矩阵要求这一行是上一行的错排，设错排为 $h(n)$，那么数量就是 $n!h(n)^{n-1}$。

字典序问题肯定是枚举到哪个位置失配，由于第一行没有错排限制所有可以先特判掉。接下来考虑剩下的一般情况：

假设我们考虑到 $(i,j)$ 失配，首先下面的 $n-j$ 行方案都是错排，也就是 $h(n)^{n-j}$，现在只需要考虑这一行：

先考虑暴力枚举 $a_{i,j}$ 是啥，然后发现这种问题相当于钦定了若干数的错排问题，而这种问题的答案只和长度与有效的限制有关（有效的限制指这个数之前都没被用过，也就是不属于可以随便放的状态）。这里有一个容斥式子可以做，但是需要 NTT。

发现所有的方案乘上一个置换后是等价的，于是考虑设计 dp $f_{i,j}$ 表示长度为 $i$ 有 $j$ 条限制的方案数。

那么有转移 $f_{i,j} = f_{i,j-1}-f_{i-1,j-1}$（相当于用全部的情况减去违反最后一个限制的情况）

如果暴力枚举 $a_{i,j}$ 是啥能得到一个 $O(n^3)$ 的做法过不去，但是发现各种 $a_{i,j}$ 的不同之处仅在与它是不是属于一个有效的限制，所以只需要数一下可选的数有多少个是属于有效的限制并且 $< x$，多少不是并且 $<x$ ，可以用桶+树状数组维护。注意要特判一下这个位置和上一行不能相等即可。

一类求排名的问题也就是求字典序比它小个数，不要被骗了。

#include <bits/stdc++.h>

#define fi first
#define se second
#define db double
#define U unsigned
#define P std::pair<int,int>
#define LL long long
#define pb push_back
#define MP std::make_pair
#define all(x) x.begin(),x.end()
#define CLR(i,a) memset(i,a,sizeof(i))
#define FOR(i,a,b) for(int i = a;i <= b;++i)
#define ROF(i,a,b) for(int i = a;i >= b;--i)
#define DEBUG(x) std::cerr << #x << '=' << x << std::endl

const int MAXN = 2000+5;
const int ha = 998244353;
int f[MAXN][MAXN];

inline void add(int &x,int y){
    x += y;if(x >= ha) x -= ha;
}

// 长度为i的排列 有j个位置限制

inline void prework(){
    f[0][0] = 0;
    f[1][0] = 1;f[1][1] = 0;
    FOR(i,2,MAXN-1){
        f[i][0] = 1ll*f[i-1][0]*i%ha;
        FOR(j,1,i){
            f[i][j] = f[i][j-1];
            add(f[i][j],ha-f[i-1][j-1]);
        }
    }
}

int n,a[MAXN][MAXN];
int cnt[MAXN],now;

struct BIT{
    #define lowbit(x) ((x)&(-(x)))
    int tree[MAXN];
    
    inline void add(int pos,int x){
        while(pos < MAXN){
            tree[pos] += x;
            pos += lowbit(pos);
        }
    }
    
    inline int query(int pos){
        int res = 0;if(!pos) return 0;
        while(pos){
            res += tree[pos];
            pos -= lowbit(pos);
        }
        return res;
    }
}bit1,bit2;
bool vis[MAXN];
// 1=无限制
// 2=有限制

inline int qpow(int a,int n=ha-2){
    int res = 1;
    while(n){
        if(n & 1) res = 1ll*res*a%ha;
        a = 1ll*a*a%ha;
        n >>= 1;
    }
    return res;
}

inline void ins(int x,int d){
    ++cnt[x];if(cnt[x] == 2) ++now;
    if(d){
        if(cnt[x] == 1) bit1.add(x,1);
        else bit2.add(x,1);
    }
    else{
        if(cnt[x] == 2) bit1.add(x,-1),bit2.add(x,1);
    }
}

int main(){
    prework();
    scanf("%d",&n);FOR(i,1,n) FOR(j,1,n) scanf("%d",&a[i][j]);
    // TODO: 第一行特判
    int ans = 0;
    ROF(i,n,1){
        // 第一行没有错排限制!
        int c = bit1.query(a[1][i]);
        if(c) add(ans,1ll*c*f[n-i][0]%ha);
        bit1.add(a[1][i],1);
    }
    // DEBUG(ans);
    ans = 1ll*ans*qpow(f[n][n],n-1)%ha;
    FOR(i,2,n){
        CLR(cnt,0);CLR(vis,0);CLR(bit1.tree,0);CLR(bit2.tree,0);now = 0;
        int gx = 0;
        ROF(j,n,1){
            /*
            首先要计算出前i个中有多少数字是相同的k,那么后面的数有j-k个没有限制
            然后枚举这个位置填什么 情况只有填都有的和没有的
            */
            // 现在需要知道 当前的位置 有多少个数字 有限制/无限制
            ins(a[i-1][j],0);ins(a[i][j],1);
            int t1 = bit1.query(a[i][j]-1),t2 = bit2.query(a[i][j]-1),sz = n-j+1;
            if(cnt[a[i-1][j]] == 2 && a[i-1][j] < a[i][j]) t2--;
            // if(j == 2)DEBUG(sz-1),DEBUG(now);    
            add(gx,1ll*t1*f[sz-1][now-(cnt[a[i-1][j]]==2)]%ha);
            add(gx,1ll*t2*f[sz-1][now-1-(cnt[a[i-1][j]]==2)]%ha);
        }
        // if(i == 2) exit(0);
        gx = 1ll*gx*qpow(f[n][n],n-i)%ha;
        add(ans,gx);
    }
    printf("%d\n",ans);
    return 0;
}
/*
每一行是以上一行为基的错排 设错排为 h(n)
有多少个好矩阵? h(n)^n
枚举第i行开始不同 后面都是错排方案数
然后枚举 (i,j) 格子不同,如果能枚举这个格子填的是啥,相当于就是一个固定数字的错排问题了
*/

F

这个东西显然是不能直接算的，但是我们发现设 $f(x)$ 表示 $x$ 时刻覆盖面积大小还是可以算的，考虑转化到这上面。

首先有一个经典的考虑贡献的转化：设 $t_i$ 表示 $i$ 点被燃烧的时间，那么 $\sum t_i = \sum (t-t_i) = tf(t)-\sum_{i=0}^{t-1}f(i)$。所以现在的目标是如何求 $\sum_{i=0}^{t-1}f(i)$。

剩下的我也想不到。。对于 $t$ 这么大肯定要考虑插值之类的，首先容斥原理变成求交，我们考虑两个点的交的情况：首先在没有触碰的时候一直是 $0$，之后就是一个二次函数。所以相当于在每两个矩形开始相碰的时候就要加上一个二次函数，也就是在这里分段，整体形状是分段二次函数。而将分段二次函数段内线性组合不会影响函数的形态，所以整个 $f(i)$ 就是分段二次函数，段都分在某个时间点两个矩形开始相交的时候。然后对每一段插个值就行了。

这里不得不提一下线段树求矩形并或者离散化维护东西的细节：必须要让区间是左闭右开/左开右闭区间才不会算重，可以好好看看代码。。写了一晚上

#include <bits/stdc++.h>

#define fi first
#define se second
#define db double
#define U unsigned
#define P std::pair<int,int>
#define LL long long
#define pb push_back
#define MP std::make_pair
#define all(x) x.begin(),x.end()
#define CLR(i,a) memset(i,a,sizeof(i))
#define FOR(i,a,b) for(int i = a;i <= b;++i)
#define ROF(i,a,b) for(int i = a;i >= b;--i)
#define DEBUG(x) std::cerr << #x << '=' << x << std::endl

const int ha = 998244353;
const int inv2 = 499122177;
const int inv6 = 166374059;
const int MAXN = 300+5;
std::vector<LL> Sx,Sy;

namespace DS{
    int sm[MAXN<<2],tag[MAXN<<2];
    #define lc ((x)<<1)
    #define rc ((x)<<1|1)
    
    inline void modify(int x,int l,int r,int L,int R,int d){
        // int len = Sy[r-1]-(l==1?Sy[0]:Sy[l-2]);
        int len = Sy[r]-Sy[l-1];
        // if(l == 1 && r == 2) DEBUG(Sy[r]),DEBUG(Sy[l-1]);
        // DEBUG(l);DEBUG(r);DEBUG(len);
        if(l == L && r == R){
            tag[x] += d;
            sm[x] = tag[x] ? len : (l==r?0:(sm[lc]+sm[rc])%ha);
            return;
        }
        int mid = (l + r) >> 1;
        if(R <= mid) modify(lc,l,mid,L,R,d);
        else if(L > mid) modify(rc,mid+1,r,L,R,d);
        else modify(lc,l,mid,L,mid,d),modify(rc,mid+1,r,mid+1,R,d);
        sm[x] = tag[x]?len:(l==r?0:(sm[lc]+sm[rc])%ha);
    }
}
using DS::modify;

int x[MAXN],y[MAXN],n;

inline void add(int &x,int y){
    x += y;if(x >= ha) x -= ha;
}

struct Node{
    int x1,y1,x2,y2;//(x1,y1) <= (x2,y2)
    Node(int x1=0,int y1=0,int x2=0,int y2=0) : x1(x1),y1(y1),x2(x2),y2(y2) {}
}a[MAXN];

std::vector<std::pair<P,int> > G[MAXN];

inline int f(int k){
    Sx.clear();Sy.clear();
    FOR(i,1,n){
        a[i] = Node(x[i]-k,y[i]-k,x[i]+k+1,y[i]+k+1);
        Sx.pb(x[i]-k);Sy.pb(y[i]-k);Sx.pb(x[i]+k+1);Sy.pb(y[i]+k+1);
        // DEBUG(x[i]+k+1);DEBUG(y[i]+k+1);
    }
    std::sort(all(Sx));Sx.erase(std::unique(all(Sx)),Sx.end());
    std::sort(all(Sy));Sy.erase(std::unique(all(Sy)),Sy.end());
    // Sx.pb(Sx[0]-1);Sy.pb(Sy[0]-1);
    // std::sort(all(Sx));std::sort(all(Sy));
    int m = Sx.size(),M = Sy.size();
    FOR(i,0,m+1) G[i].clear();
    FOR(i,1,n){
        a[i].x1 = std::lower_bound(all(Sx),a[i].x1)-Sx.begin()+1;
        a[i].x2 = std::lower_bound(all(Sx),a[i].x2)-Sx.begin()+1;
        a[i].y1 = std::lower_bound(all(Sy),a[i].y1)-Sy.begin()+1;
        a[i].y2 = std::lower_bound(all(Sy),a[i].y2)-Sy.begin()+1;
        // printf("%d %d %d %d\n",a[i].x1,a[i].y1,a[i].x2,a[i].y2);
        G[a[i].x1].pb(MP(MP(a[i].y1,a[i].y2),1));
        G[a[i].x2].pb(MP(MP(a[i].y1,a[i].y2),-1));
    }
    Sy.pb(Sy.back());
    // Sy.pb(Sy[0]-1);std::sort(all(Sy));
    // exit(0);
    CLR(DS::sm,0);CLR(DS::tag,0);
    int ans = 0;
    FOR(i,1,m){
        int t = (Sx[i-1]-Sx[std::max(i-2,0)])%ha;
        // DEBUG(t);
        // DEBUG(DS::sm[1]);
        add(ans,1ll*t*DS::sm[1]%ha);
        for(auto x:G[i]) modify(1,1,M,x.fi.fi,x.fi.se-1,x.se);//,DEBUG(x.fi.fi),DEBUG(x.fi.se-1),DEBUG(x.se);
    }
    return ans;
}

inline int sm2(int n){
    int res = 0;if(n < 0) return 0;
    if(n <= 5){
        FOR(i,1,n) add(res,i*i);
    }
    else{
        res = 1ll*n*(n+1)%ha*(2ll*n+1)%ha*inv6%ha;
    }
    return res;
}

inline int sm(int n){
    int res = 0;if(n < 0) return 0;
    if(n <= 5){
        FOR(i,1,n) add(res,i);
    }
    else{
        res = 1ll*n*(n+1)%ha*inv2%ha;
    }
    return res;
}

inline int sm(int l,int r){
    return (sm(r)+ha-sm(l-1))%ha;
}

inline int sm2(int l,int r){
    return (sm2(r)+ha-sm2(l-1))%ha;
}

int main(){
    int t;scanf("%d%d",&n,&t);
    // t = 100000;
    FOR(i,1,n) scanf("%d%d",x+i,y+i);
    std::vector<int> part;part.pb(0);part.pb(t);
    FOR(i,1,n){
        FOR(j,i+1,n){
            int d = std::max(std::abs(x[i]-x[j]),std::abs(y[i]-y[j]));
            d = (d+1)/2;
            if(d >= t) continue;
            part.pb(d);
            // if(d-1 > 0) part.pb(d-1);
            // if(d+1 < t) part.pb(d+1);
        }
    }
    // DEBUG(f(t));
    // exit(0);
    // DEBUG(1ll*(400000000ll+1)*(400000000+1)%ha);
    // exit(0);
    // int ttt = 0;
    // FOR(i,0,t-1) add(ttt,f(i));
    // DEBUG(ttt);
    std::sort(all(part));part.erase(std::unique(all(part)),part.end());
    int ans = 0;
    FOR(i,1,(int)part.size()-1){
        int l = part[i-1],r = part[i]-1;
        // DEBUG(l);DEBUG(r);
        if(r-l+1 <= 3){
            FOR(k,l,r) add(ans,f(k));
            continue;
        }
        int x[3],y[3];
        FOR(j,0,2) y[j] = f(x[j]=l+j);
        int a = 1ll*y[0]*inv2%ha;
        add(a,ha-y[1]);add(a,1ll*y[2]*inv2%ha);
        int b = 1ll*y[0]*inv2%ha*(x[1]+x[2])%ha;
        add(b,ha-1ll*y[1]*((x[0]+x[2])%ha)%ha);
        add(b,1ll*y[2]*inv2%ha*(x[1]+x[0])%ha);
        b = ha-b;
        
        int c = 1ll*x[1]*x[2]%ha*y[0]%ha*inv2%ha;
        add(c,ha-1ll*x[0]*x[2]%ha*y[1]%ha);
        add(c,1ll*x[0]*x[1]%ha*y[2]%ha*inv2%ha);
        // DEBUG(a);DEBUG(b);DEBUG(c);
        // DEBUG(sm(l,r));
        // int tt = 0;
        // FOR(i,l,r) add(tt,i);
        // DEBUG(tt);
        add(ans,1ll*sm2(l,r)*a%ha);
        // DEBUG(sm2(l,r));
        add(ans,1ll*sm(l,r)*b%ha);
        add(ans,1ll*(r-l+1)*c%ha);
    }
    // DEBUG(ans);
    // DEBUG(ans);
    // int _ = 400000000ll*400000000%ha;
    add(ans,ha-1ll*t*f(t)%ha);
    ans = (ha-ans)%ha;
    printf("%d\n",ans);
    return 0;
}
/*
设 f(i) 表示 i 时间有多少个格子着火了
答案就是 tf(t)-\sum_{i=0}^{t-1}f(i)
单次询问 f(i) 是可以求矩阵面积并的,但是你不能询问1e8次
考虑用容斥原理将矩形面积并变成交
观察一个子集 发现只有在某两个矩形由不交变成相交的时候才会分段
所以只有 n^2 段 插值 每一段需要做3/4次矩形面积并
矩形面积并就是离散化后排序 支持区间加删线段 全局查询 修改到对应线段即可
*/

Last modification：September 21st, 2020 at 01:41 pm

如果觉得我的文章对你有用，请随意赞赏

3 comments

RainAir
September 21st, 2020 at 09:23 pm

丁爸带带我

Reply
orz
September 19th, 2020 at 10:38 pm

您好像写错了矩阵的数量应该是$fac_n \times h(n)^{n-1}$

Reply
1. RainAir
  September 21st, 2020 at 01:41 pm
  
  @orz
  
  哦哦谢谢神仙指导
  
  Reply

CF 1086 题解

RainAir • 2020 年 09 月 19 日

这场 C sb了敲错一个字符爆零了。。最后发现 D 也很简单。

策略以后还是要先做掉简单题，然后难题调不出来就换题，先大体浏览一下题目再做（说不定后面有我擅长的题呢）

A

B

注意到可以设置为 $0$ 边，并且直径的两个端点一定是叶子，设叶子有 $l$ 个，可以给每个叶子上面的边分配 $\frac{s}{l}$，答案是 $2\frac{s}{l}$。

C

但是我把 $n$ 和 $k$ 写反了。。。要不然早就过了

D

发现一个点前后是独立的，分别考虑。

E

先思考有多少个好的矩阵：这个矩阵要求这一行是上一行的错排，设错排为 $h(n)$，那么数量就是 $n!h(n)^{n-1}$。

字典序问题肯定是枚举到哪个位置失配，由于第一行没有错排限制所有可以先特判掉。接下来考虑剩下的一般情况：

假设我们考虑到 $(i,j)$ 失配，首先下面的 $n-j$ 行方案都是错排，也就是 $h(n)^{n-j}$，现在只需要考虑这一行：

发现所有的方案乘上一个置换后是等价的，于是考虑设计 dp $f_{i,j}$ 表示长度为 $i$ 有 $j$ 条限制的方案数。

那么有转移 $f_{i,j} = f_{i,j-1}-f_{i-1,j-1}$（相当于用全部的情况减去违反最后一个限制的情况）

一类求排名的问题也就是求字典序比它小个数，不要被骗了。

#include <bits/stdc++.h>

#define fi first
#define se second
#define db double
#define U unsigned
#define P std::pair<int,int>
#define LL long long
#define pb push_back
#define MP std::make_pair
#define all(x) x.begin(),x.end()
#define CLR(i,a) memset(i,a,sizeof(i))
#define FOR(i,a,b) for(int i = a;i <= b;++i)
#define ROF(i,a,b) for(int i = a;i >= b;--i)
#define DEBUG(x) std::cerr << #x << '=' << x << std::endl

const int MAXN = 2000+5;
const int ha = 998244353;
int f[MAXN][MAXN];

inline void add(int &x,int y){
    x += y;if(x >= ha) x -= ha;
}

// 长度为i的排列 有j个位置限制

inline void prework(){
    f[0][0] = 0;
    f[1][0] = 1;f[1][1] = 0;
    FOR(i,2,MAXN-1){
        f[i][0] = 1ll*f[i-1][0]*i%ha;
        FOR(j,1,i){
            f[i][j] = f[i][j-1];
            add(f[i][j],ha-f[i-1][j-1]);
        }
    }
}

int n,a[MAXN][MAXN];
int cnt[MAXN],now;

struct BIT{
    #define lowbit(x) ((x)&(-(x)))
    int tree[MAXN];
    
    inline void add(int pos,int x){
        while(pos < MAXN){
            tree[pos] += x;
            pos += lowbit(pos);
        }
    }
    
    inline int query(int pos){
        int res = 0;if(!pos) return 0;
        while(pos){
            res += tree[pos];
            pos -= lowbit(pos);
        }
        return res;
    }
}bit1,bit2;
bool vis[MAXN];
// 1=无限制
// 2=有限制

inline int qpow(int a,int n=ha-2){
    int res = 1;
    while(n){
        if(n & 1) res = 1ll*res*a%ha;
        a = 1ll*a*a%ha;
        n >>= 1;
    }
    return res;
}

inline void ins(int x,int d){
    ++cnt[x];if(cnt[x] == 2) ++now;
    if(d){
        if(cnt[x] == 1) bit1.add(x,1);
        else bit2.add(x,1);
    }
    else{
        if(cnt[x] == 2) bit1.add(x,-1),bit2.add(x,1);
    }
}

int main(){
    prework();
    scanf("%d",&n);FOR(i,1,n) FOR(j,1,n) scanf("%d",&a[i][j]);
    // TODO: 第一行特判
    int ans = 0;
    ROF(i,n,1){
        // 第一行没有错排限制!
        int c = bit1.query(a[1][i]);
        if(c) add(ans,1ll*c*f[n-i][0]%ha);
        bit1.add(a[1][i],1);
    }
    // DEBUG(ans);
    ans = 1ll*ans*qpow(f[n][n],n-1)%ha;
    FOR(i,2,n){
        CLR(cnt,0);CLR(vis,0);CLR(bit1.tree,0);CLR(bit2.tree,0);now = 0;
        int gx = 0;
        ROF(j,n,1){
            /*
            首先要计算出前i个中有多少数字是相同的k,那么后面的数有j-k个没有限制
            然后枚举这个位置填什么 情况只有填都有的和没有的
            */
            // 现在需要知道 当前的位置 有多少个数字 有限制/无限制
            ins(a[i-1][j],0);ins(a[i][j],1);
            int t1 = bit1.query(a[i][j]-1),t2 = bit2.query(a[i][j]-1),sz = n-j+1;
            if(cnt[a[i-1][j]] == 2 && a[i-1][j] < a[i][j]) t2--;
            // if(j == 2)DEBUG(sz-1),DEBUG(now);    
            add(gx,1ll*t1*f[sz-1][now-(cnt[a[i-1][j]]==2)]%ha);
            add(gx,1ll*t2*f[sz-1][now-1-(cnt[a[i-1][j]]==2)]%ha);
        }
        // if(i == 2) exit(0);
        gx = 1ll*gx*qpow(f[n][n],n-i)%ha;
        add(ans,gx);
    }
    printf("%d\n",ans);
    return 0;
}
/*
每一行是以上一行为基的错排 设错排为 h(n)
有多少个好矩阵? h(n)^n
枚举第i行开始不同 后面都是错排方案数
然后枚举 (i,j) 格子不同,如果能枚举这个格子填的是啥,相当于就是一个固定数字的错排问题了
*/

F

这个东西显然是不能直接算的，但是我们发现设 $f(x)$ 表示 $x$ 时刻覆盖面积大小还是可以算的，考虑转化到这上面。

这里不得不提一下线段树求矩形并或者离散化维护东西的细节：必须要让区间是左闭右开/左开右闭区间才不会算重，可以好好看看代码。。写了一晚上

#include <bits/stdc++.h>

#define fi first
#define se second
#define db double
#define U unsigned
#define P std::pair<int,int>
#define LL long long
#define pb push_back
#define MP std::make_pair
#define all(x) x.begin(),x.end()
#define CLR(i,a) memset(i,a,sizeof(i))
#define FOR(i,a,b) for(int i = a;i <= b;++i)
#define ROF(i,a,b) for(int i = a;i >= b;--i)
#define DEBUG(x) std::cerr << #x << '=' << x << std::endl

const int ha = 998244353;
const int inv2 = 499122177;
const int inv6 = 166374059;
const int MAXN = 300+5;
std::vector<LL> Sx,Sy;

namespace DS{
    int sm[MAXN<<2],tag[MAXN<<2];
    #define lc ((x)<<1)
    #define rc ((x)<<1|1)
    
    inline void modify(int x,int l,int r,int L,int R,int d){
        // int len = Sy[r-1]-(l==1?Sy[0]:Sy[l-2]);
        int len = Sy[r]-Sy[l-1];
        // if(l == 1 && r == 2) DEBUG(Sy[r]),DEBUG(Sy[l-1]);
        // DEBUG(l);DEBUG(r);DEBUG(len);
        if(l == L && r == R){
            tag[x] += d;
            sm[x] = tag[x] ? len : (l==r?0:(sm[lc]+sm[rc])%ha);
            return;
        }
        int mid = (l + r) >> 1;
        if(R <= mid) modify(lc,l,mid,L,R,d);
        else if(L > mid) modify(rc,mid+1,r,L,R,d);
        else modify(lc,l,mid,L,mid,d),modify(rc,mid+1,r,mid+1,R,d);
        sm[x] = tag[x]?len:(l==r?0:(sm[lc]+sm[rc])%ha);
    }
}
using DS::modify;

int x[MAXN],y[MAXN],n;

inline void add(int &x,int y){
    x += y;if(x >= ha) x -= ha;
}

struct Node{
    int x1,y1,x2,y2;//(x1,y1) <= (x2,y2)
    Node(int x1=0,int y1=0,int x2=0,int y2=0) : x1(x1),y1(y1),x2(x2),y2(y2) {}
}a[MAXN];

std::vector<std::pair<P,int> > G[MAXN];

inline int f(int k){
    Sx.clear();Sy.clear();
    FOR(i,1,n){
        a[i] = Node(x[i]-k,y[i]-k,x[i]+k+1,y[i]+k+1);
        Sx.pb(x[i]-k);Sy.pb(y[i]-k);Sx.pb(x[i]+k+1);Sy.pb(y[i]+k+1);
        // DEBUG(x[i]+k+1);DEBUG(y[i]+k+1);
    }
    std::sort(all(Sx));Sx.erase(std::unique(all(Sx)),Sx.end());
    std::sort(all(Sy));Sy.erase(std::unique(all(Sy)),Sy.end());
    // Sx.pb(Sx[0]-1);Sy.pb(Sy[0]-1);
    // std::sort(all(Sx));std::sort(all(Sy));
    int m = Sx.size(),M = Sy.size();
    FOR(i,0,m+1) G[i].clear();
    FOR(i,1,n){
        a[i].x1 = std::lower_bound(all(Sx),a[i].x1)-Sx.begin()+1;
        a[i].x2 = std::lower_bound(all(Sx),a[i].x2)-Sx.begin()+1;
        a[i].y1 = std::lower_bound(all(Sy),a[i].y1)-Sy.begin()+1;
        a[i].y2 = std::lower_bound(all(Sy),a[i].y2)-Sy.begin()+1;
        // printf("%d %d %d %d\n",a[i].x1,a[i].y1,a[i].x2,a[i].y2);
        G[a[i].x1].pb(MP(MP(a[i].y1,a[i].y2),1));
        G[a[i].x2].pb(MP(MP(a[i].y1,a[i].y2),-1));
    }
    Sy.pb(Sy.back());
    // Sy.pb(Sy[0]-1);std::sort(all(Sy));
    // exit(0);
    CLR(DS::sm,0);CLR(DS::tag,0);
    int ans = 0;
    FOR(i,1,m){
        int t = (Sx[i-1]-Sx[std::max(i-2,0)])%ha;
        // DEBUG(t);
        // DEBUG(DS::sm[1]);
        add(ans,1ll*t*DS::sm[1]%ha);
        for(auto x:G[i]) modify(1,1,M,x.fi.fi,x.fi.se-1,x.se);//,DEBUG(x.fi.fi),DEBUG(x.fi.se-1),DEBUG(x.se);
    }
    return ans;
}

inline int sm2(int n){
    int res = 0;if(n < 0) return 0;
    if(n <= 5){
        FOR(i,1,n) add(res,i*i);
    }
    else{
        res = 1ll*n*(n+1)%ha*(2ll*n+1)%ha*inv6%ha;
    }
    return res;
}

inline int sm(int n){
    int res = 0;if(n < 0) return 0;
    if(n <= 5){
        FOR(i,1,n) add(res,i);
    }
    else{
        res = 1ll*n*(n+1)%ha*inv2%ha;
    }
    return res;
}

inline int sm(int l,int r){
    return (sm(r)+ha-sm(l-1))%ha;
}

inline int sm2(int l,int r){
    return (sm2(r)+ha-sm2(l-1))%ha;
}

int main(){
    int t;scanf("%d%d",&n,&t);
    // t = 100000;
    FOR(i,1,n) scanf("%d%d",x+i,y+i);
    std::vector<int> part;part.pb(0);part.pb(t);
    FOR(i,1,n){
        FOR(j,i+1,n){
            int d = std::max(std::abs(x[i]-x[j]),std::abs(y[i]-y[j]));
            d = (d+1)/2;
            if(d >= t) continue;
            part.pb(d);
            // if(d-1 > 0) part.pb(d-1);
            // if(d+1 < t) part.pb(d+1);
        }
    }
    // DEBUG(f(t));
    // exit(0);
    // DEBUG(1ll*(400000000ll+1)*(400000000+1)%ha);
    // exit(0);
    // int ttt = 0;
    // FOR(i,0,t-1) add(ttt,f(i));
    // DEBUG(ttt);
    std::sort(all(part));part.erase(std::unique(all(part)),part.end());
    int ans = 0;
    FOR(i,1,(int)part.size()-1){
        int l = part[i-1],r = part[i]-1;
        // DEBUG(l);DEBUG(r);
        if(r-l+1 <= 3){
            FOR(k,l,r) add(ans,f(k));
            continue;
        }
        int x[3],y[3];
        FOR(j,0,2) y[j] = f(x[j]=l+j);
        int a = 1ll*y[0]*inv2%ha;
        add(a,ha-y[1]);add(a,1ll*y[2]*inv2%ha);
        int b = 1ll*y[0]*inv2%ha*(x[1]+x[2])%ha;
        add(b,ha-1ll*y[1]*((x[0]+x[2])%ha)%ha);
        add(b,1ll*y[2]*inv2%ha*(x[1]+x[0])%ha);
        b = ha-b;
        
        int c = 1ll*x[1]*x[2]%ha*y[0]%ha*inv2%ha;
        add(c,ha-1ll*x[0]*x[2]%ha*y[1]%ha);
        add(c,1ll*x[0]*x[1]%ha*y[2]%ha*inv2%ha);
        // DEBUG(a);DEBUG(b);DEBUG(c);
        // DEBUG(sm(l,r));
        // int tt = 0;
        // FOR(i,l,r) add(tt,i);
        // DEBUG(tt);
        add(ans,1ll*sm2(l,r)*a%ha);
        // DEBUG(sm2(l,r));
        add(ans,1ll*sm(l,r)*b%ha);
        add(ans,1ll*(r-l+1)*c%ha);
    }
    // DEBUG(ans);
    // DEBUG(ans);
    // int _ = 400000000ll*400000000%ha;
    add(ans,ha-1ll*t*f(t)%ha);
    ans = (ha-ans)%ha;
    printf("%d\n",ans);
    return 0;
}
/*
设 f(i) 表示 i 时间有多少个格子着火了
答案就是 tf(t)-\sum_{i=0}^{t-1}f(i)
单次询问 f(i) 是可以求矩阵面积并的,但是你不能询问1e8次
考虑用容斥原理将矩形面积并变成交
观察一个子集 发现只有在某两个矩形由不交变成相交的时候才会分段
所以只有 n^2 段 插值 每一段需要做3/4次矩形面积并
矩形面积并就是离散化后排序 支持区间加删线段 全局查询 修改到对应线段即可
*/

CF 1086 题解

A

B

C

D

E

F

3 comments

Leave a Comment Cancel reply

I'm back

NOI2021 退役记

SDOI2020 退役记

点双连通分量 & 圆方树学习笔记

CSP2019 游记

「CF1106F」Lunar New Year and a Recursive Sequence

「CF599E」Sandy and Nuts

20联赛集训day4 题解

「HNOI2009」最小圈

Dinic 学习笔记

CF 1086 题解

A

B

C

D

E

F