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

· · 题解

观察题目，容易发现第一问就是求有多少区间 [l,r] 满足 1 \le l \le r <n 且区间内的数的种类和区间外的数的种类没有交。

可以对右端点扫描线，考虑对于当前右端点 r 来说合法的左端点 l 需要满足什么要的条件：

  1. 如果 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 维护。
  2. 如果 x 只出现在 a_1 \sim a_r 中，则 l 要在 x 第一次出现的位置的左边，可以用线段树维护，求出有多少位置符合要求即可。

第二问容易发现只要求出长度大于 \lfloor \frac{n}{2} \rfloor 的区间中长度最小的和长度小于等于 \lfloor \frac{n}{2} \rfloor 中长度最大的即可，那么线段树二分就行。

时间复杂度 \mathcal O(n \log n)，代码：


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