题解：AT_abc389_f [ABC389F] Rated Range

#include<bits/stdc++.h>
#define N 700010
using namespace std;
int n,m,sz[N],ls[N],rs[N],val[N],lasy[N],f[N];
unsigned int rd[N];
mt19937 rnd(time(0));
int root,cnt;
int g(int x,int y)
{
	sz[++cnt]=1,val[cnt]=x,rd[cnt]=rnd();
	f[cnt]=y;
	return cnt;
}
void upd(int p)
{
	sz[p]=sz[ls[p]]+sz[rs[p]]+1;
}
void pushdown(int p)
{
	if(lasy[p])
	{
		if(ls[p]) lasy[ls[p]]+=lasy[p],val[ls[p]]+=lasy[p];
		if(rs[p]) lasy[rs[p]]+=lasy[p],val[rs[p]]+=lasy[p];
		lasy[p]=0;
	}
}
void split(int p,int k,int &x,int &y)
{
	if(!p) {x=y=0;return ;}
	pushdown(p);
	if(k<val[p]) y=p,split(ls[p],k,x,ls[p]);
	else x=p,split(rs[p],k,rs[p],y);
	upd(p);
}
int merge(int x,int y)
{
	if(!x||!y) return x+y;
	if(rd[x]<rd[y])
	{
		pushdown(x);
		rs[x]=merge(rs[x],y);
		upd(x);
		return x;
	}
	else{
		pushdown(y);
		ls[y]=merge(x,ls[y]);
		upd(y);
		return y;
	}
}
void solve(int l,int r)
{
	int x,y;
	split(root,l-1,x,y);
	int u,v;
	split(y,r-l+1,u,v);
	lasy[u]^=1;
	root=merge(x,merge(u,v));
}
int l[N],r[N];
struct node{
	int val,id;
}h[N];
int ans[N];
void solve(int p)
{
	if(!p) return;
	pushdown(p);
	ans[f[p]]=val[p];
	print(ls[p]);
	print(rs[p]);
}
int main()
{
	ios::sync_with_stdio(false);
	cin.tie(0),cout.tie(0);
	cin>>n;
	for(int i=1;i<=n;i++) cin>>l[i]>>r[i];
	cin>>m;
	for(int i=1;i<=m;i++) cin>>h[i].val,h[i].id=i;
	sort(h+1,h+1+m,[&](node x,node y){return x.val<y.val;});
	for(int i=1;i<=m;i++) root=merge(root,g(h[i].val,h[i].id));
	for(int i=1;i<=n;i++){
		int x,y,z;
		split(root,l[i]-1,x,y);
		split(y,r[i],y,z);
		lasy[y]++,val[y]++;
		root=merge(x,merge(y,z));
	}
	solve(root);
	for(int i=1;i<=m;i++) cout<<ans[i]<<"\n";
	return 0;
}