P12720 题解

DHeasy · 2025-05-26 19:33:49 · 题解

T611148 [Algo Beat Contest 002 G] Game Time

出题人题解

1. 考虑博弈部分

不难想到，谁赢只取决于最后一个 1 的位置。如果最后一个 1 是由小 D 决定的，小 D 赢，否则小 H 赢。特别的，如果全是 0，则小 D 赢。

2. O(n^2m) 暴力

对于每次修改，枚举所有区间重新计算答案即可。

3. O(nm) 暴力

首先可以计算 1 和连续的 0 对答案的贡献。

3.1. 0 的贡献

这是简单的，对于一个长度为 l 的 0 的极长段（即端点左右为 1 或数列边界），对答案的贡献为 \frac{l\times (l+1)}{2}。

3.2. 1 的贡献

设第 i 位是 1，即 a_i=1，记 j 位最大的整数且 a_{i+1}\sim a_j 都为 0，不难发现对于所有的区间 [l,r] 满足（1\le l\le i\le r\le j），只需要考虑第 i 位是由谁决定的。

而 O(1) 判断是简单的，只需考虑 i 与 l 的奇偶性。如果 i 与 l 奇偶性相同，则是由小 D 决定，即小 D 赢，否则小 H 赢。

所以第 i 位对答案的贡献为 \lceil\frac{i}{2}\rceil\times(j-i+1)（解释：与 i 奇偶性相同的位的数量乘上右端点数量）。

3.3. O(nm) 暴力

直接暴力修改然后按照上述方式计算答案即可。

4. O((n+m)\log n)正解

注意到答案是可以用区间维护的，且可以将若干子区间合并计算出区间的答案。

于是可以用线段树维护区间 [l,r] 的答案，贡献计算方式和上文一样，然后要注意合并两个区间时区间的点会产生的新贡献。

具体合并方式见代码注释。

5. 代码

