题解：AT_arc206_b [ARC206B] Slime Swap

· · 题解

思路

题目中说道的："可以将所有史莱姆按大小升序排列"，我们会发现，如果同一种颜色的路径有交叉，那么就不可以完成排列。我们需要拎出来路径没有交叉的所有点，即是相同颜色的 P_i 的最长上升子序列（如果有下降一定会有交叉）。

那么我们对每个颜色求一下 LIS，时间复杂度 O(n\log n)。（咱的代码实现上有点小问题，每次开长度为 n 的 vector 理论最坏可以达到 O(n^2) 的时间复杂度，正确做法是将同种颜色的 P_i 进行离散化，这样总共只会开 O(n) 个元素，开 vector 的时间复杂度为 O(n)。）

#include<bits/stdc++.h>

#define pii pair<int,int> 
#define pll pair<long long,long long> 
#define ll long long
#define i128 __int128

#define mem(a,b) memset((a),(b),sizeof(a))
#define m0(a) memset((a),0,sizeof(a))
#define m1(a) memset(a,-1,sizeof(a))
#define lb(x) ((x)&-(x))
#define lc(x) ((x)<<1)
#define rc(x) (((x)<<1)|1)
#define pb(G,x) (G).push_back((x))
#define For(a,b,c) for(int a=(b);a<=(c);a++)
#define Rep(a,b,c) for(int a=(b);a>=(c);a--)
#define in1(a) a=read()
#define in2(a,b) a=read(), b=read()
#define in3(a,b,c) a=read(), b=read(), c=read()
#define in4(a,b,c,d) a=read(), b=read(), c=read(), d=read()
#define fst first 
#define scd second 
#define dbg puts("IAKIOI")

using namespace std;

int read() {
    int x=0,f=1; char c=getchar();
    for(;c<'0'||c>'9';c=getchar()) f=(c=='-'?-1:1); 
    for(;c<='9'&&c>='0';c=getchar()) x=(x<<1)+(x<<3)+(c^48);
    return x*f;
}
void write(int x) { if(x>=10) write(x/10); putchar('0'+x%10); }

const int mod = 998244353;
int qpo(int a,int b) {int res=1; for(;b;b>>=1,a=(a*a)%mod) if(b&1) res=res*a%mod; return res; }
int inv(int a) {return qpo(a,mod-2); }

#define maxn 200050

int n,p[maxn],c[maxn];
vector<int> a[maxn];
struct Bit {
    void upd(int x,int val,vector<int>& c) {
        for(;x<(int)c.size();x+=lb(x)) c[x]=max(c[x],val);
    }
    int query(int x,vector<int>& c) {
        int res=0;
        for(;x;x-=lb(x)) res=max(res,c[x]);
        return res;
    }
}tr;

void work() {
    in1(n);
    For(i,1,n) in1(p[i]);
    For(i,1,n) {
        in1(c[i]);
        a[c[i]].push_back(p[i]);
    }
    ll ans=0;
    For(i,1,n) if(a[i].size()){
        vector<int> Tr(n+1);
        int res=0;
        For(j,0,(int)(a[i].size())-1) {
            int qwq=tr.query(a[i][j]-1,Tr)+1;
            res=max(res,qwq);
            tr.upd(a[i][j],qwq,Tr);
        }
//      cout<<i<<' '<<a[i].size()<<' '<<res<<'\n';
        ans+=(a[i].size()-res)*i*1ll;
    }
    cout<<ans;

}

signed main() {
//  freopen("data.in","r",stdin);
//  freopen("myans.out","w",stdout);
//  ios::sync_with_stdio(false); 
//  cin.tie(0); cout.tie(0);
    double stt=clock();
    int _=1;
//  _=read();
//  cin>>_;
    For(i,1,_) {
        work();
    }
    cerr<<"\nTotal Time is:"<<(clock()-stt)*1.0/1000<<" second(s)."<<'\n';
    return 0;
}