自动搬运

查看原文

来自洛谷，原作者为

	zifanwang RP++

搬运于2025-08-24 22:38:25，当前版本为作者最后更新于2022-10-27 21:30:08，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

首先对于每一个矩形，若 $x_2<0$，就将 $x_1,x_2$ 均乘上 $-1$ 再交换，对于 $y_1,y_2$ 也做同样的操作。

我们建立一个操作序列 a[0~1000]，和一个数组 $d$，每一个操作用 $(x,y)$ 表示，就是在 $d$ 内把所有 $0$ 到 $x$ 的位置加上 $y$。

我们再定义一种新的操作 $[x,y,z]$，表示对于每一个 $0\le i\le x$ 都在 a[i] 处插入一个操作 $(y,z)$。

我们定义一种行为 $\{i,x_1,x_2,z\}$，表示执行：

• 若 $x_1<0$，就执行三个操作操作 $[i,-x_1,z],[i,x_2,z],[i,0,-z]$
• 若 $x_1=0$，就执行操作 $[i,x_2,z]$
• 若 $x_1>0$，就执行两个操作 $[i,x_2,z],[i,x_1-1,-z]$

下面对于每一个矩形的 $y_1,y_2$ 进行分类：

• 若 $y_1<0$，执行行为 $\{-y_1,x_1,x_2,1\},\{y_2,x_1,x_2,1\},\{0,x_1,x_2,-1\}$
• 若 $y_1=0$，执行行为 $\{y_2,x_1,x_2,1\}$
• 若 $y_1>0$，执行行为 $\{y_2,x_1,x_2,1\},\{y_1-1,x_1,x_2,-1\}$

因为询问的时间是单调递增的，可以记录一个时间 $t$，表示当前是 $t$ 时刻，初始化 $t=-1$。对于每一个询问 $k$，重复下面的操作直到 $t=k$：

• 将 $t+1$，然后执行 a[t] 的所有操作。

最后的答案就对于每一个 $0\le i\le k$，$d$ 数组内第 $i$ 个位置对应的值的和，可以用树状数组维护 $d$。但是这只能过掉 $|y_1|,|y_2|\le 1000$ 的数据。

正解

我们发现要执行的操作 $[x,y,z]$ 的数量是不多的。

再经过仔细思考，可以发现 $t$ 时刻的答案就是对于所有 $[x,y,z]$，$(\min(x,t)+1)(\min(y,t)+1)\times z$ 的和。详细的原因可以看看题解的末尾。

我们先不执行这些操作，把这些操作插入到一个集合 $S$，然后维护四个值 sum,add,ans,addans：

• sum 表示所有 $y>t$ 的操作 $[x,y,z]$ 的 $z\times(\min(x,t)+1)$ 的和。

• add 表示 $t$ 每怎加 $1$ 时 sum 要增加的值，也就是所有 $y>t\land x>t$ 的操作 $[x,y,z]$ 的 $z$ 的和。

• ans 表示所有 $y\le t$ 的操作 $[x,y,z]$ 对答案的贡献。

• addans 表示 $t$ 每怎加 $1$ 时 ans 要增加的值，也就是所有 $y\le t\land x>t$ 的操作 $[x,y,z]$ 的 $z\times(y+1)$ 的和。

我们建立一个 $dl$ 数组，对于每一个操作 $[x,y,z]$ 在 dl[x+1] 处插入。

当 $t$ 每次增加 $1$ 时，枚举所有 dl[t] 内的操作 $[x,y,z]$：

• 若此操作已经在集合 $S$ 内被删除了（也就是在这次询问之前 $y\le t$），就把 addans 减去 $z\times(y+1)$。

• 若此操作还在集合 $S$ 内（也就是在这次询问之前 $y>t$），就把 add 减去 $z$。

直到 $t=k$ 时 $t$ 才停止增加，下面再更新集合 $S$。枚举所有满足 $y\le k$ 的操作 $[x,y,z]$：

• 若 $x\ge k$，说明此操作还在未在上面的 dl 数组中被访问过，此时 sum 要减去 $z\times(k+1)$，add 减去 $z$，ans 加上 $z\times (k+1)(y+1)$，addans 加上 $z\times (y+1)$。

