题解：AT_abc421_f [ABC421F] Erase between X and Y

· · 题解

CF 做不进去的蒟蒻先把这题题解写了。

这是把我送进水名的题目。也是我切过的 kenkoooo 分最高的 AtCoder 题。

首先考虑 x 一定在 y 前面的做法。

因为加入的数不重，所以一定可以记录每一个数的前驱后继。每一个数都只会被删除一次，所以一定是 O(n) 的。

回到原问题，需要记录 x 和 y 的相对顺序。一个重大结论在于：删数不影响不被删的数的相对顺序。此算法需要离线。

先忽略掉所有的删除操作。把数全部加进去，看数在链表的哪一个位置，得到 x 和 y 的相对顺序，然后转化成 x 在 y 前的情况。

时间复杂度 O(n)。

#include<bits/stdc++.h>
#define int long long
#define mp(a,b) make_pair(a,b)
using namespace std;

int q;
int nxt[5*114514],lst[5*114514];

int place[5*114514];    //代表不删除序列的元素顺序！ 

int op[5*114514];
int x[5*114514],y[5*114514],z[5*114514];
signed main(){
    cin>>q;
    nxt[0]=q+1,lst[q+1]=0;  //代表节点  
    for(int i=1;i<=q;i++){
        cin>>op[i];
        if(op[i]==1){
            cin>>x[i];
            int lst1=x[i],nxt1=nxt[x[i]];   //代表未来节点的位置 
            nxt[lst1]=i,lst[i]=lst1;
            lst[nxt1]=i,nxt[i]=nxt1;    //代表现在的位置  
        }
        else{
            cin>>y[i]>>z[i]; 
        } 
        int now=0;
        // cout<<'!';
        // while(now!=q+1){
        //     cout<<now<<' ';
        //     now=nxt[now];
        // }
        // cout<<endl;
    }
    int now=0;
    place[now]=1;
    int ptr=1;
    while(now!=q+1){
        now=nxt[now];
        ptr++;
        place[now]=ptr;
        // cout<<now<<' ';
    }
 //    for(int i=0;i<=q;i++){
 //        cout<<'#'<<i<<' '<<place[i]<<endl;
 //    }
    // cout<<endl;
    for(int i=0;i<=q;i++){
        nxt[i]=lst[i]=0;    //更新位置！ 离线做法的精髓！  
    } 
    nxt[0]=q+1,lst[q+1]=0;
    for(int i=1;i<=q;i++){
        if(op[i]==1){
            int lst1=x[i],nxt1=nxt[x[i]];   //代表未来节点的位置 
            nxt[lst1]=i,lst[i]=lst1;
            lst[nxt1]=i,nxt[i]=nxt1;    //代表现在的位置  
        }
        else{
            int st=y[i],ed=z[i];
            // cout<<st<<' '<<ed<<endl;
            // cout<<place[st]<<' '<<place
            if(place[st]>place[ed]) swap(st,ed);    //精髓！
            int now=nxt[st];
            int include13=0;
            // cout<<st<<' '<<ed<<endl;
            while(now!=ed){
                int nxt1=nxt[now],lst1=lst[now];
                nxt[lst1]=nxt1,lst[nxt1]=lst1;
                include13+=now;
                nxt[now]=lst[now]=0; 
                now=nxt1;   //代表目前的情况  
            } 
            cout<<include13<<endl;
        } 
        int now=0;
        // cout<<"不朽！"<<' ';
        // while(now!=q+1){
        //  cout<<now<<' ';
        //  now=nxt[now];
        // } 
        // cout<<endl;
    } 
    cout<<endl;
    return 0;
} //一定要挽回罗琪钧的遗憾啊，一定会挽回罗琪钧的遗憾的！