本文章由 WyOJ Shojo 从洛谷专栏拉取，原发布时间为 2024-08-04 08:43:41

题目链接

abc365_g

思路

类似于扫描线，只不过不需要用线段树，因为每次只用查询两个人，所以直接模拟两个人进出房间的状态和进出的时间。

实现

用 $vector$ 存下所有人各自的操作，对于每一次询问直接暴力找时间最早的未完成操作，更改标记，计算同时在场的时间即。加上记忆化，防止反复询问同一组人。

代码

#include<bits\/stdc++.h>
#define int long long
using namespace std;
int n,m,q;
vector<int> v[200005];
unordered_map<int,int> mp[200005],vis[200005];
\/\/用unordered_map会更快
int ask(int x,int y){
	if(vis[x][y]==1) return mp[x][y];\/\/记忆化
	int sum=0,i=0,j=0,flag=0,flagg=0,pos=0;
	while(i!=v[x].size()&&j!=v[y].size()){\/\/两人都没有操作结束
		\/\/根据扫描线思路，优先操作时间更早的
		if(v[x][i]<v[y][j]){
			if(flag==1){
				if(flagg==1) sum+=v[x][i]-pos;
				pos=v[x][i];
				flag=0;
			}
			else {
				flag=1;
				pos=v[x][i];
			}i++;
		}
		else {
			if(flagg==1){
				if(flag==1) sum+=v[y][j]-pos;
				pos=v[y][j];
				flagg=0;
			}
			else  {
				flagg=1;
				pos=v[y][j];
			}j++;
		}
	}
	mp[x][y]=sum;
	vis[x][y]=1;
	\/\/不要直接把mp当成标记，如果两人没有同时出现的话，会被当成没有计算过，导致记忆化无效
	
	return sum;
}
signed main(){
 	ios::sync_with_stdio(false),cin.tie(0),cout.tie(0);
 	\/\/cin与cout优化
	cin>>n>>m;
	for(int i=1,t,x;i<=m;i++){
		cin>>t>>x;
		v[x].emplace_back(t);
		\/\/据说emplace比push快
	} 
	cin>>q;
	for(int i=1,x,y;i<=q;i++){;
		cin>>x>>y;
		cout<<ask(x,y)<<"\n";
	} 
    return 0;
}

4656ms 的代码

关于时间复杂度

应该是 $O(q\sqrt m)$ 。

考虑卡这份代码，应该使 $\sqrt m$ 人的进出次数都为 $\sqrt m$ 次，考虑每一次都是不同的两个人（使记忆化不生效），这样每一次查询是 $(\sqrt m +\sqrt m)$ 次操作。具体我也不会证明，感性理解一下。

警示后人

给室友卡了一晚上常，不要忘了优化一下常数。