题目描述
- 一个简单的整数问题2
题目
提交记录
讨论
题解
视频讲解
给定一个长度为 N 的数列 A,以及 M 条指令,每条指令可能是以下两种之一:
C l r d,表示把 A[l],A[l+1],…,A[r] 都加上 d。
Q l r,表示询问数列中第 l∼r 个数的和。
对于每个询问,输出一个整数表示答案。
输入格式
第一行两个整数 N,M。
第二行 N 个整数 A[i]。
接下来 M 行表示 M 条指令,每条指令的格式如题目描述所示。
输出格式
对于每个询问,输出一个整数表示答案。
每个答案占一行。
数据范围
1≤N,M≤105,
|d|≤10000,
|A[i]|≤109
输入样例:
10 5
1 2 3 4 5 6 7 8 9 10
Q 4 4
Q 1 10
Q 2 4
C 3 6 3
Q 2 4
输出样例:
4
55
9
15
算法1
(数组数组) $O(mlogn)$
C++ 代码
#include <iostream>
#include <cstring>
using namespace std;
typedef long long LL;
const int N = 1e5 + 10;
int n, m;
int a[N],b[N];
LL tr[N],tri[N];
int lowbit(int x)
{return x&-x;}
void add(LL tr[N],int x,LL v)
{
for(int i=x;i<N;i+=lowbit(i))
tr[i]+=v;
}
LL sum(LL tr[N],int x)
{
LL res=0;
for(int i=x;i;i-=lowbit(i))
res+=tr[i];
return res;
}
LL query(int x)
{
return sum(tr,x)*(x+1)-sum(tri,x);
}
int main()
{
scanf("%d%d",&n,&m);
for(int i=1;i<=n;i++) scanf("%d",&a[i]);
for(int i=1;i<=n;i++)
{
b[i]=a[i]-a[i-1];
add(tr,i,b[i]);
add(tri,i,(LL)i*b[i]);
}
while (m--)
{
char op[2];
int l, r, c;
scanf("%s", op);
if (op[0] == 'Q')
{
scanf("%d%d", &l, &r);
printf("%lld\n",query(r)-query(l-1));
}
else
{
scanf("%d%d%d", &l, &r, &c);
add(tr,l,c),add(tr,r+1,-c);
add(tri,l,l*c),add(tri,r+1,-(r+1)*c);
}
}
return 0;
}
算法2
(线段树) $O(mlogn)$
C++ 代码
#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
typedef long long LL;
const int N = 1e5 + 10;
int n, m;
int a[N];
struct node
{
int l,r;
LL sum;
int add;
}tr[4*N];
void pushup(int u)
{
tr[u].sum=tr[u<<1].sum+tr[u<<1|1].sum;
}
void pushdown(int u)
{
auto&root=tr[u];
auto&left=tr[u<<1];
auto&right=tr[u<<1|1];
left.add+=root.add;
right.add+=root.add;
left.sum+=(left.r-left.l+1)*root.add;
right.sum+=(right.r-right.l+1)*root.add;
root.add=0;
}
void build(int u,int l,int r)
{
if(l==r) tr[u]={l,r,a[l]};
else
{
tr[u]={l,r};
int mid=l+r>>1;
build(u<<1,l,mid);
build(u<<1|1,mid+1,r);
pushup(u);
}
}
LL query(int u,int l,int r)
{
if(l<=tr[u].l&&tr[u].r<=r)
return tr[u].sum;
pushdown(u);LL res=0;
int mid=tr[u].l+tr[u].r>>1;
if(l<=mid) res+=query(u<<1,l,r);
if(r>mid) res+=query(u<<1|1,l,r);
return res;
}
void modify(int u,int l,int r,int d)
{
if(l<=tr[u].l&&tr[u].r<=r)
{
tr[u].add+=d;
tr[u].sum+=(tr[u].r-tr[u].l+1)*d;
}
else
{
pushdown(u);
int mid=tr[u].l+tr[u].r>>1;
if(l<=mid) modify(u<<1,l,r,d);
if(r>mid) modify(u<<1|1,l,r,d);
pushup(u);
}
}
int main()
{
scanf("%d%d", &n, &m);
for (int i = 1; i <= n; ++i) scanf("%d", &a[i]);
build(1, 1, n);
char op[2];
int l, r, t;
while (m -- )
{
scanf("%s%d%d", op, &l, &r);
if (*op == 'Q') printf("%lld\n", query(1, l, r));
else
{
scanf("%d", &t);
modify(1, l, r, t);
}
}
return 0;
}