P8363

线段树维护历史版本和做法。

首先注意到我们可以每次只保留矩形中 $x\in[0,+\infty],y\in[1,+\infty]$ 的部分，做四遍，每做一边旋转坐标系（即 $(x,y)\to(-y,x)$）再继续做。

然后考虑这个问题怎么解决。发现操作就形如矩形加，矩形查。于是考虑套路扫描线。把 $x$ 轴转化成时间，则变成了要求维护两个操作：

• 区间加减 $1$。

• 求一个区间的历史和。

上维护历史和的线段树。但是如果简单地用矩阵维护大概率是会被卡常的（$\omega=3$），于是考虑直接打 tag。

这里大致讲一下怎么维护。

对于线段树上每个节点维护一个（也许要叫半群？）五元组 $(len,s,hs,ad,hd,t)$，表示区间大小（注意每个区间要左闭右开处理），当前区间和，区间历史和，当前区间加 tag ，历史（上一次更新后）tag 和，距上一次更新的时间。考虑怎么下传标记 $(s',hs',ad',hd',t')$。

• $s\to s+ad'\times len,ad\to ad+ad',t\to t+t'$。这三个是显然的，和一般线段树没有什么区别。

• $hs\to hs+t'\times s+hd'\times len$。$hs$ 是原来历史和，$'t\times s$ 表示如果没有修改，经过 $t'$ 的时间 $hs$ 的新增值。$'hd\times len$ 则表示这段时间内的所有还未传下的 tag 对 $hs$ 的影响量之和。

• $hd\to hd+t'\times ad+hd'$。和上面的类似，只是不用 $\times len$。

于是就可以处理 pushdown 和打 tag 了。pushup 就是平凡的 $s,hs$ 相加。

于是就做完了。总时间复杂度是 $O((n+m)\log(n+m))$，大概带 $20$ 倍常数，不过还是跑得不慢的。但是 4kb。

code：

bool Mbe;
int n,m,s,t,d[N],c[N];
ll ans[N];
struct node{
	int x,l,r,op;
}b[N];
struct Node{
	int x1,y1,x2,y2;
}a[N];
struct Tnode{
	int len;ll s,hs;int ad;ll hd;int t;
	Tnode(int _len=0,ll _s=0,ll _hs=0,int _ad=0,ll _hd=0,int _t=0):len(_len),s(_s),hs(_hs),ad(_ad),hd(_hd),t(_t){}
	Tnode operator+(const Tnode &rhs)const{
		Tnode r;
		r.len=len+rhs.len;
		r.s=s+rhs.s;
		r.hs=hs+rhs.hs;
		return r;
	}
	Tnode operator*(const Tnode &rhs)const{
		Tnode r;
		r.len=len;
		r.s=s+rhs.ad*len;
		r.hs=hs+rhs.t*s+rhs.hd*len;
		r.ad=ad+rhs.ad;
		r.hd=hd+rhs.t*ad+rhs.hd;
		r.t=t+rhs.t;
		return r;
	}
};
struct SGT{
	Tnode tr[N<<2];
	il void pushup(int o){
		tr[o]=tr[o<<1]+tr[o<<1|1];
	}
	il void pushdown(int o){
		tr[o<<1]=tr[o<<1]*tr[o],tr[o<<1|1]=tr[o<<1|1]*tr[o];
		tr[o].ad=tr[o].hd=tr[o].t=0;
	}
	void build(int l,int r,int o){
		if(l==r){
			tr[o].len=l==t?0:d[l+1]-d[l];
			return;
		}
		int mid=(l+r)>>1;
		build(l,mid,o<<1),build(mid+1,r,o<<1|1);
		pushup(o);
	}
	void update(int l,int r,int o,int x,int y,int k){
		if(x>y){
			return;
		}
		if(l>=x&&r<=y){
			tr[o]=tr[o]*Tnode(0,0,0,k,0,0);
			return;
		}
		pushdown(o);
		int mid=(l+r)>>1;
		if(x<=mid){
			update(l,mid,o<<1,x,y,k);
		}
		if(y>mid){
			update(mid+1,r,o<<1|1,x,y,k);
		}
		pushup(o);
	}
	ll query(int l,int r,int o,int x,int y){
		if(r<x||l>y){
			return 0;
		}
		if(l>=x&&r<=y){
			return tr[o].hs;
		}
		pushdown(o);
		int mid=(l+r)>>1;
		return query(l,mid,o<<1,x,y)+query(mid+1,r,o<<1|1,x,y);
	}
}T;
il void add(int x1,int x2,int y1,int y2){
	if(x1>x2){
		swap(x1,x2);
	}
	if(y1>y2){
		swap(y1,y2);
	}
	x1=max(x1,0),x2=max(x2,-1);
	y1=max(y1,1),y2=max(y2+1,1);
	b[++s]=(node){x1,y1,y2,0},b[++s]=(node){x2+1,y1,y2,-1};
	d[++t]=y1,d[++t]=y2;
}
il bool cmp(node x,node y){
	return x.x!=y.x?x.x<y.x:x.op<y.op;
}
void Yorushika(){
	scanf("%d",&n);
	rep(i,1,n){
		scanf("%d%d%d%d",&a[i].x1,&a[i].y1,&a[i].x2,&a[i].y2);
	}
	scanf("%d",&m);
	rep(i,1,m){
		scanf("%d",&c[i]);
	}
	rep(Time,0,3){
		s=t=0;
		rep(i,1,n){
			add(a[i].x1,a[i].x2,a[i].y1,a[i].y2);
			swap(a[i].x1,a[i].y1),a[i].x1*=-1;
			swap(a[i].x2,a[i].y2),a[i].x2*=-1;
		}
		rep(i,1,m){
			b[++s]=(node){c[i],1,c[i]+1,i},d[++t]=c[i]+1;
		}
		d[++t]=1;
		sort(d+1,d+t+1),t=unique(d+1,d+t+1)-d-1;
		rep(i,1,t*4){
			T.tr[i]=Tnode();
		}
		rep(i,1,s){
			b[i].l=lower_bound(d+1,d+t+1,b[i].l)-d;
			b[i].r=lower_bound(d+1,d+t+1,b[i].r)-d;
		}
		sort(b+1,b+s+1,cmp);
		T.build(1,t,1);
		rep(i,1,s){
			T.tr[1]=T.tr[1]*Tnode(0,0,0,0,0,b[i].x-b[i-1].x-1);
			int j=i;
			while(j<=s&&b[j].x==b[i].x&&b[j].op<=0){
				T.update(1,t,1,b[j].l,b[j].r-1,b[j].op*2+1);
				j++;
			}
			T.tr[1]=T.tr[1]*Tnode(0,0,0,0,0,1);
			while(j<=s&&b[j].x==b[i].x){
				ans[b[j].op]+=T.query(1,t,1,1,b[j].r-1);
				j++;
			}
			i=j-1;
		}
	}
	rep(i,1,m){
		printf("%lld\n",ans[i]);
	}
}
bool Med;
signed main(){
	cerr<<(&Mbe-&Med)/1048576.0<<'\n';
	int t=1;
	//	scanf("%d",&t);
	while(t--)
		Yorushika();
}