题解：P4348 [CERC2015] Cow Confinement

hongyuecheng · 2025-10-08 00:56:16 · 题解

P4348 [CERC2015] Cow Confinement 题解

引言

这是一篇超详细的题解。

题意

给定一个长和宽为 1 \times {10}^{6} 的矩形网格，告诉我们牛、花、栅栏的位置。求对于单独每头牛在只向下或向右的情况下，不跨过栅栏，能到达的花的个数。（栅栏不相交）

解题思路

整体上我们从下向上一行一行处理。

我们考虑一朵花对与其同一行的位置的贡献。我们发现位于第 j 列的花，记 x_i 为最大的小于 j 的栅栏或左边界位置，会使 [x_i,j] 区间的答案加一，如下图所示。

对于第 i 行，如果没有下栅栏阻挡，我们发现可以由第 i-1 行转移而来，如图蓝色箭头。 如果有栅栏阻挡，就无法从第 i-1 行转移， 答案清零，如红色箭头。

其实还有一种情况。当走到栅栏的尽头，我们要拆除左右栅栏，这时答案又可以从右边转移来了。

以下图为例，区间 [5,8] 是由下面一层转移而来。此时右侧栅栏已经走到了尽头，先拆除 2 号格子和 5 号格子左侧的栅栏，由于区间 [2,4] 无法从下面一层转移过来，所以要先清空区间 [2,4]，再从点 (5,1) 向左转移至下一个栅栏边界或左边界。

但是，我们发现计算到左上角时，右下角会被重复计算。（如图所示）

所以我们存一下右下角的答案，在左上角减去就行了。

代码实现

从解题思路中不难看出，我们需要一种高效的数据结构来维护答案，要支持区间加、区间赋值为零和单点查询。于是我想到了线段树！线段树区间赋值为零就是对一个区间乘上 0。 线段树2

我们先把点存下来，进行排序（我用的是优先队列），先按纵轴从大到小排，对于同一排，先处理栅栏，再处理花，最后处理牛，其中栅栏从左往右排。

这么排的原因：

1. 栅栏会影响到花对答案的修改，所以先栅栏。

2. 花会影响到最终答案，所以把花排在牛的前面。

3. 左边栅栏边界拆除会影响右边栅栏拆除时赋值的区间，所以先左后右。

对于点：

struct point{
    ll x,y;
    ll type;
    bool operator <(const point p)const{
        if(y!=p.y) return y<p.y;//从左往右排
        if(type<=0&&p.type>0) return 1;//先栅栏
        if(type>0&&p.type<=0) return 0;
        if(type<0&&p.type==0) return 1;//把花排在牛的前面
        if(type==0&&p.type<0) return 0;
        return x>p.x;
    }
}a[1000007];
ll cnt;
priority_queue<point> pq;

void add_p(ll x,ll y,ll type){
    cnt++;
    a[cnt].y=y;
    a[cnt].x=x;
    a[cnt].type=type;
}