C42 线段树+差分 P1438 无聊的数列

#include<iostream>
using namespace std;

#define LL long long
#define ls u<<1
#define rs u<<1|1
#define mid ((l+r)>>1)
const int N=100005;
int a[ N];
LL sum[ N<<2],tag[ N<<2];
//sum:区间和, tag:懒标记

void pushup(int u){ //上传
  sum[ u]=sum[ ls]+sum[ rs];
}
void pushdown(int u,int l,int r){ //下传
  sum[ ls]+=tag[ u]*(mid-l+1);
  sum[ rs]+=tag[ u]*(r-mid);
  tag[ ls]+=tag[ u];
  tag[ rs]+=tag[ u];  
  tag[ u]=0;
}
void build(int u,int l,int r){ //建树
  sum[ u]=a[ l]; tag[ u]=0;
  if(l==r) return;
  build(ls,l,mid);
  build(rs,mid+1,r);
  pushup(u);
}
void change(int u,int l,int r,int x,int y,LL v){ //区修
  if(x<=l&&r<=y){
    sum[ u]+=(r-l+1)*v;
    tag[ u]+=v; return;
  }
  pushdown(u,l,r);
  if(x<=mid) change(ls,l,mid,x,y,v);
  if(y>mid) change(rs,mid+1,r,x,y,v);
  pushup(u);
}
LL query(int u,int l,int r,int x,int y){ //区查
  if(x<=l&&r<=y) return sum[ u];
  pushdown(u,l,r);
  LL s=0;
  if(x<=mid) s+=query(ls,l,mid,x,y);
  if(y>mid) s+=query(rs,mid+1,r,x,y);
  return s;
}
int main(){
  int n,m,op,l,r,k,d,p; scanf("%d%d",&n,&m);
  for(int i=1;i<=n;i++) scanf("%d",&a[ i]);
  for(int i=n;i>1;i--) a[ i]-=a[ i-1]; //差分
  build(1,1,n);
  
  for(int i=1;i<=m;i++){
    scanf("%d",&op);
    if(op==1){
      scanf("%d%d%d%d",&l,&r,&k,&d);
      change(1,1,n,l,l,k);
      if(l+1<=r) change(1,1,n,l+1,r,d);
      if(r<n) change(1,1,n,r+1,r+1,-(k+d*(r-l)));
    }
    else{
      scanf("%d",&p);
      printf("%lld\n",query(1,1,n,1,p));
    }
  }
  return 0;
}

C42 线段树+差分 P1438 无聊的数列

#include<iostream>
using namespace std;

#define LL long long #define ls u<<1 #define rs u<<1|1 #define mid ((l+r)>>1) const int N=100005; int a[ N]; LL sum[ N<<2],tag[ N<<2]; //sum:区间和, tag:懒标记

void pushup(int u){ //上传 sum[ u]=sum[ ls]+sum[ rs]; } void pushdown(int u,int l,int r){ //下传 sum[ ls]+=tag[ u](mid-l+1); sum[ rs]+=tag[ u](r-mid); tag[ ls]+=tag[ u]; tag[ rs]+=tag[ u];
tag[ u]=0; } void build(int u,int l,int r){ //建树 sum[ u]=a[ l]; tag[ u]=0; if(l==r) return; build(ls,l,mid); build(rs,mid+1,r); pushup(u); } void change(int u,int l,int r,int x,int y,LL v){ //区修 if(x<=l&&r<=y){ sum[ u]+=(r-l+1)*v; tag[ u]+=v; return; } pushdown(u,l,r); if(x<=mid) change(ls,l,mid,x,y,v); if(y>mid) change(rs,mid+1,r,x,y,v); pushup(u); } LL query(int u,int l,int r,int x,int y){ //区查 if(x<=l&&r<=y) return sum[ u]; pushdown(u,l,r); LL s=0; if(x<=mid) s+=query(ls,l,mid,x,y); if(y>mid) s+=query(rs,mid+1,r,x,y); return s; } int main(){ int n,m,op,l,r,k,d,p; scanf("%d%d",&n,&m); for(int i=1;i<=n;i++) scanf("%d",&a[ i]); for(int i=n;i>1;i--) a[ i]-=a[ i-1]; //差分 build(1,1,n);

for(int i=1;i<=m;i++){ scanf("%d",&op); if(op==1){ scanf("%d%d%d%d",&l,&r,&k,&d); change(1,1,n,l,l,k); if(l+1<=r) change(1,1,n,l+1,r,d); if(r<n) change(1,1,n,r+1,r+1,-(k+d*(r-l))); } else{ scanf("%d",&p); printf("%lld\n",query(1,1,n,1,p)); } } return 0; }</pre>