计蒜客The Fake Fake Friends

@zryabc  August 30, 2019

题目

题目链接

互膜作为一种机房活动,在增进友谊、锻炼表达能力的同时,也能给蒟蒻以充分表达自己对神犇景仰之情的机会,可谓一举多得。

同时,它也是附中洗脑团队的日常。

每一天,n 个 OIer 都会围成一圈,为方便起见,我们不妨按顺时针为他们编号 1~n。

每个 OIer 都有一个 01 属性,这个属性代表着他们是蒟蒻还是神犇。在这里,为了简化问题,我们并不区分日常写挂的蒟蒻和什么都不会的蒟蒻,我们也不区分数论之神和 DSM(Data Structure Master)。

从11号 OIer 开始,每个人都有一次机会,在环上钦定一个区间,并对这个区间进行 orz。再一次,为了简化问题,这个区间可以包含该 OIer 本身。鉴于蒟蒻的膜拜会使人变神,而神犇乱膜会使人变成蒟蒻,这个区间内被 orz 过的 OIer 属性都会变成发起 orz 的 OIer 属性xor11。11~nn 号OIer依次膜过人后,互膜环节便宣告结束,大家也就回到各自的位置,继续一天的 OI 生活。

S 是这些 OIer 中的一员。在这一次互膜的时候,他的编号为 ss。S 已经预先得知了其他 n-1n−1 个 OIer 接下来要 orz 的区间,而他所想做的,就是选择一个区间,使互膜结束后神犇的数量最多,因为这表示这次互膜很成功。但他还要出题,所以希望你,OI 界的希望,帮他算一下方案。

思路

这题首先要理清各个点之间的关系。

不难发现,在进行覆盖操作的整个流程中,会发现在S之前的覆盖状态是确定的,所以说实际上只用考虑S之后的点被S的影响就行了。

然后我们会发现,每个点都有一个惟一的来源点,也就是说,这个点去更新其它点之前,最后一次更新它的点。

我们定义这个点为$fa[x]$

不难发现$fa[x]<x$,也就是说这是一个树形结构(森林)。

然后我们思考该如何处理这些信息,发现,我们最终对某个点有影响的只是这些根罢了,所以只需要维护每个点对根的状态(与根相同或不同)

所以在线段树上再加上维护这些信息。

最后覆盖的时候,就是覆盖一段根节点,处理一个根节点覆盖与不覆盖的差值,用ST表,线段树,单调队列等数据结构维护一下最优的覆盖区间就行了。

代码

#include<bits/stdc++.h>
#define M 2000005
#pragma GCC optimize(3)
using namespace std;
bool mm1;
struct YD_tree{
    struct YD{
        int l,r,mark;
    }tree[M<<2];
#define fa tree[p]
#define lson tree[p<<1]
#define rson tree[p<<1|1]
    void down(int p){
        if(fa.mark!=-1){
            lson.mark=fa.mark;
            rson.mark=fa.mark;
            fa.mark=-1;
        }
    }
    void build(int l,int r,int p){
        fa.l=l;fa.r=r;fa.mark=-1;
        if(l==r)return;
        int mid=(l+r)>>1;
        build(l,mid,p<<1);
        build(mid+1,r,p<<1|1);
    }
    void update(int l,int r,int d,int p){
        if(fa.l==l&&fa.r==r){
            fa.mark=d;
            return;
        }
        down(p);
        int mid=(fa.l+fa.r)>>1;
        if(r<=mid)update(l,r,d,p<<1);
        else if(l>mid)update(l,r,d,p<<1|1);
        else {
            update(l,mid,d,p<<1);
            update(mid+1,r,d,p<<1|1);
        }
    }
    int query(int x,int p){
        if(fa.l==x&&fa.r==x)return fa.mark;
        int mid=(fa.l+fa.r)>>1;
        down(p);
        if(x<=mid)return query(x,p<<1);
        return query(x,p<<1|1);
    }
#undef fa
#undef lson
#undef rson
}T1,T2,T3;
int L[M],R[M],n,S,A[M];
int w[M][2],val[M],pre[M];
bool mm2;
int main(){
    //printf("%lf\n",(&mm2-&mm1)/1024.0/1024);
    scanf("%d%d",&n,&S);
    for(int i=1;i<=n;i++)scanf("%d",&A[i]);
    for(int i=1;i<=n;i++){
        if(i==S)continue;
        scanf("%d%d",&L[i],&R[i]);
    }
    T1.build(1,n,1);
    for(int i=1;i<=n;i++)T1.update(i,i,A[i],1);
    for(int i=1;i<S;i++){
        int now=T1.query(i,1);now=!now;
        if(L[i]<=R[i])T1.update(L[i],R[i],now,1);
        else {
            T1.update(L[i],n,now,1);
            T1.update(1,R[i],now,1);
        }
    }
    T2.build(1,n,1);T3.build(1,n,1);
    for(int i=1;i<=n;i++)T2.update(i,i,i,1);
    for(int i=1;i<=n;i++)T3.update(i,i,0,1);
    for(int i=S+1;i<=n;i++){
        int a=T2.query(i,1),b=T3.query(i,1);b=b^1;
        if(L[i]<=R[i])T2.update(L[i],R[i],a,1),T3.update(L[i],R[i],b,1);
        else {
            T2.update(L[i],n,a,1);
            T2.update(1,R[i],a,1);
            T3.update(L[i],n,b,1);
            T3.update(1,R[i],b,1);
        }
    }
    for(int i=1;i<=n;i++){
        int a=T2.query(i,1);
        int b=T3.query(i,1);
        w[a][b^1]++;
    }
    int ans=0,st=T1.query(S,1);
    for(int i=1;i<=n;i++){
        int c=T1.query(i,1);
        ans+=w[i][c];
        val[i]=st!=c?0:w[i][c^1]-w[i][c];
    }
    int ret=0;
    for(int res=0,sum=0,i=1;i<=n;i++){
        res+=val[i];
        if(res<0)res=0;
        ret=max(ret,res);
        pre[i]=max(pre[i-1],sum+=val[i]);
    }
    for(int sum=0,suf=0,i=n;i>=2;i--){
        suf=max(suf,sum+=val[i]);
        ret=max(ret,pre[i-1]+suf);
    }
    printf("%d\n",ans+ret);
    return 0;
}

添加新评论