题解：P12720 [Algo Beat Contest 002 G] Game Time

· · 题解

赛后 4min 过题什么水平 /fn。

首先我们发现谁获胜取决于最后一个 1 是谁操作的，在遍历时记录上一个 1 的位置并计算贡献，我们可以写出一份简单的暴力代码：

ll sum=0;
int lst=0;
for (int i=1;i<=n;i++){
    if (a[i]) lst=i;
    else sum+=i-lst; // 0 的连续段
    sum+=(lst+1)>>1; // 除以 2 是因为只有一半的情况会获胜
}
cout<<sum<<"\n";

这样复杂度为 O(nq)，我们考虑如何优化。

我们把贡献拆成两份，一个计算 0 连续段的个数，一个计算 (lst+1)>>1 的贡献。

然后这里又有区间反转操作，考虑用线段树维护。

线段树每个节点维护前面/后面连续 0/1 的个数、0/1 连续段的个数、先手/后手 1 处贡献的总和，共 8 项内容。

然后基于上面的描述，我们可以写出 pushup。

void pushup(int i){
    tr[i].sum0=tr[ls].sum0+tr[rs].sum0+tr[ls].r0*tr[rs].l0;
    tr[i].sum1=tr[ls].sum1+tr[rs].sum1+tr[ls].r1*tr[rs].l1;
    // 0/1 连续段个数
    tr[i].l0=(tr[ls].l0==tr[ls].len?tr[ls].len+tr[rs].l0:tr[ls].l0);
    tr[i].l1=(tr[ls].l1==tr[ls].len?tr[ls].len+tr[rs].l1:tr[ls].l1);
    tr[i].r0=(tr[rs].r0==tr[rs].len?tr[rs].len+tr[ls].r0:tr[rs].r0);
    tr[i].r1=(tr[rs].r1==tr[rs].len?tr[rs].len+tr[ls].r1:tr[rs].r1);
    // 前后连续 0/1 数量
    tr[i].ans0=tr[ls].ans0+tr[rs].ans0;
    if (tr[ls].r0!=tr[ls].len) tr[i].ans0+=tr[rs].l0*ll((tr[ls].r-tr[ls].r0+1)>>1);
    tr[i].ans1=tr[ls].ans1+tr[rs].ans1;
    if (tr[ls].r1!=tr[ls].len) tr[i].ans1+=tr[rs].l1*ll((tr[ls].r-tr[ls].r1+1)>>1); // 注意：全是 0 时不能算入贡献
    // 先手/后手 1 处贡献
}

区间修改时只需要打上标记然后交换 0/1 数据即可。

void pushdown(int i){
    if (tr[i].tag){
        swap(tr[ls].l0,tr[ls].l1);
        swap(tr[ls].r0,tr[ls].r1);
        swap(tr[ls].sum0,tr[ls].sum1);
        swap(tr[ls].ans0,tr[ls].ans1);
        tr[ls].tag^=1;

        swap(tr[rs].l0,tr[rs].l1);
        swap(tr[rs].r0,tr[rs].r1);
        swap(tr[rs].sum0,tr[rs].sum1);
        swap(tr[rs].ans0,tr[rs].ans1);
        tr[rs].tag^=1;

        tr[i].tag=0;
    }
}

void update(int i,int l,int r){
    if (tr[i].l>=l and tr[i].r<=r){
        swap(tr[i].l0,tr[i].l1);
        swap(tr[i].r0,tr[i].r1);
        swap(tr[i].sum0,tr[i].sum1);
        swap(tr[i].ans0,tr[i].ans1);
        tr[i].tag^=1;
        return;
    }
    pushdown(i);
    if (tr[ls].r>=l) update(ls,l,r);
    if (tr[rs].l<=r) update(rs,l,r);
    pushup(i);
}

建树时在对应位置上设置初始值就好了。

void build(int i,int l,int r){
    memset(&tr[i],0,sizeof(tr[i]));
    tr[i].l=l;
    tr[i].r=r;
    tr[i].len=r-l+1;
    if (l==r){
        if (a[l]==0) tr[i].l0=tr[i].r0=1,tr[i].sum0=1,tr[i].ans1=(l+1)>>1;
        else tr[i].l1=tr[i].r1=1,tr[i].sum1=1,tr[i].ans0=(l+1)>>1;
        return;
    }
    int mid=(l+r)>>1;
    build(ls,l,mid);
    build(rs,mid+1,r);
    pushup(i);
}

由于查询是全局的，所以每次可以直接输出 tr[1].sum0+tr[1].ans0。

总复杂度为线段树的 O(q\log n)，可以通过，完整代码就不给了。最后，别忘了建树 qwq。