自动搬运

查看原文

来自洛谷，原作者为

	Basori_Tiara 悪魔メイドVtuberの猫雷にゃるです！#猫雷art# 字幕组1156469150通知群710717783

搬运于2025-08-24 21:50:28，当前版本为作者最后更新于2023-10-12 15:06:42，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

P3587

容易发现，拉珠环是个烟雾弹，如果切两刀断成两段，一定有一段是原序列上的一段区间，所以你当一条拉珠上找合法区间就行了。

什么是合法区间呢？颜色为 $col$ 的点要么全在这里面要么全不在这里面。

我们考虑怎么做这个，你首先枚举一个右端点 $rt$，然后看哪些左端点满足条件。

对于一种颜色 $i$，假设他的最左在 $st_i$，最右在 $ed_i$，那么有两种情况：

1. $ed_i>rt$，那么第 $i$ 种颜色不要碰，因为不管怎么选左端点区间都没办法包含所有这种颜色，这个可以用栈维护距离 $rt$ 最近的编号，设为 $lt$，那么 $[lt+1,rt]$ 是本限制下备选区间。
2. $ed_i\leqslant rt$，那么对于第 $i$ 种颜色，左端点不可以放在 $[st_i+1,ed_i]$ 的位置，原因显然，如果这样的话就一定包住了最后一个没包住第一个，然后就不合法了，你考虑开一棵区间赋值区间求和的线段树，每次遇到这种情况就区间打个不能走的标记。

然后这两个限制加起来，我们就能求出第一问的答案，那就是在区间 $[lt+1,rt]$ 中找到线段树中没有标记的点的数量。

第二问怎么求？首先把最优的左节点找出来，直接把长度拉到 $\frac{n}{2}$ 就可以了，然后考虑线段树二分出离那个点最近的可用点，把那个记入答案即可。

#include<bits/stdc++.h>
#define int long long
using namespace std;
int n,k;
int a[1000005];
int st[1000005];
int ed[1000005];
bool vis[1000005];
stack<int> stk;
bool tag[1000005];
class SegTree{
    public:
    int Tree[1000005<<2];
    int Tag[1000005<<2];
    void pushup(int cur){
        Tree[cur]=Tree[cur<<1]+Tree[cur<<1|1];
        return;
    }
    void addtag(int cur,int lt,int rt,int val){
        Tree[cur]=(rt-lt+1)*val;
        Tag[cur]=val;
        return;
    }
    void pushdown(int cur,int lt,int rt){
        if(!Tag[cur])return;
        int mid=lt+rt>>1;
        addtag(cur<<1,lt,mid,Tag[cur]);
        addtag(cur<<1|1,mid+1,rt,Tag[cur]);
        Tag[cur]=0;
        return;
    }
    void update(int cur,int lt,int rt,int qx,int qy,int val){
        if(lt>qy||rt<qx){
            return;
        }
        if(lt>=qx&&rt<=qy){
            addtag(cur,lt,rt,val);
            return;
        }
        pushdown(cur,lt,rt);
        int mid=lt+rt>>1;
        update(cur<<1,lt,mid,qx,qy,val);
        update(cur<<1|1,mid+1,rt,qx,qy,val);
        pushup(cur);
        return;
    }
    int query(int cur,int lt,int rt,int qx,int qy){
        if(lt>qy||rt<qx)return 0;
        if(lt>=qx&&rt<=qy)return Tree[cur];
        pushdown(cur,lt,rt);
        int mid=lt+rt>>1;
        return query(cur<<1,lt,mid,qx,qy)+query(cur<<1|1,mid+1,rt,qx,qy);
    }
    int find(int cur,int lt,int rt,int qx,int qy,int need){
        if(Tree[cur]==(rt-lt+1))return -1;
        if(lt==rt)return lt;
        pushdown(cur,lt,rt);
        int mid=lt+rt>>1;
        if(mid>=qy)return find(cur<<1,lt,mid,qx,qy,need);
        if(mid<qx)return find(cur<<1|1,mid+1,rt,qx,qy,need);
        if(mid+1<=need){
            int tmp=find(cur<<1|1,mid+1,rt,qx,qy,need);
            if(tmp!=-1)return tmp;
            return find(cur<<1,lt,mid,qx,qy,need);
        }
        else{
            int tmp=find(cur<<1,lt,mid,qx,qy,need);
            if(tmp!=-1)return tmp;
            return find(cur<<1|1,mid+1,rt,qx,qy,need);
        }
    }
}P;
signed main(){
    scanf("%lld%lld",&n,&k);
    for(int i=1;i<=n;i++){
        scanf("%lld",&a[i]);
    }
    for(int i=1;i<=n;i++)ed[a[i]]=i;
    for(int i=n;i>=1;i--)st[a[i]]=i;
    int cnt=0,ans=2e9;
    stk.push(0);
    for(int i=1;i<n;i++){
        stk.push(i);
        int col=a[i];
        if(i==ed[col]){
            vis[col]=true;
            if(st[col]<ed[col])P.update(1,1,n,st[col]+1,ed[col],1);
        }
        while(vis[a[stk.top()]])stk.pop();
        int lt=stk.top()+1;
        if(lt>i)continue;
        int tmp=P.query(1,1,n,lt,i);
        cnt+=(i-lt+1)-(tmp);
        int need=max(i-(n/2),1ll);//
        int S=P.find(1,1,n,lt,i,need);
        if(S==-1)continue;
        ans=min(ans,abs((i-S+1)-(n-(i-S+1))));
    }
    printf("%lld %lld",cnt,ans);
    return 0;
}