题解：P16758 [GKS 2020 #C] Candies

Jin_2014 · 2026-07-23 08:11:44 · 题解

题意：

有长度为 n 的糖果甜度数组 a，支持两类操作：

单点更新：
将第 x 颗糖果的甜度值修改为 v。
区间查询：计算子数组 [L,R] 的‌甜度分数‌，计算公式为：

S(L,R)=\sum_{i=L}^R(−1)^{i−L}\times a_i\times (i−L+1)

最后需要输出每个测试用例所有查询的甜度分数总和。

推公式：

展开：

S(L,R)\\=\sum_{i=L}^Ra_i\times(-1)^{i-L}\times(i-L+1)\\=(-1)^{i-L}\times[\sum_{i=L}^Ra_i\times i\times (-1)^i-(L-1)\times \sum_{i=L}^Ra_i\times (-1)^i]

据此我们可以定义两个辅助数组：

数组 b_i=a_i\times(-1)^i。
数组 c_i=a_i\times(-1)^i\times i。

最终查询公式简化为：

S(L,R)=(-1)^L\times (\sum_{i=L}^{R}c_i-(L-1)\times\sum_{i=L}^{R}b_i)

这样就转化为两个普通数组的区间求和问题。

思路1：分块：

思路：

将整个数组划分为大小为 \sqrt{n} 的块，每块维护两个全局统计量：

### 操作： 1. ‌更新‌：修改对应位置的 $b_i$ 和 $c_i$，并更新所属块的 bs 和 cs。 2. ‌查询‌：零散块暴力遍历累加，完整块直接使用预存的 $bs$ 和 $cs$ 统计值，即可快速得到区间和，代入公式得到甜度分数。 ### 时间复杂度： $O(T\times (N+M)\times\sqrt N)

代码：

#include<bits/stdc++.h>
#define LL long long
using namespace std;
const int N=2e5+5;
int n,m,len;
LL ans,a[N],id[N]; // 每个位置所属的块编号
LL b[N],bs[N]/* a[i]*(-1)^i */,c[N],cs[N];// a[i]*i*(-1)^i
// 获取 (-1)^i
inline int get(int i) 
{
return (i&1)?-1:1;
}
//初始化
void init() 
{
memset(bs,0,sizeof bs);
memset(cs,0,sizeof cs);
for(int i=1;i<=n;i++) 
{
    id[i]=i/len;
    int s=get(i);
    b[i]=(LL)a[i]*s;
    c[i]=(LL)a[i]*i*s;
    bs[id[i]]+=b[i];
    cs[id[i]]+=c[i];
}
}
//修改 
void add(int x,LL v) 
{
int s=get(x);
// 移除旧值贡献
bs[id[x]]-=b[x];
cs[id[x]]-=c[x];
// 更新全局数组
a[x]=v;
b[x]=(LL)v*s;
c[x]=(LL)v*x*s;

// 添加新值贡献
bs[id[x]]+=b[x];
cs[id[x]]+=c[x];
}
// 查询
void ch(int l,int r,LL &s1,LL &s2) 
{
s1=0,s2=0;
int bl=id[l],br=id[r];
if(bl==br)
    for(int i=l;i<=r;i++) 
    {
        s1+=b[i];
        s2+=c[i];
    }
else 
{
    // 左边零散部分
    for(int i=l;i<=min((bl+1)*len-1,n);i++) 
    {
        s1+=b[i];
        s2+=c[i];
    }
    // 中间完整块
    for(int i=bl+1;i<br;i++) 
    {
        s1+=bs[i];
        s2+=cs[i];
    }
    // 右边零散部分
    for(int i=br*len;i<=r;i++) 
    {
        s1+=b[i];
        s2+=c[i];
    }
}
}
LL s(int l,int r) 
{
LL s1,s2;
ch(l,r,s1,s2);
// 公式: S(l,r)=(-1)^l*[cs-(L-1)*bs]
return get(l)*(s2-(l-1)*s1);
}
int main() 
{
ios::sync_with_stdio(0);
cin.tie(0);cout.tie(0);
int T;
cin>>T;
for(int cas=1;cas<=T;cas++)
{
    cin>>n>>m;
    len=sqrt(n);
    for(int i=1;i<=n;i++)cin>>a[i];
    init();
    ans=0;
    while (m--) 
    {
        char c;
        cin>>c;
        if(c=='U')
        {
            int x;
            LL v;
            cin>>x>>v;
            add(x,v);
        } 
        else
        {
            int l,r;
            cin>>l>>r;
            ans+=s(l,r);
        }
    }
    cout<<"case #"<<cas<<": "<<ans<<"\n";
}
return 0;
}

思路2：线段树：

思路：

还是定义 b 和 c，并维护两个基础值：

### 操作：套板子即可，合并时只要将左右端点的 $bs$ 和 $cs$ 相加。 ### 时间复杂度： $O(T\times(N+M)\times \log N)

代码：

#include<bits/stdc++.h>
#define LL long long
using namespace std;
const int N=2e5+5;
int n,m,len;
LL ans,a[N],id[N]; // 每个位置所属的块编号
LL b[N],bs[N]/* a[i]*(-1)^i */,c[N],cs[N];// a[i]*i*(-1)^i
// 获取 (-1)^i
inline int get(int i) 
{
return (i&1)?-1:1;
}
//初始化
void init() 
{
memset(bs,0,sizeof bs);
memset(cs,0,sizeof cs);
for(int i=1;i<=n;i++) 
{
    id[i]=i/len;
    int s=get(i);
    b[i]=(LL)a[i]*s;
    c[i]=(LL)a[i]*i*s;
    bs[id[i]]+=b[i];
    cs[id[i]]+=c[i];
}
}
//修改 
void add(int x,LL v) 
{
int s=get(x);
// 移除旧值贡献
bs[id[x]]-=b[x];
cs[id[x]]-=c[x];
// 更新全局数组
a[x]=v;
b[x]=(LL)v*s;
c[x]=(LL)v*x*s;

// 添加新值贡献
bs[id[x]]+=b[x];
cs[id[x]]+=c[x];
}
// 查询
void ch(int l,int r,LL &s1,LL &s2) 
{
s1=0,s2=0;
int bl=id[l],br=id[r];
if(bl==br)
    for(int i=l;i<=r;i++) 
    {
        s1+=b[i];
        s2+=c[i];
    }
else 
{
    // 左边零散部分
    for(int i=l;i<=min((bl+1)*len-1,n);i++) 
    {
        s1+=b[i];
        s2+=c[i];
    }
    // 中间完整块
    for(int i=bl+1;i<br;i++) 
    {
        s1+=bs[i];
        s2+=cs[i];
    }
    // 右边零散部分
    for(int i=br*len;i<=r;i++) 
    {
        s1+=b[i];
        s2+=c[i];
    }
}
}
LL s(int l,int r) 
{
LL s1,s2;
ch(l,r,s1,s2);
// 公式: S(l,r)=(-1)^l*[cs-(L-1)*bs]
return get(l)*(s2-(l-1)*s1);
}
int main() 
{
ios::sync_with_stdio(0);
cin.tie(0);cout.tie(0);
int T;
cin>>T;
for(int cas=1;cas<=T;cas++)
{
    cin>>n>>m;
    len=sqrt(n);
    for(int i=1;i<=n;i++)cin>>a[i];
    init();
    ans=0;
    while(m--) 
    {
        char c;
        cin>>c;
        if(c=='U')
        {
            int x;
            LL v;
            cin>>x>>v;
            add(x,v);
        } 
        else
        {
            int l,r;
            cin>>l>>r;
            ans+=s(l,r);
        }
    }
    cout<<"case #"<<cas<<": "<<ans<<"\n";
}
return 0;
}

思路3：树状数组：

思路：

套前面的公式就行。

操作：

单点查询和修改：
套版子。
区间查询：
基于树状数组能支持前缀和查询，直接 s(r)-s(l-1) 就行（不懂可以做做 P3374）。
时间复杂度：
### 代码： ```cpp #include<bits/stdc++.h> #define LL long long using namespace std; const int N=200005; int n,m; LL ans,a[N],b[N],c[N]; // 获取 (-1)^i inline LL get(int i) { return (i&1)?-1:1; } inline int lowbit(int x) { return x&-x; } // 单点修改 void add(LL tr[],int x,LL d) { for(int i=x;i<=n;i+=lowbit(i))tr[i]+=d; } // 单点查询 LL s(LL tr[],int x) { LL ans=0; for(int i=x;i;i-=lowbit(i))ans+=tr[i]; return ans; } // 区间查询 LL ch(LL tr[],int l,int r) { return s(tr,r)-s(tr,l-1); } int main() { ios::sync_with_stdio(0); cin.tie(0);cout.tie(0); int T; cin>>T; for(int cas=1;cas<=T;cas++) { memset(b,0,sizeof b); memset(c,0,sizeof c); cin>>n>>m; for(int i=1;i<=n;i++)cin>>a[i]; for(int i=1;i<=n;i++) { int s=get(i); add(b,i,a[i]*s); add(c,i,a[i]*i*s); } ans=0; while(m--) { char op; cin>>op; if(op=='U') { int x; LL v; cin>>x>>v; LL s=get(x); // 先移除旧值贡献 add(b,x,-a[x]*s); add(c,x,-a[x]*x*s); // 更新数值 a[x]=v; // 加入新值贡献 add(b,x,v*s); add(c,x,v*x*s); } else { int l,r; cin>>l>>r; ans+=get(l)*(ch(c,l,r)-(l-1)*ch(b,l,r)); } } cout<<"Case #"<<cas<<": "<<ans<<"\n"; } return 0; } ```