题解：AT_arc214_e [ARC214E] Swap K times

· · 题解

前置操作：弱化版、离线二维数点。

好的现在默认大家已经会了弱化版，即会求最小值了。所以如果一个移动序列（记次数为 t）合法，记答案为 c，那么 t\equiv cK\pmod 2。完结撒花！了吗？

如果 N=3, K=99, A=(1,1,2), B=(2,1,1) 呢？此时易得 t=2，那么 c=2。但是我们可以操作完之后相邻的两个 1 换。所以答案是 c=1。那不是直接炸飞了吗？

那就不做了吧。

我们考虑交换一组相等的数 (l,r)。记映射数组（不记得看看弱化版）为 p。则对于 l\le i\le r（p_l<p_r）：

就是二维数点：左下角 (l,p_l)，右上角 (r,p_r) 数点数乘二加一（加上交换 (p_l,p_r) 带来的逆序对。但是 O(n^2)

考虑优化。

现在考虑优化对象。设同一个值在 A 里出现了三次，位置 l_1<l_2<l_3（p_{l_1}<p_{l_2}<p_{l_3}），那么 \operatorname{rectangle}((l_1,p_{l_1}),(l_2,p_{l_2}))\in\operatorname{rectangle}((l_1,p_{l_1}),(l_3,p_{l_3}))，则 \operatorname{pointsInRectangle}((l_1,p_{l_1}),(l_2,p_{l_2}))\le\operatorname{pointsInRectangle}((l_1,p_{l_1}),(l_3,p_{l_3}))。所以只需要统计相同颜色的相邻的就行。

然后求最小值就可以。

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
#define file(x)freopen(#x".in","r",stdin),freopen(#x".out","w",stdout)
const ll maxn=3e5+5;
class fenwick{
    ll n;
    vector<ll>a;
public:
    fenwick(ll _n):n(_n){a=vector<ll>(n+1);}
    fenwick(){n=3e5+5;a=vector<ll>(n+1);}
    void add(ll i,ll x){
        for(;i<=n;i+=(i&-i))a[i]+=x;
    }
    ll query(ll x){
        ll ans=0;
        while(x){ans+=a[x];x-=(x&-x);}
        return ans;
    }
};
ll n,k,q,T;
ll a[maxn],b[maxn],p[maxn],nxt[maxn];
array<ll,4>query[maxn<<1];
ll ans[maxn<<1],rnk[maxn];
queue<ll>Q[maxn];
ll getans(ll t){
    if((t&1)&&!(k&1)||t==LLONG_MAX/8)return LLONG_MAX;
    if(t&1){
        ll ans=(t+k-1)/k;
        if(ans&1)return ans;
        return ans+1;
    }else{
        ll ans=(t+k-1)/k;
        if(!(ans&1)||!(k&1))return ans;
        return ans+1;
    }
}
void solve(){
    cin>>n>>k;T=0;
    for(ll i=1;i<=n;i++)nxt[i]=0;q=0;
    for(ll i=1;i<=n;i++)cin>>a[i];
    for(int i=1;i<=n;i++)cin>>b[i],Q[b[i]].push(i);
    for(int i=1;i<=n;i++)rnk[p[i]=Q[a[i]].front()]=i,Q[a[i]].pop(),(Q[a[i]].size()?nxt[i]=Q[a[i]].front():0);
    for(int i=1;i<=n;i++){
        if(nxt[i]){
            ll r=rnk[nxt[i]];
            ++q;query[q]={i,r,p[r],q};ans[q]=0;
            ++q;query[q]={i,r,p[i],q};ans[q]=0;
        }
    }
    sort(query+1,query+1+q,[&](array<ll,4>x,array<ll,4>y){
        return x[1]<y[1];
    });// 数点
    fenwick x(n);
    for(int i=1;i<=q;i++){
        for(int j=query[i-1][1]+1;j<=query[i][1];++j)
            x.add(p[j],1);
        ans[query[i][3]]+=x.query(query[i][2]);
    }
    sort(query+1,query+1+q,[&](array<ll,4>x,array<ll,4>y){
        return x[0]<y[0];
    });
    x=fenwick(n);
    query[0][0]=1;
    for(int i=1;i<=q;i++){
        for(int j=query[i-1][0];j<query[i][0];++j)
            x.add(p[j],1);
        ans[query[i][3]]-=x.query(query[i][2]);
    }
    fenwick tree(n);// 求逆序对
    for(int i=n;i>=1;i--){
        T+=tree.query(p[i]-1);
        tree.add(p[i],1);
    }
    if(!q&&(T&1)&&!(k&1))cout<<"-1\n";
    else{
        ll tt=LLONG_MAX/8;
        for(ll i=1;i<=q;i+=2)
            tt=min(tt,T+2*(ans[i]-ans[i+1])-1);// 变奇偶性
        ll ans=min(getans(T),getans(tt));
        if(ans==LLONG_MAX)cout<<"-1\n";
        else cout<<min(getans(T),getans(tt))<<"\n";
    }
}
int main(){
    ios::sync_with_stdio(false);
    cin.tie(nullptr),cout.tie(nullptr);
    file(swap);
    int oT_To;
    for(cin>>oT_To;oT_To--;solve());
    return 0;
}