ABC365_G

zibenlun · 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) 次操作。具体我也不会证明，感性理解一下。

警示后人

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