J.2D Travel

题解

首先注意到两维可以独立求解。

据此考虑离线处理。对于每一维，令位置集 为所有当前处于位置 的询问形成的集合，我们记录总偏移量 ，位置集偏移量 ，询问偏移量 和每个询问 所属的位置集 ，同时记录当前边界 与 。

接下来对于从 到 每一次操作，我们依次进行如下处理：

1. 对于插入询问操作，我们将对应询问加入其所属的位置集 ，同时初始化其偏移量为 。
2. 更新操作对应的边界 与 。
3. 对于所有超出边界（即 或 ）的位置集，我们将其与 或 合并。
4. 对于查询询问操作，我们将询问 的位置更新为 ，同时将 的移动距离增加总偏移量 、位置集偏移量 与询问偏移量 之和 。

由于每次合并操作都会减少一个集合，因此采用启发式合并则有时间复杂度 。

代码

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;

const int N=200000;

int i,j,k,n,m,t;

int d[3][N+50],sz,pos[N+50],it;
ll cl,cr;
basic_string<int> q1[N+50],q2[N+50],v[N+50];

ll r[3][N+50],tot[N+50],w[N+50],w2[N+50],cur[N+50],pre;

unordered_map<ll,int> mp;
set<ll> s;

void hb(ll x,ll y){
	if(!mp.count(y)){
		mp[y]=++it;
		cur[it]=y; w[it]=-pre;
		s.insert(y);
	}
	int x1=mp[x],y1=mp[y];
	if(v[x1].size()>v[y1].size()){
		swap(x1,y1);
		w[y1]-=llabs(x-y);
		w[x1]+=llabs(x-y);
		cur[y1]=y; mp[y]=y1;
	}
	for(auto i:v[x1]){
		w2[i]+=w[x1]-w[y1]-llabs(x-y);
		pos[i]=y1;
	}
	v[y1]+=v[x1];
	mp.erase(x); s.erase(x); v[x1]={};
}

void work(int ty){
	mp={}; s={}; it=0; pre=0;
	cl=0; cr=(ty==1?n:m);
	for(i=1;i<=sz;i++){
		for(auto j:q1[i]){
			ll t1=r[ty][j]+cl;
			if(!mp.count(t1)){
				mp[t1]=++it; 
				cur[it]=t1; w[it]=-pre;
				s.insert(t1);
			}
			k=mp[t1]; v[k]+=j; pos[j]=k; w2[j]=-pre-w[k];
		}
		ll d1=llabs(d[ty][i]);
		pre+=d1;
		cl+=d[ty][i]; cr+=d[ty][i];
		while(!s.empty()){
			auto k=*s.begin();
			if(k<cl)hb(k,cl);
			else break;
		}
		while(!s.empty()){
			auto k=*s.rbegin();
			if(k>cr)hb(k,cr);
			else break;
		}
		for(auto j:q2[i]){
			r[ty][j]=cur[pos[j]]-cl;
			tot[j]+=w[pos[j]]+w2[j]+pre;
		}
	}
	memset(w,0,sizeof(w));
	memset(w2,0,sizeof(w2));
	for(i=1;i<=it;i++)v[i]={};
}

int main(){
	ios::sync_with_stdio(0); cin.tie(0);
	cin>>n>>m>>sz>>t;
	for(i=1;i<=sz;i++){
		string s;
		cin>>s>>k;
		if(s=="L")d[1][i]=k;
		if(s=="R")d[1][i]=-k;
		if(s=="U")d[2][i]=-k;
		if(s=="D")d[2][i]=k;
	}
	for(i=1;i<=t;i++){
		cin>>r[1][i]>>r[2][i]>>j>>k;
		q1[j]+=i;
		q2[k]+=i;
	}
	work(1); work(2);
	for(i=1;i<=t;i++)cout<<r[1][i]<<' '<<r[2][i]<<' '<<tot[i]<<'\n';
}