自动搬运

查看原文

来自洛谷，原作者为

	ARIS2_0 路虽远，行则将至；事虽难，做则必成。

搬运于2025-08-24 23:07:08，当前版本为作者最后更新于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$。

1. $pos \bmod 3=0$：$w_i+(pos+\lfloor\frac{pos}{3}\rfloor)\times len\to w_i$。

2. $pos \bmod 3=1$：$w_i+(pos+\lfloor\frac{pos}{3}\rfloor)\times len+rest_{i,2}\to w_i$，然后使 $rest_{i,0},rest_{i,1},rest_{i,2}$ 变为 $rest_{i,1},rest_{i,2},rest_{i,0}$。

3. $pos \bmod 3=2$：$w_i+(pos+\lfloor\frac{pos}{3}\rfloor)\times len+rest_{i,1}+rest_{i,2}\to w_i$，然后使 $rest_{i,0},rest_{i,1},rest_{i,2}$ 变为 $rest_{i,2},rest_{i,0},rest_{i,1}$。

于是，我们可以写出以下的 $\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 题，我拼尽全力无法战胜。

果然还是技不如人吗。