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

· · 题解

P12720 [Algo Beat Contest 002 G] Game Time

游戏的部分很简单，因为怎样都可以一步把答案的奇偶性改变，所以游戏的结果只取决于最后一个 1 的位置。

现在我们要做的就是，算最后一个 1 在奇数位上/没有 1 的子段个数。

容斥一下，算最后一个 1 在偶数位上的子段个数，答案为 \binom{n+1}{2} 减去这个。

对于一个 1 在 i，下一个 1 /边界在 nxt(i)，它作为最后一个 1 的区间为 [l,r](1\le l\le i\le r < nxt(i))，而且只有 l 对答案有影响，即要求 l 和 i 一奇一偶，所以这个 1 的贡献为 (nxt(i)-i)\lfloor i/2 \rfloor。

我们要求的就是 \sum_{a_i=1}(nxt(i)-i)\lfloor i/2\rfloor=\sum_{a_i=1}(nxt(i)\lfloor i/2\rfloor-i\lfloor i/2\rfloor)，说明答案只与相邻位的下标有关。考虑对于所有值为 0/1 的下标建平衡树，节点维护下标 x、子树答案和 sum、子树下标最小/大值 mi/mx，我们 pushup 的过程相当于把三段相邻的合并。也就是左子树最大下标和当前根、根和右子树最小下标合并，即

\begin{aligned}sum(x)&\leftarrow sum(ls)+sum(rs)-x\lfloor x/2\rfloor+x\lfloor mx(ls)/2\rfloor+mi(rs)\lfloor x/2\rfloor\\mi(x)&\leftarrow mi(ls)\\mx(x)&\leftarrow mx(rs)\end{aligned}

注意我们会少算最后一个 1 到边界的答案，记位置为 t，此时把答案加上 (n+1)\lfloor t/2\rfloor 即可。

考虑反转操作，使用 FHQ-Treap，只要将两棵树的 [l,r] 范围的树分裂下来然后交换拼回去即可。

综上时间复杂度 O((n+m)\log n)。好写。

#include<bits/stdc++.h>
#define int long long
using namespace std;
const int maxn=4e5+7;
int n,m;
#define ls tree[now].l
#define rs tree[now].r
int root[2],cnt;
struct node{
    int val,sum,mx,mi;
    int l,r,siz,wei;
}tree[maxn];
void pushup(int now){
    tree[now].siz=tree[ls].siz+tree[rs].siz+1;
    tree[now].sum=-tree[now].val*(tree[now].val/2);
    if(ls) tree[now].sum+=tree[ls].sum+(tree[ls].mx/2)*(tree[now].val);
    if(rs) tree[now].sum+=tree[rs].sum+(tree[now].val/2)*(tree[rs].mi);
    tree[now].mi=ls?tree[ls].mi:tree[now].val; 
    tree[now].mx=rs?tree[rs].mx:tree[now].val;
    // 维护子树和、子树下标最小/大值
}
int create(int val){
    tree[++cnt]={val,-val*(val/2),val,val,0,0,1,rand()};
    return cnt;
}
void split(int now,int val,int &rt1,int &rt2){
    if(!now){ rt1=rt2=0; return; }
    if(tree[now].val<=val){
        rt1=now;
        split(rs,val,rs,rt2);
    }else{
        rt2=now;
        split(ls,val,rt1,ls);
    }
    pushup(now);
}
int merge(int rt1,int rt2){
    if(!rt1||!rt2) return rt1+rt2;
    if(tree[rt1].wei>tree[rt2].wei){
        tree[rt1].r=merge(tree[rt1].r,rt2);
        pushup(rt1);
        return rt1;
    }else{
        tree[rt2].l=merge(rt1,tree[rt2].l);
        pushup(rt2);
        return rt2;
    }
}
void ins(int val,int wt){
    int x,y;
    split(root[wt],val-1,x,y);
    root[wt]=merge(merge(x,create(val)),y);
}
void swp(int l,int r){ // 交换
    int a,b,c,d,e,f,g,h;
    split(root[0],l-1,a,g);
    split(g,r,b,c);
    split(root[1],l-1,d,h);
    split(h,r,e,f);
    root[0]=merge(merge(a,e),c);
    root[1]=merge(merge(d,b),f);
}
signed main(){
    ios::sync_with_stdio(0);
    cin.tie(0); cout.tie(0);
    cin>>n>>m;
    for(int i=1,x;i<=n;i++)
        cin>>x, ins(i,x);
    for(int i=1,l,r;i<=m;i++){
        cin>>l>>r; swp(l,r);
        cout<<n*(n+1)/2-tree[root[1]].sum-(n+1)*(tree[root[1]].mx/2)<<'\n';
    }
    return 0;
}