ABC371F 题解

KSCD_ · 2024-09-15 07:51:05 · 题解

思路

发现由于移动时不能让两人在同一位置，所以所有人的相对顺序不会改变，同时移动时若旁边已经有人，还可能需要带上别的人一起动。

考虑把相邻的人看成一个整块一起移动，初始每个人各为一个块，移动时暴力向目标方向走，接上下一个块就合成一个整块接着走，直到到达终点。

具体维护时可以在 set 中维护 (p_i,x_i) 表示一个从 p_i 开始的整块，此时 p_i 的位置为 x_i。每个块的右端点和长度可以结合下一个块的左端点来计算，具体操作还是看代码实现吧。

时间复杂度上由于每次操作只可能从一个整块中分出一个含 T_i 的小块，总块数不超过 S=N+Q，合并的次数不超过总块数，所以时间复杂度是 O(S\log S) 的。

代码

#include<iostream>
#include<set>
#define int long long
#define pii pair<int,int>
using namespace std; 
const int N=4e5+10;
const int inf=1e18;
int n,Q,res;
set <pii> s;
signed main()
{
    ios::sync_with_stdio(false),cin.tie(0),cout.tie(0);
    cin>>n;
    for(int i=1,x;i<=n;i++) cin>>x,s.insert({i,x});
    s.insert({0,-inf}),s.insert({n+1,inf}),cin>>Q; // 处理边界 
    while(Q--)
    {
        int p,to; cin>>p>>to;
        pii te=*--s.upper_bound({p,inf}); s.erase(te); // p 所在的整块 
        int lp=te.first,lx=te.second,nowx=lx+(p-lp),nlp=(*s.upper_bound(te)).first; // lp 为左端点人的编号，lx 为位置 
        if(to<nowx) // 向左走 
        {
            if(p+1!=nlp) s.insert({p+1,nowx+1}),nlp=p+1; // 拆块 
            to-=(p-lp); //转化为左端点移动到的位置 
            while(lx!=to)
            {
                pii tt=*(--s.upper_bound({lp,lx})); // 左边的块 
                int tp=tt.first,tx=tt.second,lim=tx+(lp-tp),tto=max(to,lim);
                res+=(nlp-lp)*(lx-tto),lx=tto;  
                if(lx==lim) s.erase(tt),to-=(lp-tp),lp=tp,lx=tx; // 合并 
            }
        }
        else //向右走 
        {
            if(p!=lp) s.insert({lp,lx}),lp=p,lx=nowx; // 拆块 
            while(lx!=to)
            {
                pii tt=*(s.upper_bound({lp,lx})); // 右边的块 
                int np=tt.first,nx=tt.second,lim=nx-(np-lp),tto=min(to,lim);
                res+=(np-lp)*(tto-lx),lx=tto;
                if(lx==lim) s.erase(tt); // 合并 
            }
        }
        s.insert({lp,lx}); //把目前的块重新加入集合 
    }
    cout<<res;
    return 0;
}