解题思路
区间加等差数列+单点询问,用差分+线段树解决,线段树里维护的就是差分数组,区间加等差数列相当于在差分序列中l位置处+首项的值,r+1位置处-末项的值,中间加公差的值,然后单点询问就相当于在差分数列中求前缀和。
#include#include #include #include using namespace std;const int MAXN = 100005;typedef long long LL;inline int rd(){ int x=0,f=1;char ch=getchar(); while(!isdigit(ch)) {f=ch=='-'?0:1;ch=getchar();} while(isdigit(ch)) {x=(x<<1)+(x<<3)+ch-'0';ch=getchar();} return f?x:-x;}int n,m,a[MAXN],c[MAXN];LL sum[MAXN<<2],lazy[MAXN<<2];void pushdown(int x,int ln,int rn){ lazy[x<<1]+=lazy[x];lazy[x<<1|1]+=lazy[x]; sum[x<<1]+=ln*lazy[x];sum[x<<1|1]+=rn*lazy[x]; lazy[x]=0;}void build(int x,int l,int r){ if(l==r){sum[x]=c[l];return;} int mid=(l+r)>>1; build(x<<1,l,mid);build(x<<1|1,mid+1,r); sum[x]=sum[x<<1]+sum[x<<1|1];}void update(int x,int l,int r,int L,int R,int w){ if(L<=l && r<=R) {sum[x]+=(r-l+1)*w;lazy[x]+=w;return;} int mid=(l+r)>>1;if(lazy[x]) pushdown(x,mid-l+1,r-mid); if(L<=mid) update(x<<1,l,mid,L,R,w); if(mid >1;LL ret=0;if(lazy[x]) pushdown(x,mid-l+1,r-mid); if(L<=mid) ret+=query(x<<1,l,mid,L,R); if(mid