题解：P9310 [EGOI 2021] Luna likes Love / 卢娜爱磕 cp

LJN1117 · 2025-11-04 20:22:25 · 题解

贪心的从左向右更新，用链表连接节点。

若一个数第一次出现，记录其下标。否则，查询中间需经过多少数，并将两数从链表中删去，用线段树维护。

code：

#include<bits/stdc++.h>
#define int long long
#define maxn 500100

using namespace std;

int n;
int a[maxn<<1];
int nxt[maxn<<1],pre[maxn<<1];
int id[maxn<<1];
int ans=0;

struct tree{
    int l,r;
    int sum;
}tr[maxn<<3];

void push_up(int u){
    tr[u].sum=tr[u<<1].sum+tr[u<<1|1].sum;
}

void build(int u,int l,int r){
    tr[u].l=l,tr[u].r=r;
    if(l==r){
        tr[u].sum=1;
        return ;
    }
    int mid=(l+r)>>1;
    build(u<<1,l,mid);
    build(u<<1|1,mid+1,r);
    push_up(u);
}

void modify(int u,int x){
    if(tr[u].l==tr[u].r){
        tr[u].sum=0;
        return ;
    }
    int mid=(tr[u].l+tr[u].r)>>1;
    if(x<=mid) modify(u<<1,x);
    else modify(u<<1|1,x);
    push_up(u);
}

int query(int u,int l,int r){
    if(tr[u].l>=l && tr[u].r<=r) return tr[u].sum;
    int res=0;
    int mid=(tr[u].l+tr[u].r)>>1;
    if(l<=mid) res+=query(u<<1,l,r);
    if(r>mid) res+=query(u<<1|1,l,r);
    push_up(u);
    return res;
}

signed main(){
    // freopen("happy.in","r",stdin);
    // freopen("happy.out","w",stdout);
    ios::sync_with_stdio(false);
    cin.tie(0);cout.tie(0);
    cin>>n;
    build(1,1,2*n);
    for(int i=1;i<=2*n;i++) cin>>a[i];
    nxt[1]=2;pre[2*n]=n-1;
    for(int i=2;i<2*n;i++) pre[i]=i-1,nxt[i]=i+1;
    for(int i=1;i<=2*n;i++){
        int num=a[i];
        // cout<<i<<" "<<top<<"\n";
        if(!id[num]) id[num]=i;
        else{
            if(nxt[id[num]]==i){
                nxt[pre[id[num]]]=nxt[i];
                pre[nxt[i]]=pre[id[num]];
                modify(1,id[num]),modify(1,i);
                ans++;
            }
            else{
                int t=id[num];
                // cout<<query(id[num])<<" "<<t<<" "<<top<<" "<<num<<" +2\n";
                // cout<<top-t<<"\n";
                int tot=query(1,t,i);
                // cout<<t<<" "<<i<<" "<<tot<<"\n";
                pre[nxt[t]]=pre[t];
                nxt[pre[t]]=nxt[t];
                pre[nxt[i]]=pre[i];
                nxt[pre[i]]=nxt[i];
                modify(1,t);modify(1,i);
                ans+=tot-1;
                // cout<<ans<<"\n";
            }
        }
    }
    cout<<ans<<"\n";
    return 0;
}