自动搬运

查看原文

来自洛谷，原作者为

	starusc ~

搬运于2025-08-24 21:59:15，当前版本为作者最后更新于2020-11-11 20:36:26，作者可能在搬运后再次修改，您可在原文处查看最新版

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

以下是正文

线段树加扫描线维护答案的差分。加花单点加 1，查询后缀和。

加入右区间时把绿色点加上蓝色区域的值（实际上不是到底，而是到下一个栅栏）（因为我们新加入两条栅栏后就走不下来了），然后把橘色区域清零（会被栅栏挡住）。

删除左区间时把棕色区域清零（会被栅栏挡住），并在粉色点减去紫色区域的值（去掉两条栅栏后，粉色点可能先下后右，或先右后下，会算重，所以减掉去重）。

注意排序顺序：先右区间，然后左区间，然后加花，最后查询。

时间复杂度 $O(n\log n)$。

//starusc
#include<bits/stdc++.h>
using namespace std;
inline int read(){
	int x=0,f=1,c=getchar();
	while(!isdigit(c)){if(c=='-')f=-1;c=getchar();}
	while(isdigit(c)){x=(x<<1)+(x<<3)+(c^48);c=getchar();}
	return f==1?x:-x;
}
const int N=2e5+4,M=1e6+4,mx=1e6+1;
namespace seg{
	#define lc (p<<1)
	#define rc (p<<1|1)
	int t[M<<2],lz[M<<2];
	inline void pushdown(int p,int l,int r){
		if(!lz[p])return;
		lz[lc]=lz[rc]=1;
		t[lc]=t[rc]=0;
		lz[p]=0;
	}
	inline void pushup(int p){
		t[p]=t[lc]+t[rc];
	}
	void modify(int p,int l,int r,int x,int v){
		if(l==r){
			t[p]+=v;
			return;
		}
		pushdown(p,l,r);
		int mid=(l+r)>>1;
		if(x<=mid)modify(lc,l,mid,x,v);
		else modify(rc,mid+1,r,x,v);
		pushup(p); 
	}
	void cover(int p,int l,int r,int ql,int qr){
		if(ql<=l&&r<=qr){
			lz[p]=1;
			t[p]=0;
			return;
		}
		pushdown(p,l,r);
		int mid=(l+r)>>1;
		if(ql<=mid)cover(lc,l,mid,ql,qr);
		if(mid<qr)cover(rc,mid+1,r,ql,qr);
		pushup(p);
	}
	int query(int p,int l,int r,int ql,int qr){
		if(ql<=l&&r<=qr)return t[p];
		pushdown(p,l,r);
		int mid=(l+r)>>1;
		if(qr<=mid)return query(lc,l,mid,ql,qr);
		if(mid<ql)return query(rc,mid+1,r,ql,qr);
		return query(lc,l,mid,ql,qr)+query(rc,mid+1,r,ql,qr);
	}
	#undef lc
	#undef rc
}
struct ques{
	int x,yl,yr,id,op;
}q[N<<2];
inline bool comp(const ques &a,const ques &b){//op!顺序问题 
	if(a.x!=b.x)return a.x>b.x;
	return a.op<b.op;
}
int n,tot,ans[N],tmp[N];
multiset<int>s;
int main(){
	freopen("cow.in","r",stdin);
	freopen("cow.out","w",stdout);
	n=read();
	for(int i=1,a1,b1,a2,b2;i<=n;i++){
		a1=read();b1=read();a2=read();b2=read();
		q[++tot]=(ques){a2,b1,b2,i,1};
		q[++tot]=(ques){a1-1,b1,b2,-i,2};
	} 
	n=read();
	for(int i=1,x,y;i<=n;i++){
		x=read();y=read();
		q[++tot]=(ques){x,y,0,0,3};
	}
	n=read();
	for(int i=1,x,y;i<=n;i++){
		x=read();y=read();
		q[++tot]=(ques){x,y,i,0,4};
	}
	sort(q+1,q+tot+1,comp);
	s.insert(mx);
	for(int i=1,nxt;i<=tot;i++){
		if(q[i].id){
			if(q[i].id>0){
				nxt=(*s.upper_bound(q[i].yr));
				tmp[q[i].id]=seg::query(1,0,mx,q[i].yr+1,nxt);
				seg::modify(1,0,mx,q[i].yl-1,seg::query(1,0,mx,q[i].yl,nxt));
				seg::cover(1,0,mx,q[i].yl,q[i].yr);
				s.insert(q[i].yl-1);
				s.insert(q[i].yr);
			}
			else{
				seg::modify(1,0,mx,q[i].yl-1,-tmp[-q[i].id]);
				seg::cover(1,0,mx,q[i].yl,q[i].yr);
				s.erase(s.find(q[i].yl-1));
				s.erase(s.find(q[i].yr));
			}
		}
		else if(!q[i].yr){
			seg::modify(1,0,mx,q[i].yl,1);
		}
		else{
			nxt=(*s.lower_bound(q[i].yl));
			ans[q[i].yr]=seg::query(1,0,mx,q[i].yl,nxt);
		}
	}
	for(int i=1;i<=n;i++)cout<<ans[i]<<"\n";
	return (0-0);
}