题解：P13976 数列分块入门 1

ingo_dtw · 2025-09-07 00:17:06 · 题解

P13976 数列分块入门 1

题目描述：

• 0 l r c：将区间 [l,r] 内的数全部加 c。
• 1 l r c：查询 a_r 的值（忽略 l 和 c）。

解题思路：

• 虽然树状数组通常用于单点修改和区间查询，但通过维护差分数组，我们可以让它高效地支持区间修改和单点查询：
  • 区间修改：对区间 [l, r] 加 c 等价于：
  • d_l += c
  • d_{r+1} -= c
  • 单点查询：位置 r 的值 a_r 等于差分数组的前缀和：a_r = \sum_{i=1}^{r} d_i

Ac Code：

#include<bits/stdc++.h>
using namespace std;
char buf[1<<23],*p1=buf,*p2=buf;
#define gc() (p1==p2&&(p2=(p1=buf)+fread(buf,1,1<<21,stdin),p1==p2)?EOF:*p1++)
#ifdef __linux__
#define pc putchar_unlocked
#else
#define pc _putchar_nolock
#endif
#define int long long
#define rint register int
#define R register
#define _ read<int>()
template<class T>inline T read()
{
    R T r=0,f=1;R char c=gc();
    while(!isdigit(c))
    {
        if(c=='-') f=-1;
        c=gc();
    } 
    while(isdigit(c)) r=(r<<1)+(r<<3)+(c^48),c=gc();
    return f*r;
}
inline void out(rint x)
{
    if(x<0) pc('-');
    if(x<10) pc(x+'0');
    else out(x/10),pc(x%10+'0');
}
const int N=3e5+10;
int a[N],tr[N];
inline int lowbit(rint x)
{
    return x&(-x);
}
inline void modify(rint p,rint x)
{
    while(p<N)
    {
        tr[p]+=x;
        p+=lowbit(p);
    }
}
inline int query(rint p)
{
    rint ans=0;
    while(p>0)
    {
        ans+=tr[p];
        p-=lowbit(p);
    }
    return ans;
}
signed main()
{
    rint n=_;
    for(rint i=1;i<=n;i++)
    {
        rint x=_;
        modify(i,x);
        modify(i+1,-x);
    }
    for(rint i=1;i<=n;i++)
    {
        rint op=_;
        if(op==0)
        {
            rint l=_,r=_,c=_;
            modify(l,c);
            modify(r+1,-c);
        }
        else
        {
            rint l=_,r=_,c=_;
            printf("%lld\n",query(r));
        }
    }
    return 0;
}