@[codwarm](/user/775993) tag 也要开 5 倍空间
```cpp
#include<bits/stdc++.h>
using namespace std;
#define ull unsigned long long
#define ll long long
#define INF 0x3f3f3f3f
#define re register
#define il inline
#define gc getchar
#define int ll
inline int read()
{
int f=1,k=0;
char c = getchar();
while (c <'0' || c > '9')
{
if (c=='-') f=-1;
c=getchar();
}
while(c >= '0' && c <= '9') k = (k << 1)+(k << 3)+(c^48),c=getchar();
return k*f;
}
const int N = 500005;
int n,m,op,x,y,k,sum[N*5],a[N],tag[N * 5];
void build(int k,int l,int r)
{
if (l > r) return;
if (l == r)
{
sum[k] = a[l];
return ;
}
int mid = l+r>>1;
build(k<<1,l,mid);build(k<<1|1,mid+1,r);
sum[k] = sum[k << 1] + sum[k << 1 | 1];
return;
}
void pushdown(int k,int l,int r)
{
if (tag[k])
{
int mid = l +r >> 1;
tag[k << 1] += tag[k];
tag[k << 1 | 1] += tag[k];
sum[k<<1] += tag[k] * (mid-l+1);
sum[k << 1 | 1] += tag[k] * (r-mid);
tag[k] = 0;
}
}
void modify(int k,int l,int r,int x,int y,int v)
{
if (x > r || y < l) return;
if (x <= l && y >= r)
{
sum[k] += (r-l+1) * v;
tag[k] += v;
}
else
{
pushdown(k,l,r);
int mid = l + r >> 1;
modify(k<<1,l,mid,x,y,v);
modify (k<<1|1,mid+1,r,x,y,v);
sum[k] = sum[k<<1] + sum[k << 1 | 1];
}
}
int query(int k,int l,int r,int x,int y)
{
if (x > r || y < l) return 0;
if (x <= l && y >= r)
{
return sum[k];
}
else
{
pushdown(k,l,r);
int mid = l + r>> 1;
return query(k<<1,l,mid,x,y) + query(k<<1|1,mid+1,r,x,y);
}
}
signed main()
{
n = read(),m = read();
for (int i = 1;i <= n;i++) a[i] = read();
build(1,1,n);
while (m--)
{
op = read();
if (op == 1)
{
x = read(),y = read(),k = read();
modify(1,1,n,x,y,k);
}
else
{
x = read();
cout << query(1,1,n,x,x) << endl;
}
}
return 0;
}
```
by 5t0_0r2 @ 2023-11-25 11:31:05
你的tag数组开小了
by Filberte @ 2023-11-25 11:32:00
谢谢大佬们,此贴结。
by codwarm @ 2023-11-25 11:35:29