题解：[EPXLQ2024 fall round] 神奇磁铁

ARIS2_0 · 2024-12-16 12:42:15 · 题解

前言

好神奇的题面，赛时看了半天才看懂。

简化题意

设 f(x) 为拥有 x 块磁铁时，最大的能够激活的磁铁数量。

则本题题意即为：

给定长度为 n 的数组 a，第一种操作将区间 [l,r] 加上 x，第二种操作询问 \sum\limits_{i=l}^rf(2\times i)。

解题思路

考虑计算 f(2\times i)。由于要求有一个 y\in[1,i] 使得没有任意两个激活的磁铁的距离为 y，不难发现，对于一个固定的 y，激活磁铁的最优策略一定是激活 y 个，不激活 y 个，再激活 y 个，以此类推，直到第 2\times i 个磁铁。

考虑把磁铁的激活构造为如下形式：设 pos=\lceil\frac{2\times i}{3}\rceil，我们采用前面激活 pos 个，中间不激活 pos 个，最后激活 2\times i-2\times pos 个，总激活个数为 2\times i-pos=2\times i-\lceil\frac{2\times i}{3}\rceil=\lfloor\frac{4\times i}{3}\rfloor=i+\lfloor\frac{i}{3}\rfloor。

以下为证明：

• 若 pos=\lceil\frac{2\times i}{3}\rceil+1，前面激活和中间不激活的个数各 +1，后面激活的个数不多只少，不优。

• 若 pos=\lceil\frac{2\times i}{3}\rceil-1，前面激活和中间不激活的个数各 -1，而因为 3\times pos<2\times i，所以会有不激活的“第四部分”占据末尾，此时最大激活个数为 2\times pos=2\times(\lceil\frac{2\times i}{3}\rceil-1)\le2\times\lfloor\frac{2\times i}{3}\rfloor\le\lfloor\frac{4\times i}{3}\rfloor，同样不优。

这样，我们不是很严谨地证明了 f(2\times i)=i+\lfloor\frac{i}{3}\rfloor。

欢迎提供更严谨的证明，本蒟蒻还是太菜了。

代码实现

下文称 \sum\limits_{i=l}^rf(2\times i)=\sum\limits_{i=l}^ri\times\lfloor\frac{i}{3}\rfloor 为区间 [l,r] 的权值。

使用线段树，维护每个区间的权值、模 3 余 0,1,2 的数的个数，分别记为 w_i,rest_{i,0},rest_{i,1},rest_{i,2}。

考虑如何实现区间加操作：假设现在要把编号为 i ，长度为 len 的区间加上 pos。

于是，我们可以写出以下的 \rm{maketag()} 函数：

void maketag(int id,int pos,int len){
    tag[id]+=pos;
    switch(pos%3){
        case 0:{
            w[id]+=(pos+pos/3)*len;
            break;
        }
        case 1:{
            w[id]+=(pos+pos/3)*len+rest[id][2];
            int res=rest[id][2];
            rest[id][2]=rest[id][1];
            rest[id][1]=rest[id][0];
            rest[id][0]=res;
            break;
        }
        case 2:{
            w[id]+=(pos+pos/3)*len+rest[id][1]+rest[id][2];
            int res=rest[id][2];
            rest[id][2]=rest[id][0];
            rest[id][0]=rest[id][1];
            rest[id][1]=res;
            break;
        }
    }
}

但考虑到 pos 可能为负数，这样写连样例都过不去。

不过，我们可以找到一个最大的 ppos 满足 ppos\le pos,ppos \bmod 3=0，然后先调用 \rm{maketag}(\textit{id,ppos,len})，再调用 \rm{maketag}(\textit{id,pos-ppos,len})，这样可以保证正确性而且不用特判负数。

于是这道题就做完了。

AC Code

#include<bits/stdc++.h>
using namespace std;
#define int long long
#define pii pair<int,int>
#define fi first
#define se second
const int inf=1e16,maxn=5e5+10;
int a[maxn],w[4*maxn],rest[4*maxn][3],tag[4*maxn];
void pushup(int id){
    w[id]=w[id*2]+w[id*2+1];
    for(int i:{0,1,2})rest[id][i]=rest[id*2][i]+rest[id*2+1][i];
}
void build(int id,int l,int r){
    if(l==r){w[id]=a[l]+a[l]/3;rest[id][a[l]%3]=1;return;}
    int mid=(l+r)/2;
    build(id*2,l,mid);
    build(id*2+1,mid+1,r);
    pushup(id);
}
void maketag(int id,int pos,int len){
    if(pos<0 and pos%3){
        int ppos=pos;
        while(ppos%3)ppos--;
        maketag(id,ppos,len);
        maketag(id,pos-ppos,len);
        return;
    }
    tag[id]+=pos;
    switch(pos%3){
        case 0:{
            w[id]+=(pos+pos/3)*len;
            break;
        }
        case 1:{
            w[id]+=(pos+pos/3)*len+rest[id][2];
            int res=rest[id][2];
            rest[id][2]=rest[id][1];
            rest[id][1]=rest[id][0];
            rest[id][0]=res;
            break;
        }
        case 2:{
            w[id]+=(pos+pos/3)*len+rest[id][1]+rest[id][2];
            int res=rest[id][2];
            rest[id][2]=rest[id][0];
            rest[id][0]=rest[id][1];
            rest[id][1]=res;
            break;
        }
    }
}
void pushdown(int id,int l,int r){
    int mid=(l+r)/2;
    maketag(id*2,tag[id],mid-l+1);
    maketag(id*2+1,tag[id],r-mid);
    tag[id]=0;
}
bool inr(int l,int r,int cl,int cr){return cl<=l and r<=cr;}
bool outr(int l,int r,int cl,int cr){return cr<l or r<cl;}
void update(int id,int l,int r,int cl,int cr,int pos){
    if(inr(l,r,cl,cr)){maketag(id,pos,r-l+1);return;}
    if(outr(l,r,cl,cr))return;
    pushdown(id,l,r);
    int mid=(l+r)/2;
    update(id*2,l,mid,cl,cr,pos);
    update(id*2+1,mid+1,r,cl,cr,pos);
    pushup(id);
}
int check(int id,int l,int r,int cl,int cr){
    if(inr(l,r,cl,cr))return w[id];
    if(outr(l,r,cl,cr))return 0;
    pushdown(id,l,r);
    int mid=(l+r)/2;
    return check(id*2,l,mid,cl,cr)+check(id*2+1,mid+1,r,cl,cr);
}
signed main(){
    ios::sync_with_stdio(0);
    cin.tie(0);
    int n,m;cin>>n>>m;
    for(int i=1;i<=n;i++)cin>>a[i];
    build(1,1,n);
    while(m--){
        int op,l,r;cin>>op>>l>>r;
        if(op==1){
            int x;cin>>x;
            update(1,1,n,l,r,x);
        }
        else cout<<check(1,1,n,l,r)<<"\n";
    }
    return 0;
}

后言

机房有同学通过找规律轻轻松松飚过 C 题和 E 题，我拼尽全力无法战胜。

果然还是技不如人吗。