BZOJ 4422（CERC 2015）Cow Confinement（扫描线+线段树+差分）

发表于 |
字数统计: 1,455字 | 阅读时长 ≈ 8min

[CERC2015]奶牛围栏

问题描述

一个10^6行10^6列的网格图，上面有一些牛、花和一些矩形围栏，围栏在格子的边界上，牛和花在格子里，牛只能向下或向右走，牛也不能穿过围栏和地图边界，求每头牛它能到达的花的数量。注意栅栏不会相交

.png)

输入格式

第一行一个数f表示矩形围栏的数量。

接下来f行，每行四个数x1,y1,x2,y2，表示(x1,y1)在围栏内部矩形的左上角，(x2,y2)在右下角。

接下来一行一个数m表示花的数量。

接下来m行每行两个数x,y，表示在(x,y)处有一朵花。

接下来一行一个数n表示牛的数量。

接下来n行每行两个数x,y，表示在(x,y)处有一头牛。

输出格式

总共n行，每行一个数ans，第i个数表示第i头牛能到ans个花。

样例输入

4

2 2 8 4

1 9 4 10

6 7 9 9

3 3 7 3

9

3 4

8 4

11 5

10 7

10 8

9 8

2 8

4 11

9 11

8

1 1

5 10

6 9

3 7

7 1

4 2

7 5

3 3

样例输出

5

1

0

1

3

1

3

0

由于每头牛只能往右或往下走，我们考虑从右往左扫描，令$f[i]$表示扫描到当前$x$坐标时，纵坐标为$i$的位置能到的花的数目，那么考虑维护$f[i]$，发现不是很好维护，令$g[i]=f[i]-f[i+1]$，考虑来维护$g[i]$

如果遇到一朵花，就是单点修改，如果遇到右栅栏$[l,r]$，那么就是将$[l,p]$（p为$l$下方第一个栅栏的位置）区间的和加到$g[l-1]$上，然后记录一下当前$[r+1,p]$的和$res[i]$，再清空$[l,r]$

如果遇到左栅栏$[l,r]$，就清空$[l,r]$区间，然后在$l-1$位置减去先前记录的$res[i]$，这个画个图就能看出来此时$res[i]$被重复计算了一次，因此要减掉。

如果遇到牛$x$，就是查询$[x,p]$的和，因此只需要扫描线时用线段树来维护$g[i]$即可。

这题疑似数据和描述不清，特别注意排序顺序。

代码：

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
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
#include<stdio.h>
#include<iostream>
#include<algorithm>
#include<cstring>
#include<set>
#define N 200005
using namespace std;
char buf[1<<20],*p1,*p2;
#define GC (p1==p2&&(p2=(p1=buf)+fread(buf,1,1000000,stdin),p1==p2)?0:*p1++)
inline int _R()
{
	char t=GC;int x;
	while(t<48||t>57)t=GC;
	for(x=0;t>47&&t<58;t=GC)x=(x<<3)+(x<<1)+t-48;
	return x;
}
const int T=1e6+1;
set<int>Q;
struct node{int x1,x2,y1,y2;}fence[N];
struct thh{int pos,l,r,id,ty;}op[N<<3];
struct nodd{int x,y,id;}flower[N],cow[N];
bool cmp1(thh a,thh b)
{
	if(a.pos!=b.pos)return a.pos>b.pos;
	if(a.ty!=b.ty&&(a.ty>2||b.ty>2))return a.ty<b.ty;
	if(a.l!=b.l)return a.l<b.l;
	return a.r<b.r;
}
int f,n,m,res[N],Ans[N];
namespace Seg
{
	int tot,ls[T<<2],rs[T<<2],v[T<<2],lazy[T<<2];
	int BT(int x,int y)
	{
		int p=++tot;
		if(x==y)return p;
		int mid=x+y>>1;
		ls[p]=BT(x,mid);
		rs[p]=BT(mid+1,y);
		return p;
	}
	void PD(int p)
	{
		v[ls[p]]=v[rs[p]]=0;
		lazy[ls[p]]=lazy[rs[p]]=1;
		lazy[p]=0;
	}
	void Clear(int p,int l,int r,int x,int y)
	{
		if(lazy[p])PD(p);
		if(x<=l&&y>=r){v[p]=0;lazy[p]=-1;return;}
		int mid=l+r>>1;
		if(x<=mid&&y>=l)Clear(ls[p],l,mid,x,y);
		if(x<=r&&y>mid)Clear(rs[p],mid+1,r,x,y);
		v[p]=v[ls[p]]+v[rs[p]];
	}
	void ADD(int p,int l,int r,int k,int d)
	{
		if(lazy[p])PD(p);v[p]+=d;
		if(l==r)return;
		int mid=l+r>>1;
		if(k<=mid)ADD(ls[p],l,mid,k,d);
		else ADD(rs[p],mid+1,r,k,d);
		v[p]=v[ls[p]]+v[rs[p]];
	}
	int GS(int p,int l,int r,int x,int y)
	{
		if(lazy[p])PD(p);
		if(x<=l&&y>=r)return v[p];
		int mid=l+r>>1,sum=0;
		if(x<=mid&&y>=l)sum+=GS(ls[p],l,mid,x,y);
		if(x<=r&&y>mid)sum+=GS(rs[p],mid+1,r,x,y);
		return sum;
	}
}
int Get(int x)
{
	set<int>::iterator it=Q.lower_bound(x);
	return *it;
}
int main()
{
	int i,j,k,x,y,x1,x2,y1,y2,tot;
	f=_R();
	for(i=1;i<=f;i++)
	{
		x1=_R();y1=_R();x2=_R();y2=_R();
		fence[i]=(node){x1,x2,y1,y2};
	}
	m=_R();for(i=1;i<=m;i++)flower[i]=(nodd){_R(),_R(),i};
	n=_R();for(i=1;i<=n;i++)cow[i]=(nodd){_R(),_R(),i};
	for(i=1;i<=f;i++)
	{
		op[i]=(thh){fence[i].y1-1,fence[i].x1,fence[i].x2,i,2};
		op[i+f]=(thh){fence[i].y2,fence[i].x1,fence[i].x2,i,1};
	}
	Seg::BT(0,T);tot=f+f;Q.insert(T);
	for(i=1;i<=m;i++)op[++tot]=(thh){flower[i].y,flower[i].x,0,i,3};
	for(i=1;i<=n;i++)op[++tot]=(thh){cow[i].y,cow[i].x,0,i,4};
	sort(op+1,op+tot+1,cmp1);
	for(i=1;i<=tot;i++)
	{
		if(op[i].ty==1)
		{
			res[op[i].id]=Seg::GS(1,0,T,op[i].r+1,Get(op[i].r+1));
			int tmp=Seg::GS(1,0,T,op[i].l,Get(op[i].l));
			Seg::Clear(1,0,T,op[i].l,op[i].r);
			Seg::ADD(1,0,T,op[i].l-1,tmp);
			Q.insert(op[i].l-1);Q.insert(op[i].r);
		}
		else if(op[i].ty==3)Seg::ADD(1,0,T,op[i].l,1);
		else if(op[i].ty==4)Ans[op[i].id]=Seg::GS(1,0,T,op[i].l,Get(op[i].l));
		else if(op[i].ty==2)
		{
			Seg::Clear(1,0,T,op[i].l,op[i].r);
			Seg::ADD(1,0,T,op[i].l-1,-res[op[i].id]);
			Q.erase(op[i].l-1);Q.erase(op[i].r);
		}
	}
	for(i=1;i<=n;i++)printf("%d\n",Ans[i]);
}