【BZOJ4822】[CQOI2017]老C的任务（扫描线）

时间：2022-01-24 03:53:59

【BZOJ4822】[CQOI2017]老C的任务（扫描线）

题面

BZOJ

洛谷

题解

没有修改操作，都不需要分治了。。。

直接排序之后扫描线算贡献就好了。。。

不知道为啥洛谷上过不了。。。

#include<iostream>

#include<cstdio>

#include<cstdlib>

#include<cstring>

#include<cmath>

#include<algorithm>

#include<vector>

using namespace std;

#define ll long long

#define MAX 100100

inline int read()

{

	int x=0;bool t=false;char ch=getchar();

	while((ch<'0'||ch>'9')&&ch!='-')ch=getchar();

	if(ch=='-')t=true,ch=getchar();

	while(ch<='9'&&ch>='0')x=x*10+ch-48,ch=getchar();

	return t?-x:x;

}

int n,m;

struct Node{int x,y,p;}p[MAX];

struct Qry{int l,r,x,opt,id;}q[MAX<<1];

bool operator<(Node a,Node b){return a.x<b.x;}

bool operator<(Qry a,Qry b){return a.x<b.x;}

int X[MAX<<2],Y[MAX<<2],tx,ty,tot;

int calcx(int x){return lower_bound(&X[1],&X[tx+1],x)-X;}

int calcy(int x){return lower_bound(&Y[1],&Y[ty+1],x)-Y;}

ll ans[MAX],c[MAX<<2];

int lb(int x){return x&(-x);}

void add(int x,int w){while(x<=ty)c[x]+=w,x+=lb(x);}

ll getsum(int x){ll ret=0;while(x)ret+=c[x],x-=lb(x);return ret;}

int main()

{

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

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

	{

		int x=read(),y=read(),P=read();

		X[++tx]=x;Y[++ty]=y;

		p[i]=(Node){x,y,P};

	}

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

	{

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

		q[++tot]=(Qry){y1,y2,x1,-1,i};

		q[++tot]=(Qry){y1,y2,x2,1,i};

		X[++tx]=x1;X[++tx]=x2;Y[++ty]=y1;Y[++ty]=y2;

	}

	sort(&X[1],&X[tx+1]);tx=unique(&X[1],&X[tx+1])-X-1;

	sort(&Y[1],&Y[ty+1]);ty=unique(&Y[1],&Y[ty+1])-Y-1;

	for(int i=1;i<=n;++i)p[i].x=calcx(p[i].x),p[i].y=calcy(p[i].y);

	for(int i=1;i<=tot;++i)q[i].x=calcx(q[i].x),q[i].l=calcy(q[i].l),q[i].r=calcy(q[i].r);

	sort(&p[1],&p[n+1]);sort(&q[1],&q[tot+1]);

	for(int i=1,j=0;i<=tot;++i)

	{

		while(j<n&&p[j+1].x<q[i].x)++j,add(p[j].y,p[j].p);

		if(q[i].opt==-1)ans[q[i].id]-=getsum(q[i].r)-getsum(q[i].l-1);

		while(j<n&&p[j+1].x<=q[i].x)++j,add(p[j].y,p[j].p);

		if(q[i].opt==1)ans[q[i].id]+=getsum(q[i].r)-getsum(q[i].l-1);

	}

	for(int i=1;i<=m;++i)printf("%lld\n",ans[i]);

	return 0;

}

相关文章