专栏文章

题解：P4348 [CERC2015] Cow Confinement

hhongyuecheng
P4348题解参与者 8已保存评论 8

文章操作

快速查看文章及其快照的属性，并进行相关操作。

当前评论
8 条
当前快照
1 份
快照标识符
@minnsqj7
此快照首次捕获于
2025/12/02 05:26
3 个月前
此快照最后确认于
2025/12/02 05:26
3 个月前
查看原文

P4348 [CERC2015] Cow Confinement 题解

引言

这是一篇超详细的题解。

题意

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

解题思路

整体上我们从下向上一行一行处理。
我们考虑一朵花对与其同一行的位置的贡献。我们发现位于第 jj 列的花，记 xix_i 为最大的小于 jj 的栅栏或左边界位置，会使 [xi,j][x_i,j] 区间的答案加一，如下图所示。
一朵花对同行的贡献
对于第 ii 行，如果没有下栅栏阻挡，我们发现可以由第 i−1i-1 行转移而来，如图蓝色箭头。 如果有栅栏阻挡，就无法从第 i−1i-1 行转移， 答案清零，如红色箭头。
一朵花对其他行的影响
其实还有一种情况。当走到栅栏的尽头，我们要拆除左右栅栏，这时答案又可以从右边转移来了。
以下图为例，区间 [5,8][5,8] 是由下面一层转移而来。此时右侧栅栏已经走到了尽头，先拆除 22 号格子和 55 号格子左侧的栅栏，由于区间 [2,4][2,4] 无法从下面一层转移过来，所以要先清空区间 [2,4][2,4]，再从点 (5,1)(5,1) 向左转移至下一个栅栏边界或左边界。
处理栅栏尽头
但是，我们发现计算到左上角时，右下角会被重复计算。（如图所示）
特殊处理
所以我们存一下右下角的答案，在左上角减去就行了。

代码实现

从解题思路中不难看出，我们需要一种高效的数据结构来维护答案，要支持区间加、区间赋值为零和单点查询。于是我想到了线段树！线段树区间赋值为零就是对一个区间乘上 00。 线段树2
我们先把点存下来，进行排序（我用的是优先队列），先按纵轴从大到小排，对于同一排，先处理栅栏，再处理花，最后处理牛，其中栅栏从左往右排。
这么排的原因：
  1. 栅栏会影响到花对答案的修改，所以先栅栏。
  2. 花会影响到最终答案，所以把花排在牛的前面。
  3. 左边栅栏边界拆除会影响右边栅栏拆除时赋值的区间，所以先左后右。
对于点：
CPP
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;
}
typei<0type_i<0 代表这个点是牛，其编号为 −typei-type_i。
typei=0type_i=0 代表这个点是花。
typei>0type_i>0 代表这个点是栅栏，第 kk 号栅栏其左上点 typei=k×2−1type_i=k\times 2-1，其右下点 typej=k×2type_j=k\times 2。
对于栅栏和牛：
为了便于快速查找最大的小于 kk 的栅栏位置，和删除位置为 jj 的栅栏。这里用一个 set 来存左右栅栏边界（为了统一我都存栅栏在左侧的格子）。由于栅栏不相邻，不用考虑被去重。
CPP
struct fence{
	ll w;//栅栏宽度
	ll val;//右下角的值
}fc[200007];
set<ll> left_fc;