#include<bits/stdc++.h>
#define ll long long
#define re register
#define fi first
#define se second
using namespace std;
inline ll read(){
    ll res=0ll,f=1;
    char c;
    for(;(c=getchar())<'0'||c>'9';c=='-'?f=-f:0);
    while(c>='0' && c<='9') res=(res<<1) + (res<<3) + c-'0',c=getchar();
    return res*f;
}
inline ll Max(re ll x,re ll y){return x>y?x:y;}
inline ll Min(re ll x,re ll y){return x<y?x:y;}
inline void cmax(re auto &x,re auto y){x=Max(x,y);}
inline void cmin(re auto &x,re auto y){x=Min(x,y);}
/*-----------------*/
const int N=2e5+20;
int n,m,a[N];
inline ll g(re ll len){return len*(len+1)/2;}
struct P{
    int l,r,h0,t0,id;// 左、右端点，左 0 的个数，右 0 的个数，最后一个 1 的编号
    int num1,num2;// 奇数位上 1 的数量，偶数位上 1 的数量
    ll sum1,sum2,ans;// 奇数位上 1 的权值和，偶数位上 1 的权值和
    bool f;// 是否全 0
    /*
    权值：1 后面的 0 的数量 +1
    <1> 00000000 + 00000000 = 0000000000000000
    <2> 00000000 + 00100010 = 00100010 - 00 + 0000000000 + (len = 8) / 2 * (sum1 = 4) + (len - len / 2) * (sum2 = 2)
    <3> 00100010 + 00000000 = 00100010 - 0 + 000000000 + (((id = 7) - (l = 1)) / 2 + 1) * (len = 8)
    <4> 00100010 + 00110010 = 00100010 + 00110010 - 0 - 00 + 000 + ... + ...
    */
    P friend operator +(P x,P y){
        P z={x.l,y.r,0,0,0,0,0,0,0,0,0};
        if(x.f&&y.f) return P{x.l,y.r,0,0,0,0,0,0,0,g(y.r-x.l+1),1};
        else if(x.f){
            int len=x.r-x.l+1;
            z.h0=len+y.h0,z.t0=y.t0,z.id=y.id,z.f=0;
            (len&1)?(z.sum1=y.sum2,z.sum2=y.sum1,z.num1=y.num2,z.num2=y.num1):
                    (z.sum1=y.sum1,z.sum2=y.sum2,z.num1=y.num1,z.num2=y.num2);
            z.ans+=y.ans-g(y.h0)+g(z.h0);// 0 的贡献
            z.ans+=(ll)len/2*y.sum1+(ll)(len-len/2)*y.sum2;// 1 的贡献
            return z;
        }
        else if(y.f){
            int len=y.r-y.l+1;
            z.h0=x.h0,z.t0=x.t0+len,z.id=x.id,z.f=0;
            z.num1=x.num1,z.num2=x.num2;
            int a=x.id-x.l+1;
            (a&1)?(z.sum1=x.sum1+len,z.sum2=x.sum2):
                  (z.sum1=x.sum1,z.sum2=x.sum2+len);
            z.ans+=x.ans-g(x.t0)+g(z.t0);// 0 的贡献
            z.ans+=(ll)(a+1)/2*len;// 1 的贡献
            return z;
        }
        else{
            int lx=x.r-x.l+1;
            z.h0=x.h0,z.t0=y.t0,z.id=y.id,z.f=0;
            /* x */
            z.num1=x.num1,z.num2=x.num2;
            int a=x.id-x.l+1;
            (a&1)?(z.sum1=x.sum1+y.h0,z.sum2=x.sum2):
                  (z.sum1=x.sum1,z.sum2=x.sum2+y.h0);
            /* y */
            (lx&1)?(z.sum1+=y.sum2,z.sum2+=y.sum1,z.num1+=y.num2,z.num2+=y.num1):
                   (z.sum1+=y.sum1,z.sum2+=y.sum2,z.num1+=y.num1,z.num2+=y.num2);
            /* ans */
            z.ans+=g(x.t0+y.h0)-g(x.t0)-g(y.h0);// 0 的贡献
            z.ans+=x.ans+(ll)(a+1)/2*y.h0;// x 的贡献
            z.ans+=y.ans+(ll)lx/2*y.sum1+(ll)(lx-lx/2)*y.sum2;// y 的贡献
            return z;
        }
    }
};
inline void Swap(re P &x,re P &y){
    P z=x;x=y;y=z;
}
struct TR{
    P t1[N<<2],t2[N<<2];bool la[N<<2];
    #define mid ((l+r)>>1)
    inline void build(re int p,re int l,re int r){
        if(l==r){
            if(a[l]&1){
                t1[p]=P{l,l,0,0,l,1,0,1,0,1,0};
                t2[p]=P{l,l,0,0,0,0,0,0,0,1,1};
            }
            else{
                t1[p]=P{l,l,0,0,0,0,0,0,0,1,1};
                t2[p]=P{l,l,0,0,l,1,0,1,0,1,0};
            }
            return;
        }
        build(p<<1,l,mid),build(p<<1|1,mid+1,r);
        t1[p]=t1[p<<1]+t1[p<<1|1];
        t2[p]=t2[p<<1]+t2[p<<1|1];
        return;
    }
    inline void push_down(re int p){
        if(!la[p]) return;
        la[p<<1]^=1,la[p<<1|1]^=1;
        Swap(t1[p<<1],t2[p<<1]);
        Swap(t1[p<<1|1],t2[p<<1|1]);
        la[p]=0;
    }
    inline void update(re int p,re int l,re int r,re int L,re int R){
        if(r<L||R<l) return;
        if(L<=l&&r<=R) return Swap(t1[p],t2[p]),la[p]^=1,void();
        push_down(p),update(p<<1,l,mid,L,R),update(p<<1|1,mid+1,r,L,R);
        t1[p]=t1[p<<1]+t1[p<<1|1],t2[p]=t2[p<<1]+t2[p<<1|1];
    }
    inline ll query(){return t1[1].ans;}
}tr;
int main(){
    n=read();m=read();
    for(re int i=1;i<=n;i++) a[i]=read();
    tr.build(1,1,n);
    while(m--){
        int l,r;
        l=read();r=read();
        tr.update(1,1,n,l,r);
        printf("%lld\n",tr.query());
    }
    return 0;
}