题解：P3587 [POI 2015 R2] 项链分割 Necklace partition

观察题目，容易发现第一问就是求有多少区间

[l,r]

满足

1 \le l \le r <n

且区间内的数的种类和区间外的数的种类没有交。

可以对右端点扫描线，考虑对于当前右端点

r

来说合法的左端点

l

需要满足什么要的条件：

如果 $x$ 同时在 $a_1 \sim a_r$ 和 $a_{r+1} \sim a_n$ 中出现，记 $L_x$ 为 $x$ 在 $a_1 \sim a_r$ 中最后一次出现的位置，则 $l$ 需要不小于 $\max \{L_x\}$ ， $\max \{L_x\}$ 可以在扫描线的同时用 set 维护。
如果 $x$ 只出现在 $a_1 \sim a_r$ 中，则 $l$ 要在 $x$ 第一次出现的位置的左边，可以用线段树维护，求出有多少位置符合要求即可。

第二问容易发现只要求出长度大于

\lfloor \frac{n}{2} \rfloor

的区间中长度最小的和长度小于等于

\lfloor \frac{n}{2} \rfloor

中长度最大的即可，那么线段树二分就行。

时间复杂度

\mathcal O(n \log n)

，代码：

CPP

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N=1e6+5;
int n,k,a[N],lst[N],pre[N],nxt[N],add[4*N],mn[4*N],cnt[4*N],ans2=1e9;
ll ans1;
set<int>s;
void push_down(int x){
	if(add[x]){
		add[2*x]+=add[x];
		add[2*x+1]+=add[x];
		mn[2*x]+=add[x];
		mn[2*x+1]+=add[x];
		add[x]=0;
	}
}
void push_up(int x){
	if(mn[2*x]<mn[2*x+1]) mn[x]=mn[2*x],cnt[x]=cnt[2*x];
	else if(mn[2*x]>mn[2*x+1]) mn[x]=mn[2*x+1],cnt[x]=cnt[2*x+1];
	else mn[x]=mn[2*x],cnt[x]=cnt[2*x]+cnt[2*x+1];
}
void build(int x,int l,int r){
	cnt[x]=r-l+1;
	if(l==r) return;
	int mid=(l+r)/2;
	build(2*x,l,mid);
	build(2*x+1,mid+1,r);
}
void modify(int x,int l,int r,int L,int R,int v){
	if(L>R) return;
	if(l>=L&&r<=R){
		add[x]+=v;
		mn[x]+=v;
		return;
	}
	push_down(x);
	int mid=(l+r)/2;
	if(L<=mid) modify(2*x,l,mid,L,R,v);
	if(R>mid) modify(2*x+1,mid+1,r,L,R,v);
	push_up(x);
}
pair<int,int>query(int x,int l,int r,int L,int R){
	if(L>R) return make_pair(114514,0);
	if(l>=L&&r<=R) return make_pair(mn[x],cnt[x]);
	push_down(x);
	int mid=(l+r)/2;
	if(R<=mid) return query(2*x,l,mid,L,R);
	if(L>mid) return query(2*x+1,mid+1,r,L,R);
	pair<int,int>a=query(2*x,l,mid,L,R),b=query(2*x+1,mid+1,r,L,R);
	if(a.first<b.first) return a;
	if(a.first>b.first) return b;
	return make_pair(a.first,a.second+b.second);
}
int queryl(int x,int l,int r,int h){
	if(mn[x]) return l-1;
	if(l==r){
		if(!mn[x]) return l;
		return l-1;
	}
	push_down(x);
	int mid=(l+r)/2;
	if(h<=mid) return queryl(2*x,l,mid,h);
	int ans=queryl(2*x+1,mid+1,r,h);
	if(ans>mid) return ans;
	return queryl(2*x,l,mid,h);
}
int queryr(int x,int l,int r,int h){
	if(mn[x]) return r+1;
	if(l==r){
		if(!mn[x]) return l;
		return l+1;
	}
	push_down(x);
	int mid=(l+r)/2;
	if(h>mid) return queryr(2*x+1,mid+1,r,h);
	int ans=queryr(2*x,l,mid,h);
	if(ans<=mid) return ans;
	return queryr(2*x+1,mid+1,r,h);
}
int main(){
	ios::sync_with_stdio(0);
	cin.tie(0);cout.tie(0);
	cin>>n>>k;
	for(int i=1;i<=n;i++){
		cin>>a[i];
		pre[i]=lst[a[i]];
		lst[a[i]]=i;
	}
	memset(lst,0,sizeof(lst));
	for(int i=n;i>=1;i--){
		nxt[i]=lst[a[i]];
		lst[a[i]]=i;
	}
	build(1,1,n);
	s.insert(0);
	for(int i=1;i<n;i++){
		if(pre[i]){
			modify(1,1,n,pre[i]+1,i,1);
			s.erase(pre[i]);
		}
		if(nxt[i]) s.insert(i);
		auto it=s.upper_bound(i);
		it--;
		pair<int,int>p=query(1,1,n,(*it)+1,i);
		if(!p.first){
			ans1+=p.second;
			int h=max(1,i-(n/2)+1),p1=0,p2=0;
			if(h>1){
				p1=queryl(1,1,n,h-1);
				if(p1&&p1>=(*it)+1) ans2=min(ans2,2*(i-p1+1)-n);
			}
			p2=queryr(1,1,n,max(h,(*it)+1));
			if(p2<=i) ans2=min(ans2,n-2*(i-p2+1));
		}
	}
	cout<<ans1<<" "<<ans2<<'\n';
	return 0;
}

题解：P3587 [POI 2015 R2] 项链分割 Necklace partition

文章操作

相关推荐

评论

题解：P3587 [POI 2015 R2] 项链分割 Necklace partition