题解：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)

。）

CPP

#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;
}

题解：AT_arc206_b [ARC206B] Slime Swap

文章操作

思路

相关推荐

评论

题解：AT_arc206_b [ARC206B] Slime Swap