钢门拉珠问题

Basori_Tiara · 2023-10-12 15:06:42 · 题解

P3587

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

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

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

对于一种颜色 i，假设他的最左在 st_i，最右在 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;
}