bzoj 4822: [Cqoi2017]老C的任务【扫描线+树状数组+二维差分】

一个树状数组能解决的问题分要用树套树……还写错了我别是个傻子吧？

这种题还是挺多的，大概就是把每个矩形询问差分拆成四个点前缀和相加的形式(x1-1,y1-1,1)(x2.y2,1)(x1-1,y2,-1)(x2,y1-1,-1)，然后离散化，打上id丢去按x排序，点也按x排序。

然后按照x扫描，树状数组维护到当前x坐行标前缀和的y，每次先把坐标等于x的点加进树状数组，然后查询乘上相应权值（+-1）加到相应id的ans数组里

#include<iostream>

#include<cstdio>

#include<algorithm>

#include<map>

using namespace std;

const int N=500005;

int n,m,x[N],tx,hax,y[N],ty,hay,con;

long long ans[N],t[N<<2];

map<int,int>hx,hy;

struct qwe

{

	int x,y,id;

	long long p;

	qwe(int X=0,int Y=0,long long P=0,int ID=0)

	{

		x=X,y=Y,p=P,id=ID;

	}

}p[N],q[N<<2];

bool cmp(const qwe &a,const qwe &b)

{

	return a.x<b.x;

}

int read()

{

	int r=0,f=1;

	char p=getchar();

	while(p>'9'||p<'0')

	{

		if(p=='-')

			f=-1;

		p=getchar();

	}

	while(p>='0'&&p<='9')

	{

		r=r*10+p-48;

		p=getchar();

	}

	return r*f;

}

int lb(int x)

{

	return x&(-x);

}

void update(int x,int v)

{

	for(int i=x;i<=hay;i+=lb(i))

		t[i]+=v;

}

long long ques(int x)

{

	long long re=0;

	for(int i=x;i>0;i-=lb(i))

		re+=t[i];

	return re;

}

int main()

{

	n=read(),m=read();

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

	{

		p[i].x=read(),p[i].y=read(),p[i].p=read();

		x[++tx]=p[i].x,y[++ty]=p[i].y;

	}

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

	{

		int x1=read(),y1=read(),x2=read(),y2=read();

		if(x1>x2)

			swap(x1,x2);

		if(y1>y2)

			swap(y1,y2);

		x[++tx]=x1-1,x[++tx]=x2;

		y[++ty]=y1-1,y[++ty]=y2;

		q[++con]=qwe(x2,y2,1,i);

		q[++con]=qwe(x1-1,y1-1,1,i);

		q[++con]=qwe(x1-1,y2,-1,i);

		q[++con]=qwe(x2,y1-1,-1,i);

	}

	sort(x+1,x+1+tx);

	sort(y+1,y+1+ty);

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

		if(i==1||x[i]!=x[i-1])

			hx[x[i]]=++hax;

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

		if(i==1||y[i]!=y[i-1])

			hy[y[i]]=++hay;

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

		p[i].x=hx[p[i].x],p[i].y=hy[p[i].y];

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

		q[i].x=hx[q[i].x],q[i].y=hy[q[i].y];

	sort(p+1,p+1+n,cmp);

	sort(q+1,q+1+con,cmp);

	int w1=1,w2=1;

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

	{

		while(w1<=n&&p[w1].x==i)

		{

			update(p[w1].y,p[w1].p);

			w1++;

		}

		while(w2<=con&&q[w2].x==i)

		{

			ans[q[w2].id]+=q[w2].p*ques(q[w2].y);

			w2++;

		}

	}

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

		printf("%lld\n",ans[i]);

	return 0;

}

巴特西

bzoj 4822: [Cqoi2017]老C的任务【扫描线+树状数组+二维差分】

最新文章

热门文章