ll cow[200007];//存每个牛的答案
把所有点加到大根堆里，每次拿堆顶进行处理。
CPP
for(int i=1;i<=cnt;i++){
		pq.push(a[i]);
	}
	rgh++;//防止越界 
	init();
	while(!pq.empty()){
		point p=pq.top();
		pq.pop();
拿出的点如果是栅栏右下点，先记录右下角的答案（方便左上角减去），由于被栅栏遮挡的地方无法从下一层转移，所以用线段树对区间乘上一个 00。最后，用 set 记录左右栅栏。
CPP
			if(!(p.type%2)){
				ll id=p.type/2;
				ll w=fc[id].w,x=p.x;
				fc[id].val=(x+1>rgh?0LL:qry(x+1,1,1,rgh));//防止越界
				update(x-w+1,x,1,1,rgh,0,0);
				left_fc.insert(x+1);
				left_fc.insert(x-w+1);
			}
拿出的点如果是栅栏左上点，我们先拆除左右栅栏边界， 二分找到最大的小于等于当前位置的栅栏边界或左边界 kk,[k,x+w−1][k,x+w-1] 都加上 x+wx+w 上的答案。
CPP
else{
				ll id=p.type/2+1;
				ll w=fc[id].w,val=fc[id].val,x=p.x;
				left_fc.erase(x);
				left_fc.erase(x+w);
				auto it=left_fc.upper_bound(x);
				if(it==left_fc.begin()){
					update(x,x+w-1,1,1,rgh,0,0);
					update(1,x+w-1,1,1,rgh,1,qry(x+w,1,1,rgh));
					if(x!=1) update(1,x-1,1,1,rgh,1,-val);
				}
				else{
					it--;
					update(x,x+w-1,1,1,rgh,0,0);
					update(*it,x+w-1,1,1,rgh,1,qry(x+w,1,1,rgh));
					if(x!=1) update(*it,x-1,1,1,rgh,1,-val);
				}
			}
对于花和牛就比较简单了。如果是花，二分找到最大的小于等于当前位置的栅栏边界或左边界，对区间加 11。如果是牛，记录答案即可。
CPP
		else if(p.type==0){//花的情况
			auto it=left_fc.upper_bound(p.x);
			if(it==left_fc.begin()){
				update(1,p.x,1,1,rgh,1,1);
			}
			else{
				it--;
				update(*it,p.x,1,1,rgh,1,1);
			}
		}
		else{//牛的情况
			cow[-p.type]=qry(p.x,1,1,rgh);
		}
时间复杂度 O(Nlog⁡(NR))O(N\log (NR))，其中 NN 为点的总数，RR 为最靠右节点的横坐标。

完整代码

CPP
#include<bits/stdc++.h>
#define ll long long
using namespace std;

ll f,m,n;
ll rgh;//右边界 

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;

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

priority_queue<point> pq;
struct fence{
	ll w;
	ll val;
}fc[200007];
set<ll> left_fc;

ll cow[200007];

ll tr[5000006];
ll m_tag[5000006],a_tag[5000006];

void init(){
	for(int i=1;i<=rgh;i++){
		m_tag[i]=1;
	}
}
inline ll ls(ll p){return p<<1;}
inline ll rs(ll p){return p<<1|1;}
void push_up(ll p){
	tr[p]=tr[ls(p)]+tr[rs(p)];
	return;
}
void func(ll p,ll m,ll a,ll l,ll r){//先乘后加 
	tr[p]*=m;
	a_tag[p]*=m;
	m_tag[p]*=m;
	tr[p]+=a*(r-l+1);
	a_tag[p]+=a;
	return;
}
void push_down(ll p,ll l,ll r){
	ll mid=(l+r)>>1;
	func(ls(p),m_tag[p],a_tag[p],l,mid);
	func(rs(p),m_tag[p],a_tag[p],mid+1,r);
	m_tag[p]=1;
	a_tag[p]=0;
	return;
}
void update(ll ul,ll ur,ll p,ll l,ll r,ll m,ll a){
	if(ul<=l&&ur>=r){
		func(p,m,a,l,r);
		return;
	}
	push_down(p,l,r);
	ll mid=(l+r)>>1;
	if(ul<=mid) update(ul,ur,ls(p),l,mid,m,a);
	if(ur>mid) update(ul,ur,rs(p),mid+1,r,m,a);
	push_up(p);
	return;
}
ll qry(ll x,ll p,ll l,ll r){
	if(x==l&&x==r){
		return tr[p];
	}
	push_down(p,l,r);
	ll mid=(l+r)>>1,ans=0;
	if(x<=mid) ans=qry(x,ls(p),l,mid);
	else ans=qry(x,rs(p),mid+1,r);
	push_up(p);
	return ans;
}

int main(){
	ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
	cin>>f;
	for(int i=1;i<=f;i++){
		ll x,y,xx,yy;
		cin>>y>>x>>yy>>xx;
		rgh=max(rgh,max(x,xx));
		fc[i].w=xx-x+1;
		add_p(x,y-1,i*2LL-1LL);//
		add_p(xx,yy,i*2LL);
	}
	cin>>m;
	for(int i=1;i<=m;i++){
		ll x,y;
		cin>>y>>x;
		rgh=max(rgh,x);
		add_p(x,y,0);
	}
	cin>>n;
	for(int i=1;i<=n;i++){
		ll x,y;
		cin>>y>>x;
		rgh=max(rgh,x);
		add_p(x,y,-i);
	}
	for(int i=1;i<=cnt;i++){
		pq.push(a[i]);
	}
	rgh++;//防止越界 
	init();
	while(!pq.empty()){
		point p=pq.top();
		pq.pop();
		if(p.type>0){
			if(!(p.type%2)){
				ll id=p.type/2;
				ll w=fc[id].w,x=p.x;
				fc[id].val=(x+1>rgh?0LL:qry(x+1,1,1,rgh));
				update(x-w+1,x,1,1,rgh,0,0);
				left_fc.insert(x+1);
				left_fc.insert(x-w+1);
			}
			else{
				ll id=p.type/2+1;
				ll w=fc[id].w,val=fc[id].val,x=p.x;
				left_fc.erase(x);
				left_fc.erase(x+w);
				auto it=left_fc.upper_bound(x);
				if(it==left_fc.begin()){
					update(x,x+w-1,1,1,rgh,0,0);
					update(1,x+w-1,1,1,rgh,1,qry(x+w,1,1,rgh));
					if(x!=1) update(1,x-1,1,1,rgh,1,-val);
				}
				else{
					it--;
					update(x,x+w-1,1,1,rgh,0,0);
					update(*it,x+w-1,1,1,rgh,1,qry(x+w,1,1,rgh));
					if(x!=1) update(*it,x-1,1,1,rgh,1,-val);
				}
			}
		}
		else if(p.type==0){
			auto it=left_fc.upper_bound(p.x);
			if(it==left_fc.begin()){
				update(1,p.x,1,1,rgh,1,1);
			}
			else{
				it--;
				update(*it,p.x,1,1,rgh,1,1);
			}
		}
		else{
			cow[-p.type]=qry(p.x,1,1,rgh);
		}
	}
	for(int i=1;i<=n;i++){
		cout<<cow[i]<<'\n';
	}
	return 0;
}

评论

共 8 条评论，欢迎与作者交流。

正在加载评论...