• 若 $x<k$，把 sum 减去 $z\times (x+1)$，ans 加上 $z\times (x+1)(y+1)$。

最终的答案就是 $(t+1)\times sum+ans$。

代码：

#include<bits/stdc++.h>
#define ll long long
#define mxn 1000003
#define md 1000000007
#define pb push_back
#define mkp make_pair
#define rep(i,a,b) for(int i=a;i<=b;++i)
#define rept(i,a,b) for(int i=a;i<b;++i)
#define drep(i,a,b) for(int i=a;i>=b;--i)
using namespace std;
inline int read(){
	int x=0;bool flag=true;char ch=getchar();
	while(!isdigit(ch)){if(ch=='-')flag=false;ch=getchar();}
	while(isdigit(ch))x=(x<<1)+(x<<3)+(ch^48),ch=getchar();
	return flag?x:-x;
}
struct node{
	int x,y,z;
};
inline bool operator<(node x,node y){
	return x.y!=y.y?x.y<y.y:x.x!=y.x?x.x<y.x:x.z<y.z;
}
int n,m,t=-1;
vector<node>dl[mxn];
multiset<node>s;
ll sum,add,ans,ads;
void puta(int x,int y,int z){
	add+=z;
	s.insert({x,y,z});
	dl[x+1].pb({x,y,z});
}
void ins(int x,int l,int r,int y){
	if(l<0){
		puta(x,-l,y);
		puta(x,r,y);
		puta(x,0,-y);
	}else if(l==0){
		puta(x,r,y);
	}else{
		puta(x,r,y);
		puta(x,l-1,-y);
	}
}
signed main(){
	n=read();
	for(int i=0,x1,x2,y1,y2;i<n;++i){
		x1=read(),y1=read(),x2=read(),y2=read();
		if(x1<0&&x2<0){
			swap(x1,x2);
			x1=-x1,x2=-x2;
		}
		if(y1<0&&y2<0){
			swap(y1,y2);
			y1=-y1,y2=-y2;
		}
		if(y1<0){
			ins(-y1,x1,x2,1);
			ins(y2,x1,x2,1);
			ins(0,x1,x2,-1);
		}else if(y1==0){
			ins(y2,x1,x2,1);
		}else{
			ins(y2,x1,x2,1);
			ins(y1-1,x1,x2,-1);
		} 
	}
	m=read();
	int x;
	while(m--){
		x=read();
		while(t<x){
			t++;
			for(node i:dl[t]){
				auto it=s.find(i);
				if(it==s.end())ads-=i.z*(i.y+1ll);
				else add-=i.z;
			}
			sum+=add;
			ans+=ads;
		}
		while(s.size()&&(s.begin()->y)<=x){
			node i=*s.begin();s.erase(s.begin());
			if(i.x>=x){
				sum-=i.z*(x+1ll);
				add-=i.z;
				ans+=i.z*(i.y+1ll)*(x+1ll);
				ads+=i.z*(i.y+1ll);
			}else{
				sum-=i.z*(i.x+1ll);
				ans+=(i.x+1ll)*(i.y+1ll)*i.z;
			}
		}
		printf("%lld\n",sum*(x+1ll)+ans);
	}
	return 0;
}

问题：为什么 $t$ 时刻的答案就是对于所有 $[x,y,z]$，$(\min(x,t)+1)(\min(y,t)+1)\times z$ 的和。

题目要求的就是一个左下角为 $(-k,-k)$，右上角为 $(k,k)$ 的大矩形和一些其他的矩形的交的面积之和。

因为最终的答案是所有 $t\le k$ 时的 $d$ 数组内的第 $0$ 到 $i$ 个位置对应的值的总和，操作 $[x,y,z]$ 就可以转化成一个左下角是 $(0,0)$，右上角是 $(x,y)$，权值为 $z$ 的矩形。

答案就是一个左下角是 $(0,0)$，右上角是 $(k,k)$ 的大矩形和每一个 $[x,y,z]$ 对应的矩形的交的面积乘以 $z$ 的和。