P7119 Mivik 的游戏

· · 题解

这是我第一个不看任何题解过的蓝题。

我想把自己曲折的思考过程分享给大家。

一起深度剖析这道题。

思路

一看标签：模拟，线段树。朴实无华。

看了一下题目，很明显是让我们先找一个通解。

它是如何消除一个反面朝上的硬币的？

凡事先从简单做起，考虑只有一个硬币反面朝上。

HHHTH

很显然，想让那个反面朝上的硬币反过来，就得存在 4 个反面朝上的硬币。

所以第一步，是把前面 3 个硬币一起反过来，需要 3 步。

TTTTH

接下来就可以把所有反面朝上的硬币全翻回来了，共需 4 步。

HHHHH 完成

如果我们令 p 为这个反面朝上的硬币的位置，答案就为：

ans=p*2-1

如果有两个甚至更多的硬币反面朝上呢？

HHHHTT

在这里，k 的值一开始不是 1，而是 2。

所以我们会把位置为 2，3，4 的硬币翻过来，位置为 1 的硬币没有动。

HTTTTT

接着，k 退回 2，并把所经过的位置上的硬币翻面。

HHHHHT

然后就只有一个硬币反面朝上了。

我们在分析过程中可以发现，若 k 为反面朝上的硬币的数量，则在翻硬币时，k 会不断增加，直到位置 k 上的硬币为反面，然后 k 会不断减少，直到退回 k 原来的值。

简的来说，就是 k 不断往右移，碰到一个反面朝上的硬币则折回，向左移回到原来的位置，这个反面朝上的硬币就消除了。

这样不断地消去，直到没有反面朝上的硬币。

无解的情况怎么判断？

无解的情况只有一种，就是 k 不断向右移，却一直没碰到反面朝上的硬币。

也就是说，在位置 k 的左边有 k 个硬币反面朝上。

可左边一共就 k-1 个位置！

所以令我们惊异的是，无解的情况不存在！

坏坏的出题人。

答案公式？

我们模拟一下这个场景。

此时一共有 m 个硬币反面朝上，k 的值目前为 m。

若这个硬币的位置为 $w_1$，则这个操作所用步数为：$w_1*2-1-2*(m-1)=w_1*2-m*2+1

然后 m 值减 1，但我们不让它减，让它在接下来的操作中体现,此时 k 的初始值更新为 m-1。

接着又碰到一个反面朝上的硬币，若这个硬币的位置为 w_2，则这个操作所用步数为：w_2*2-1-2*(m-2)=w_2*2-(m-1)*2+1

以此类推。

把所有的操作的步数推出来后，相加得：

2*(w_1+w_2+...+w_{m-1}+w_m)-2(m+(m-1)+...+2+1)+m*1 2*\sum\limits_{i=1}^mw_i-2(m+1)*m/2+m 2*\sum\limits_{i=1}^mw_i-(m+1)*m+m 2*\sum\limits_{i=1}^mw_i-m^2

所以，我们做到了……

等等，怎么维护 2*\sum_{i=1}^mw_i 和 m^2？

看到这种区间异或的题目，我们会想到P3870 [TJOI2009] 开关这道题。

先切了这道题，拿着 AC 的线段树代码，公式一套，就完成啦！

代码

#include<bits/stdc++.h>
#define N 1000010
#define int long long//不开 long long 见祖宗
using namespace std;
struct hhh{
    int l,r,cnt,sum,lz;
}dl[N*4];
int n,m,l,r;
int a[N];
char p;
void pushup(int bh){
    dl[bh].cnt=dl[bh*2].cnt+dl[bh*2+1].cnt;
    dl[bh].sum=dl[bh*2].sum+dl[bh*2+1].sum;
}
void pushdown(int bh){
    if(!dl[bh].lz) return;
    dl[bh*2].lz^=1;
    dl[bh*2].cnt=dl[bh*2].r-dl[bh*2].l+1-dl[bh*2].cnt;
    dl[bh*2].sum=(dl[bh*2].r+dl[bh*2].l)*(dl[bh*2].r-dl[bh*2].l+1)/2-dl[bh*2].sum;
    dl[bh*2+1].lz^=1;
    dl[bh*2+1].cnt=dl[bh*2+1].r-dl[bh*2+1].l+1-dl[bh*2+1].cnt;
    dl[bh*2+1].sum=(dl[bh*2+1].r+dl[bh*2+1].l)*(dl[bh*2+1].r-dl[bh*2+1].l+1)/2-dl[bh*2+1].sum;
    dl[bh].lz=0;
}
void build(int bh,int l,int r){
    dl[bh].l=l,dl[bh].r=r;
    if(l==r){
        if(a[l]) dl[bh].cnt=1,dl[bh].sum=l;
        return;
    }
    int mid=(l+r)>>1;
    build(bh*2,l,mid),build(bh*2+1,mid+1,r);
    pushup(bh);
}
void update(int bh,int L,int R){
    int l=dl[bh].l,r=dl[bh].r;
    if(l>=L&&r<=R){
        dl[bh].lz^=1;
        dl[bh].cnt=r-l+1-dl[bh].cnt;
        dl[bh].sum=(r+l)*(r-l+1)/2-dl[bh].sum;
        return;
    }
    pushdown(bh);
    int mid=(l+r)>>1;
    if(L<=mid) update(bh*2,L,R);
    if(R>mid) update(bh*2+1,L,R);
    pushup(bh);
}
signed main(){
    ios::sync_with_stdio(0);
    cin.tie(0),cout.tie(0);
    cin>>n>>m;
    for(int i=1;i<=n;i++){
        cin>>p;
        if(p=='T') a[i]=1;
    }
    build(1,1,n);
    cout<<2*dl[1].sum-dl[1].cnt*dl[1].cnt<<endl;
    while(m--){
        cin>>l>>r;
        update(1,l,r);
        cout<<2*dl[1].sum-dl[1].cnt*dl[1].cnt<<endl;
    }
    return 0;
}//由于我用的是cin和cout，这道题卡常又卡得紧，所以要开O2

后记

这篇题解注重于寻找通解的过程，而不是线段树怎么打。

如果有茬，欢迎向我私信。

QAQ。