BZOJ 4422 Cow Confinement (线段树、DP、扫描线、差分)

题目链接: https://www.lydsy.com/JudgeOnline/problem.php?id=4422

我真服了。。这题我能调一天半，最后还是对拍拍出来的。。。脑子还是有病啊

题解: 首先可以dp, 分情况讨论: 若下面右面都有栅栏则值为零，若仅下面有栅栏则dp值等于右面，若仅右面有栅栏则dp值等于下面，若\((i,j)\)满足存在一矩形\((i+1,j+1)-(x,y)\)则dp[i][j]=dp[i+1][j]+dp[i][j+1]-dp[x+1][y+1]，否则dp[i][j]=dp[i+1][j]+dp[i][j+1]-dp[i+1][j+1]

然后考虑用线段树+扫描线优化。差分之后推一波发现只需要支持: 单点加、区间覆盖(为0)、区间求和。

扫描线写得还是不熟。注意如果从右往左扫，同一竖列一定要先加入栅栏再删除栅栏！如数据:

代码

#include<cstdio>

#include<cstdlib>

#include<cstring>

#include<cassert>

#include<set>

#include<iostream>

#include<algorithm>

using namespace std;

inline int read()

{

	int x=0; bool f=1; char c=getchar();

	for(;!isdigit(c);c=getchar()) if(c=='-') f=0;

	for(; isdigit(c);c=getchar()) x=(x<<3)+(x<<1)+(c^'0');

	if(f) return x;

	return -x;

}

const int N = 2e5;

const int C = 1e6;

struct SegmentTree

{

	struct SgTNode

	{

		int sum,tag;

		SgTNode() {sum = 0,tag = -1;}

	} sgt[(C<<2)+3];

	void pushdown(int pos,int le,int ri)

	{

		int mid = (le+ri)>>1;

		if(sgt[pos].tag>-1)

		{

			sgt[pos<<1].sum = sgt[pos].tag*(mid-le+1); sgt[pos<<1].tag = sgt[pos].tag;

			sgt[pos<<1|1].sum = sgt[pos].tag*(ri-mid); sgt[pos<<1|1].tag = sgt[pos].tag;

			sgt[pos].tag = -1;

		}

	}

	void addval(int pos,int le,int ri,int lrb,int val)

	{

		if(le==lrb && ri==lrb) {sgt[pos].sum += val; sgt[pos].tag = -1; return;}

		pushdown(pos,le,ri);

		int mid = (le+ri)>>1;

		if(lrb<=mid) addval(pos<<1,le,mid,lrb,val);

		else addval(pos<<1|1,mid+1,ri,lrb,val);

		sgt[pos].sum = sgt[pos<<1].sum+sgt[pos<<1|1].sum;

	}

	void modify(int pos,int le,int ri,int lb,int rb,int val)

	{

		if(le>=lb && ri<=rb) {sgt[pos].sum = (ri-le+1)*val; sgt[pos].tag = val; return;}

		pushdown(pos,le,ri);

		int mid = (le+ri)>>1;

		if(lb<=mid) {modify(pos<<1,le,mid,lb,rb,val);}

		if(rb>mid) {modify(pos<<1|1,mid+1,ri,lb,rb,val);}

		sgt[pos].sum = sgt[pos<<1].sum+sgt[pos<<1|1].sum;

	}

	int querysum(int pos,int le,int ri,int lb,int rb)

	{

		if(le>=lb && ri<=rb) {return sgt[pos].sum;}

		pushdown(pos,le,ri);

		int mid = (le+ri)>>1,ret = 0;

		if(lb<=mid) {ret += querysum(pos<<1,le,mid,lb,rb);}

		if(rb>mid) {ret += querysum(pos<<1|1,mid+1,ri,lb,rb);}

		sgt[pos].sum = sgt[pos<<1].sum+sgt[pos<<1|1].sum;

		return ret;

	}

} sgt;

struct Event

{

	int opt,x,y,xx,yy,ans,id; //1Õ¤À¸×ó²à£¬2Õ¤À¸ÓÒ²à£¬3»¨£¬4Å£

	bool operator <(const Event &arg) const

	{

		if(x<arg.x) return true; else if(x>arg.x) return false;

		if(opt>arg.opt) return true; else if(opt<arg.opt) return false;

		return y>arg.y;

	}

} qr[(N<<2)+3];

bool cmp_id(Event x,Event y) {return x.id<y.id;}

int id[(N<<2)+3];

set<int> s;

int n,m,p,q;

int getval(int y) //yµ½ÏÂÃæµÚÒ»¸öÅ£À¸-1µÄºÍ

{

	int tmp = *s.upper_bound(y);

	int ret = sgt.querysum(1,1,C,y,tmp-1);

	return ret;

}

int main()

{

	int q = 0;

	scanf("%d",&p);

	for(int i=1; i<=p; i++)

	{

		int lbx,rbx,lby,rby; scanf("%d%d%d%d",&lby,&lbx,&rby,&rbx);

		q++; qr[q].x = lbx-1; qr[q].y = lby; qr[q].opt = 2; qr[q].id = q;

		q++; qr[q].x = rbx; qr[q].y = rby; qr[q].opt = 1; qr[q].id = q;

	}

	scanf("%d",&m); for(int i=1; i<=m; i++) {int x,y; scanf("%d%d",&y,&x); q++; qr[q].x = x; qr[q].y = y; qr[q].opt = 3; qr[q].id = q;}

	scanf("%d",&n); for(int i=1; i<=n; i++) {int x,y; scanf("%d%d",&y,&x); q++; qr[q].x = x; qr[q].y = y; qr[q].opt = 4; qr[q].id = q;}

	sort(qr+1,qr+q+1); int j = q;

	for(int i=1; i<=q; i++) id[qr[i].id] = i;

	s.insert(C+1);

	for(int i=C; i>=1; i--)

	{

		while(j>0 && qr[j].x==i)

		{

			if(qr[j].opt==2)

			{

				int k = id[qr[j].id+1]; int xx = qr[k].x,yy = qr[k].y,x = i,y = qr[j].y;

				if(y>1)

				{

					int cur = getval(y-1)-qr[k].ans;

					sgt.modify(1,1,C,y-1,y-1,cur);

				}

				sgt.modify(1,1,C,y,yy,0);

				s.erase(y); if(yy<C) s.erase(yy+1);

			}

			else if(qr[j].opt==1)

			{

				int k = id[qr[j].id-1]; int x = qr[k].x,y = qr[k].y,xx = i,yy = qr[j].y;

				if(y>1)

				{

					int cur = getval(y-1);

					sgt.modify(1,1,C,y-1,y-1,cur);

				}

				if(yy<C) qr[j].ans = getval(yy+1);

				sgt.modify(1,1,C,y,yy,0);

				s.insert(y); if(yy<C) s.insert(yy+1);

			}

			else if(qr[j].opt==3)

			{

				sgt.addval(1,1,C,qr[j].y,1);

			}

			else if(qr[j].opt==4)

			{

				qr[j].ans = getval(qr[j].y);

			}

			j--;

		}

	}

	sort(qr+1,qr+q+1,cmp_id);

	for(int i=1; i<=q; i++) {if(qr[i].opt==4) printf("%d\n",qr[i].ans);}

	return 0;

}

中考超QDEZ线\(32\)分，心里最大的一块石头终于落地了……

巴特西

BZOJ 4422 Cow Confinement (线段树、DP、扫描线、差分)

代码

最新文章

热门文章